Scaling Public Key Cryptography Without Digital Certificates

83 concepts88 papers2 proposals

In traditional public-key cryptography, asymmetric key pairs solve the problem of secure communication, but they introduce a secondary dilemma: trust verification. If Alice wants to send an encrypted message to Bob, she needs Bob's public key. But how can she be absolutely certain that the public key belongs to Bob and not to an attacker masquerading as him?

The legacy solution is Public Key Infrastructure (PKI), which relies on a trusted third party called a Certificate Authority (CA) to issue a digital certificate. This certificate cryptographically binds a user's identity to their public key. While secure, this architecture imposes a massive administrative, computational, and storage burden—often referred to as the certificate management problem.

As networks scale to billions of resource-constrained Internet of Things (IoT) devices, cloud nodes, and mobile systems, this "certificate tax" becomes a critical bottleneck. To overcome these constraints, researchers have developed alternative cryptographic paradigms that eliminate digital certificates entirely while preserving trust and non-repudiation.

The Bottleneck of Traditional PKI

To understand why alternative architectures are necessary, consider what happens during a standard certificate-based exchange. When two nodes establish a secure session, they must transmit and parse complex digital certificate chains. Furthermore, to ensure a key has not been compromised, nodes must continuously consult massive, centralized databases known as Certificate Revocation Lists (CRLs) or use online verification protocols.

In high-density or real-time environments, this overhead is prohibitive. For instance, the authors of Comparative evaluation of pseudonym-based anonymisation techniques for connected autonomous vehicles (CAVs) demonstrate that relying on large-scale CRLs and frequent certificate updates creates severe processing and storage bottlenecks for connected vehicles, where safety messages must be processed with millisecond latency. As noted by Ji‐Jian Chin et al. in An Efficient and Provable Secure Certificateless Identification Scheme in the Standard Model, this administrative complexity scales poorly as the number of decentralized network participants grows.

Identity-Based Cryptography: Making the Identity the Key

The most intuitive way to eliminate digital certificates is to make a user's public key something that is already inherently known and unique to them: their identity string. This is the core mechanism of Identity-Based Cryptography (IBC).

Instead of generating a random string of numbers for a public key and verifying it with a certificate, a user's public key can be their email address, an IP address, or a phone number.

Traditional PKI:  [User Identity] <--- (Digital Certificate) ---> [Random Public Key]
Identity-Based:   [User Identity] === [Public Key]

For example, Jared W. Ring et al. applied this to Voice over IP (VoIP) networks in A new authentication mechanism and key agreement protocol for SIP using identity-based cryptography, utilizing a user's Session Initiation Protocol (SIP) address directly as their public key. By doing so, they bypassed the need for mobile devices to store and verify external credentials. Similarly, Xian-Zhu Li proposed an alternative handshake in An Improved TLS handshake protocol that replaces standard TLS certificates with identity strings, significantly reducing handshake latency and communication overhead.

How the Math Works Intuitively

In an identity-based system, a central authority called the Private Key Generator (PKG) generates a master public key and a master secret key.

  1. Encryption/Verification: Anyone can encrypt a message or verify a signature for Bob using only the PKG's public parameters and Bob's publicly known identity string (e.g., [email protected]). No certificate lookup is required because the identity is the mathematical input to the cryptographic function.
  2. Decryption/Signing: To decrypt messages, Bob authenticates himself to the PKG. The PKG uses its master secret key and Bob's identity string to compute Bob's unique private key and delivers it to him securely.

By eliminating certificate transmission, Hongwei Li et al. demonstrated in Identity-Based Cryptography for Cloud Security that IBC can reduce communication overhead by up to 70% and client-side computation by over 80% compared to standard certificate-based SSL/TLS setups.

The Key Escrow Problem and Certificateless Solutions

While IBC elegantly solves the certificate management problem, it introduces a severe security trade-off: key escrow. Because the PKG uses its master secret key to calculate every user's private key, the PKG inherently possesses the ability to decrypt any message or forge any user's signature. This lack of perfect non-repudiation makes pure IBC problematic for enterprise cloud storage or legal signatures.

To eliminate key escrow without reintroducing digital certificates, researchers developed Certificateless Public Key Cryptography (CL-PKC).

Instead of a single entity generating the private key, the responsibility is split between a trusted third party—the Key Generation Center (KGC)—and the user:

  1. The KGC uses its master secret key and the user's identity to generate a partial private key.
  2. The user independently generates a secret value that is never shared with anyone.
  3. The user combines the KGC's partial private key and their own secret value to produce their actual full private key.
  4. The user's public key is then computed from their secret value and the KGC's public parameters.
KGC Master Secret + Identity -------> [Partial Private Key] \
                                                             + ---> [Full Private Key]
User-Generated Secret Value --------> [Secret Value]        /

Because the KGC never learns the user's independent secret value, it cannot compromise or impersonate the user, successfully eliminating the key escrow flaw. Crucially, because the public key is still mathematically bound to the user's identity via the KGC's partial key parameters, external verifiers still do not require a digital certificate to trust the key.

Shengbao Wang et al. demonstrated the utility of this approach in Efficient Certificateless Authentication and Key Agreement (CL-AK) for Grid Computing, showing that certificateless systems allow dynamic, decentralized nodes to establish secure sessions rapidly without the administrative weight of a traditional certificate authority or the privacy risks of escrowed keys.

Optimizing for the Edge: Signcryption and Post-Quantum Adaptation

Eliminating certificates shifts the computational burden away from network transmission and certificate parsing toward more complex mathematical operations (such as bilinear pairings). To make certificate-free cryptography viable for ultra-low-power hardware, the field has evolved along several optimization vectors:

Signcryption

Traditionally, securing a message requires two distinct steps: signing the message for authenticity, and then encrypting it for confidentiality. Identity-Based Signcryption (IDSC) merges these operations into a single mathematical step. As surveyed by Gaurav Sharma et al. in A Computational Review of Identity-based Signcryption Schemes, signcryption significantly lowers computational overhead. Building on this, Caixue Zhou et al. introduced a generalized proxy signcryption scheme in A Provable Secure Identity-based Generalized Proxy Signcryption Scheme that allows resource-constrained systems to handle multiple cryptographic tasks using a single key pair.

Server-Aided Verification

For edge devices that cannot afford the mathematical cost of verifying identity-based signatures, operations can be securely offloaded. In Identity-Based Signature With Server-Aided Verification Scheme for 5G Mobile Systems, Mohammed Ramadan et al. designed a protocol where a mobile device offloads more than 50% of the signature verification workload to an edge server without revealing the underlying data or compromising security.

Post-Quantum Resilience

As quantum computing threatens traditional algebraic assumptions like bilinear pairings, researchers are adapting certificate-free schemes to lattice-based mathematics. For instance, Yang Yang et al. developed post-quantum data integrity auditing protocols using the Ring Learning With Errors (RLWE) assumption in RLWE-Based ID-DIA Protocols for Cloud Storage. To protect medical hardware, Bin Xiao et al. proposed Efficient and Secure Post-Quantum Certificateless Signcryption for Internet of Medical Things, achieving up to a 70% reduction in computational overhead compared to baseline post-quantum methods.

By replacing explicit, third-party digital certificates with implicit mathematical bindings derived from identities and split-key generation, these architectures allow modern networks to scale efficiently, shedding the administrative and computational weight of legacy PKI.

Key Foundational Work

Two Improved Partially Blind Signature Schemes from Bilinear Pairings (2004) — contributed 1 concept elements to this direction.
A Provably Secure Nyberg-Rueppel Signature Variant with Applications (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_certificate_management_overhead_3f649522,
  title = {certificate management overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/certificate-management-overhead/rdr_3f6495221e514dbe98ad570ef16d9aaf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_certificate_management_overhead_3f649522_v1,
  title = {certificate management overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/certificate-management-overhead/rdr_3f6495221e514dbe98ad570ef16d9aaf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake