a16z: Three Preferred Approaches to Solving the Core Challenge of Public-Key Cryptography
TechFlow Selected TechFlow Selected
a16z: Three Preferred Approaches to Solving the Core Challenge of Public-Key Cryptography
Currently, there are three solutions: Public Key Directory, Identity-Based Encryption (IBE), and Registration-Based Encryption (RBE).
Navigating Web3 tides with focused insightsAuthor: Noemi Glaeser, a16z crypto
Author: Chris, Techub News
In public-key cryptography, there has long been a challenge: how to correctly associate an encryption key (such as a public key) with a specific identity (e.g., a person or organization). The crux lies in having a public and consistent way to demonstrate the relationship between identities and public keys, so users can confidently use these public keys for encrypting messages.
Without such clear associations, it may be impossible to verify which individual owns a given public key, risking encrypted messages being sent to the wrong party—potentially leading to data leaks or other serious consequences. This issue persists in Web3.
Currently, three solutions address this problem: Public Key Directory, Identity-Based Encryption (IBE), and Registration-Based Encryption (RBE). These approaches differ in their trade-offs regarding anonymity, interactivity, and efficiency. For instance, IBE requires strong trust assumptions but excels in certain scenarios in terms of anonymity and efficiency. This article explores the applications of these three methods on blockchains and compares their respective advantages and disadvantages.
The Three Approaches
Typically, associating cryptographic keys with identity information involves using Public Key Infrastructure (PKI), whose core component is a public key directory. In this model, senders must interact with a trusted third party—the entity maintaining the directory, usually a Certificate Authority (CA)—to securely transmit encrypted messages.
However, in Web2 environments, maintaining such directories incurs high costs and operational complexity. Additionally, users face risks associated with potential abuse of power by certificate authorities.
Cryptographers have proposed alternative schemes to overcome limitations of traditional PKI. In 1984, Adi Shamir introduced Identity-Based Encryption (IBE), where an entity's identifier (e.g., phone number, email address, or ENS domain) serves directly as its public key. This eliminates the need for a public key directory, but introduces a new requirement: reliance on a trusted third party (a key generator) responsible for generating private keys.
In 2001, Dan Boneh and Matthew Franklin presented the first practical construction of IBE. However, the technology has not seen widespread adoption and remains primarily confined to closed ecosystems such as enterprise or government deployments. One reason for limited adoption may be the strong trust assumption required—that users must trust the third party handling key generation.
As discussed later in this article, this trust issue can be mitigated by relying on a trusted multi-party setup (i.e., a quorum of participants), which blockchain technology can facilitate effectively.
Advantages and Disadvantages
When comparing these cryptographic schemes, various factors must be considered. We make two simplifying assumptions:
Users do not update or revoke their keys: That is, we assume each user’s key remains fixed throughout the discussion.
Smart contracts do not use off-chain data availability services (DAS) or blob data: That is, smart contracts rely entirely on on-chain data without involving external data storage or services.
Public Key Directory
Anyone can call a smart contract to register an unused ID—specifically, a (id, pk) entry—onto a blockchain-based directory.
Decentralized PKI refers to maintaining a mapping between identities (IDs) and their corresponding public keys via smart contracts. This directory is publicly accessible and does not depend on centralized intermediaries. For example, ENS maintains a mapping between domain names (identities) and associated metadata—including wallet addresses that resolve from those domains (from which public keys can be derived through transaction analysis). While ENS is a more complex system storing various types of metadata beyond just public keys, decentralized PKI aims for simplicity: a smart contract merely maintains a list linking each identity to its public key.
When a user wishes to register an identity, they first generate a key pair (public and private keys), or use an existing one, then submit their identity ID along with the public key to the smart contract (possibly paying a fee). The smart contract checks whether the ID has already been registered. If not, it adds the ID–public key mapping to the directory. Once registered, anyone can query the smart contract to retrieve the public key associated with a given ID and use it to encrypt messages destined for that user. If the sender previously communicated with the recipient and already possesses their public key, no additional lookup is needed. With the public key obtained, the sender encrypts the message normally and sends the ciphertext to the recipient, who uses their private key to decrypt and recover the original plaintext.
Let us now examine the strengths and weaknesses of this approach:
Identity-Based Encryption (IBE)
A user’s identity is represented by their public key—meaning the public key functions both as an encryption tool and a unique identifier. However, this method depends on one or more trusted third parties responsible for generating and distributing keys. Moreover, these entities must retain a master secret key throughout the system’s lifetime, which could potentially be used to decrypt communications or perform other critical operations.
In an IBE system, users do not generate their own key pairs as in traditional systems. Instead, users register with a trusted key generator, which holds a master key pair (master secret key msk and master public key mpk). Upon receiving a user’s ID, the key generator computes a private key specific to that user using the msk and the provided ID. The resulting private key must be securely transmitted to the user, typically via a secure key exchange protocol.
For senders, IBE simplifies encryption. After downloading the key generator’s mpk once, senders can encrypt messages directly using any recipient’s ID. Recipients simply use the private key issued by the key generator to decrypt incoming ciphertexts.
The key generator’s master secret key (msk) must be preserved indefinitely because it is continuously required to generate new user private keys. Unlike some SNARK systems—where the trusted setup generates parameters that can be discarded afterward—the msk in IBE cannot be destroyed after initialization.
Even if properly safeguarded, every registered user must still trust the key generator not to read their messages. The key generator could retain copies of user private keys or recompute them at any time using the msk.
Furthermore, the key generator might issue compromised or restricted private keys—keys capable of decrypting most messages but failing on certain specially crafted ciphertexts predetermined by the key generator. This gives the key generator potential control over users’ decryption capabilities, enabling selective surveillance or censorship.
Registration-Based Encryption (RBE)
Like IBE, in this system a user’s identity (e.g., email address or phone number) acts directly as their public key. But unlike IBE, RBE does not rely on a single trusted third party or a quorum. Instead, the role of the trusted party is replaced by a "key curator."
This section discusses an efficient RBE construction, which—as far as we know—offers a significant advantage over other practical RBE constructions: it can be deployed on blockchains due to being pairing-based rather than lattice-based.
In an RBE system, each user generates their own key pair (public and private keys). They also compute certain update values (labeled 'a' in the diagram) based on their private key and a common reference string (CRS). These updates are used in subsequent system operations. The existence of the CRS implies that the setup is not fully trustless. However, the CRS is generated using a "powers-of-tau" ceremony—a process that can be collaboratively computed on-chain by multiple participants. As long as at least one participant behaves honestly, the resulting CRS is secure.
A smart contract sets up the system for a pre-determined number of users N, grouping them into buckets. When registering, a user submits their identity ID, public key, and update value to the smart contract. The contract maintains a set of public parameters pp, distinct from the CRS mentioned earlier. Think of pp as a succinct summary of all registered users’ public keys. Upon receiving a registration request, the smart contract verifies the correctness of the update value. If valid, it incorporates the user’s public key into the appropriate bucket within pp—effectively including the new user’s key in the system’s collective public parameters for future use.
In an RBE system, users must locally store auxiliary information to assist in decryption. This data needs updating whenever another user registers into the same group. Users can either monitor the blockchain themselves to manually update this information, or the smart contract can provide recent registration data, allowing users to periodically fetch updates and keep their decryption materials current.
For senders, only two actions are required:
Download the Common Reference String (CRS): This is a one-time download and never needs refreshing.
Download Public Parameters: Senders occasionally need to obtain updated public parameters. Crucially, they only require a version containing the recipient’s public key—not necessarily the latest version—as long as the target key is present.
With the downloaded CRS, public parameters, and the recipient’s identity ID, senders can encrypt messages and send them directly. Thus, senders are not burdened with frequent updates; they only need assurance that the recipient’s public key exists in the parameters they possess.
Upon receiving an encrypted message, a user first checks their locally stored auxiliary information for a matching value (e.g., one passing a validation check). If no suitable value is found, the user retrieves the latest update from the smart contract. Once the correct auxiliary value is located, the user combines it with their private key to decrypt the ciphertext and recover the original message.
Clearly, this scheme is more complex than the other two. Yet, it requires less on-chain storage than a public key directory and avoids the strong trust assumptions inherent in IBE.
Compact Parameters:
The size of on-chain parameters grows sublinearly with the number of users—significantly smaller than the linear growth required by public key directories. However, it is not constant-sized, so it still falls short of IBE in this regard.
Moderate Interactivity in Encryption:
Senders must possess a copy of the public parameters that includes the intended recipient’s key. This means senders must update their parameters sometime after the recipient registers—but not for each recipient individually, since one update may include many users’ keys. Overall, encryption requires more interaction than IBE but less than querying a full public key directory.
Moderate Interactivity in Decryption:
Similar to encryption, recipients need auxiliary information consistent with the version of public parameters used during encryption. When new users register in a group, both the public parameters and auxiliary information are updated. The values enabling decryption correspond to the parameter version used at encryption time. Users may choose to update their auxiliary data periodically instead of immediately—only doing so when decryption fails. Unlike public parameter updates, frequently fetching auxiliary updates does not compromise privacy.
Sender Anonymity:
As with the public key directory, senders can independently encrypt messages (provided they have up-to-date parameters) without querying recipient-specific data. When reading from the chain, the accessed data is unrelated to the recipient (unless the sender requests a specific parameter shard, which could leak partial information).
Transparency:
Although the system requires a trusted setup (potentially distributed or externally managed) to produce a finalized CRS, once established, it no longer relies on any trusted third party or arbitration group. While coordination depends on a smart contract, the system is fully transparent—anyone can act as coordinator or verify honest execution by checking state transitions (which enables implementation as a smart contract). Furthermore, users can request succinct proofs of (non-)membership to verify whether they or others are registered. This contrasts sharply with IBE, where it is difficult for the trusted authority to prove they haven’t secretly leaked decryption keys (e.g., by retaining hidden copies or sharing them). By comparison, public key directories are fully transparent.
Limited ID Set:
This describes a basic version of RBE. To transparently determine which bucket an ID belongs to, IDs must follow a public and deterministic ordering. Phone numbers can be easily sorted, but arbitrary strings may be extremely complex or even impossible to order—especially when the number of buckets is very large or infinite. This challenge can be mitigated by deploying a separate contract to compute the mapping or adopting cuckoo-hashing techniques proposed in follow-up research.
Recipient Anonymity:
This method ensures ciphertexts do not reveal the recipient’s identity.
Join TechFlow official community to stay tuned
Telegram:https://t.me/TechFlowDaily
X (Twitter):https://x.com/TechFlowPost
X (Twitter) EN:https://x.com/BlockFlow_News
a16z
