Source: Noemi Glaeser, a16z crypto
In Public KeyCryptography, there has always been a challenge of how to correctly associate the encrypted keys (such as Public Key) with a specific identity (such as an individual or organization). The key to this problem is to have a public and consistent way to display the relationship between identity and Public Key, so that everyone can confidently use these Public Keys to encrypt information.
If there is no such clear relationship, others may not be able to determine who a Public Key belongs to, which may result in sending encryption information to the wrong person, leading to information leakage or other serious consequences. In Web3, this problem still exists.
For the above issues, there are currently three solutions: Public Key Directory, Identity-Based Encryption (IBE), and Registration-Based Encryption (RBE). These three methods have their own advantages in terms of Anonymity, interactivity, and efficiency. For example, IBE requires a strong trust foundation, but in some cases, it performs better in terms of Anonymity and efficiency. This article aims to explore the applications of these three methods in on-chain Block and compare their advantages and disadvantages.
Three methods
In general, the common method of associating encryption Secret Key with identity information is to use Public Key Infrastructure (PKI), where the core part is a Public Key directory. In this method, the sender needs to interact with a trusted third party (i.e., the institution maintaining this directory, usually a Certificate Authority) in order to send encryption information.
However, maintaining this Public Key directory in the Web2 environment requires high costs and tedious operations. In addition, users also face the risk of certificate authorities abusing their power.
Some alternative solutions proposed by cryptographers to address the issues with Public Key infrastructure (PKI). In 1984, Adi Shamir proposed identity-based encryption (IBE), where one’s identity (such as a phone number, email, or ENS domain) can be directly used as the Public Key. This method eliminates the need to maintain a Public Key directory, but introduces a new issue: reliance on a trusted third party (Secret Key generator) to generate the Private Key.
In 2001, Dan Boneh and Matthew Franklin proposed the first practical IBE construction, but this technology has not been widely adopted and is mainly used in closed ecosystems, such as enterprise or government deployment environments. One reason why IBE is not widely used may be that it relies on a strong trust assumption, that is, trust in a third party to generate the Secret Key.
However, as will be discussed later in this article, this trust issue can be resolved by relying on a trusted longer (i.e., a legally required number of participants), and blockchain technology can easily achieve this.
Advantages and disadvantages
When comparing these encryption schemes, many different factors need to be considered, and I make two assumptions about this:
Users will not update or revoke their Secret Key: This means assuming that each user’s Secret Key is fixed and will not change in the discussion.
Smart contracts do not use any off-chain data availability services (DAS) or blob data. That is to say, assuming that smart contracts rely entirely on on-chain data, without involving off-chain data services or additional data storage.
![]()
Public Key Directory
Anyone can add an unoccupied ID, i.e. (id, pk) entry, to the on-chain directory by calling Smart Contract.
![]()
The PKI of Decentralization refers to maintaining a directory of identities (IDs) and their corresponding Public Keys through Smart Contracts. This directory is public and does not rely on a centralized third party. For example, take ENS, which maintains a mapping of a domain name (i.e., identity) to relevant Metadata, including the Address resolved by the domain name (from the transactions of these Addresses, the Public Key can be derived). ENS is a more complex system, not only recording Public Keys, but also storing other Metadata. The function of Decentralization’s PKI is relatively simple: Smart Contracts only need to maintain a list, recording the Public Key corresponding to each identity.
When a user wants to register an identity, they first need to generate a pair of Secret Key (Public Key and Private Key), or use the already generated Secret Key, to send their identity ID and Public Key to the Smart Contract (possibly also paying a certain fee). The Smart Contract will check if this ID has been registered by someone else. If it is not taken, the Smart Contract will add this ID and Public Key to the directory. Once registered, anyone can query the Smart Contract to obtain the Public Key corresponding to a certain ID, in order to encrypt and send messages to the user. If the sender has previously encrypted messages to this user and already has the user’s Public Key, they do not need to request the Public Key from the Smart Contract again. With the Public Key, the sender can use it as usual to encrypt messages, and then send the encrypted message to the recipient, who uses the corresponding Private Key to decrypt the message and restore the original text.
Let’s take a look at the advantages and disadvantages of this method:
Pros and cons of non-interactive decryption: The decryption process does not require interaction with other parties, and the decryptor can complete the decryption independently. Not succinct: The system may not be concise in certain aspects, which may imply higher complexity, larger data volume, or the need for more resources. Transparency: The system may be transparent in certain aspects, meaning that operations are open and can be audited. Interactive encryption: The encryption process may require certain interactions with other parties, adding complexity. Arbitrary ID: Users can freely choose or use arbitrary identity IDs without being restricted by specific formats or rules. Non-anonymous sender: The identity of the sender may not be completely anonymous in the system.
Identity-based encryption (IBE)
The user’s identity is represented by their Public Key, which means that the Public Key is not only used for encryption, but also serves as the unique identifier for the user. However, this method relies on one or more trusted third parties, which are responsible for generating and issuing the Secret Key. In addition, these third parties need to keep a master Secret Key throughout the entire lifecycle of the system, which may be used for decryption or other important operations in certain circumstances.
![]()
In the IBE system, users do not generate a pair of Public Key and Private Key like in traditional encryption systems. Instead, users need to register with a trusted Secret Key generator. The Secret Key generator has a pair of master Secret Key (including master Private Key msk and master Public Key mpk). When a user provides their ID, the Secret Key generator uses the master Private Key msk and the user’s ID to calculate a Private Key exclusively for that user. The generated Private Key needs to be transmitted to the user through a secure channel, usually by using a Secret Key exchange protocol to establish the secure channel.
For the sender, the IBE system simplifies the encryption process. The sender only needs to download the master Public Key (mpk) of the Secret Key generator once, and then they can use the ID to encrypt the message. For the receiver, decryption is also straightforward. Registered users can use the Private Key generated by the Secret Key generator to decrypt the received Ciphertext.
The main Private Key (msk) of the key generator must be kept for a long time, as it needs to continuously generate new user Private Keys during the system’s operation. This is different from some SNARK systems, where the latter is generated during the trusted setup process, but can be destroyed after the setup is completed. In the IBE system, the main Private Key cannot be deleted after initialization like in SNARK.
Even if the main Private Key (msk) is well kept, each registered user still needs to trust that the key generator will not read their messages. This is because the key generator can always save a copy of the user’s Private Key, or use the main Private Key to recalculate the user’s Private Key.
The Secret Key generator may also provide users with a flawed or restricted Private Key, which can decrypt most messages but not certain specific messages set by the Secret Key generator. This means that the Secret Key generator has the ability to manipulate the user’s decryption capabilities, potentially exerting a certain degree of control or restriction over the user’s communication.
Advantages and disadvantages of on-chain storage: The amount of storage required by the system on the block on-chain is small or constant and does not increase over time. Strong trust assumption: The system relies on one or more trusted third parties, which means there needs to be a strong trust in these third parties. If these third parties are compromised or unreliable, the security of the system is threatened. Non-interactive encryption: The encryption process does not require interaction with other parties, and the sender can complete the encryption independently. Sender anonymity: The system can keep the identity of the sender anonymous, protecting privacy. Arbitrary ID: Users can freely choose or use any identity ID without being limited by specific formats or rules.
Based on Registered encryption (RBE)
Like IBE, in this system, the user’s identity (e.g. email Address or phone number) directly serves as their Public Key. But unlike IBE, this system no longer relies on a trusted third party or a quorum to manage Secret Key. Instead, this trusted third party is replaced by a key curator.
In this section, I will discuss an efficient way to construct an RBE, which, as far as I know, has a significant advantage compared to other practical RBE constructions. It can be deployed on-chain in Block because it is pairing-based rather than lattice-based.
![]()
In the RBE system, each user generates their own pair of Secret Keys (including Public Key and Private Key). Users also need to calculate some update values (marked as a in the diagram) based on their Private Key and a common reference string (CRS). These update values are used for further operations in the system. The existence of the common reference string (CRS) means that the system’s setup is not completely trustless. However, the generation process of the CRS uses a construction method called tau powers. This construction method can be completed on-chain through the collaboration of multiple participants. As long as at least one participant is honest, this CRS is secure.
The Smart Contract sets up the expected number of users N, grouping these users into different buckets. When a user registers in the system, they need to send their identity ID, Public Key, and update value to the Smart Contract. The Smart Contract maintains a set of common parameters pp, which are different from the common reference strings (CRS) mentioned earlier. pp can be understood as a concise summary of the Public Keys of all registered users in the system. After receiving the user’s registration request, the Smart Contract will check the update values to verify their correctness. Once verified, the Smart Contract will multiply the user’s Public Key into the corresponding buckets in pp. This step is equivalent to incorporating the user’s Public Key into the common parameter set of the system for later use.
In the registration-based encryption (RBE) system, users need to keep some information locally to help them decrypt messages. When new users register with the same group, this information needs to be updated. Users can manually monitor the blockchain to update this information, or smart contracts can provide information on the most recent registrations, allowing users to regularly obtain these updates to keep their decryption information up to date.
In this system, the sender only needs to do two things:
Download Common Reference String (CRS): This only needs to be downloaded once and does not need to be updated again.
Download public parameters: senders need to occasionally download the latest public parameters. For senders, it is important that these public parameters contain the recipient’s Public Key, and they do not need to download the latest version every time, as long as they can find the recipient’s Public Key.
Then, the sender can encrypt the message and send it to the recipient using the downloaded CRS, public parameters, and the recipient’s identity ID. This means that the sender does not need to update the data frequently, just ensure that the recipient’s public key is in the public parameters.
When a user receives an encryption message, they will first check the auxiliary information stored locally to see if there is a value that meets certain conditions (such as a value that has passed a verification check). If the user cannot find a value that meets the conditions locally, it means they need to obtain the latest updated information from the Smart Contract. Once the user finds a suitable value of auxiliary information, they can use this value and their own Private Key to decrypt the received Ciphertext and restore the original message.
Obviously, this solution is more complex than the other two. But it requires less on-chain storage than the Public Key directory and avoids the strong trust assumption of IBE.
Simple parameters:
- The relationship between the size of parameters stored on-chain and the number of users is sub-linear, which is much smaller than the storage required for the Public Key directory (linear rise), but still not constant, so it is not as good as the IBE (Identity-Based Encryption) system at this point.
encryption with a certain degree of interactivity:
- When sending a message, the sender needs a copy of public parameters that includes the target recipient. This means that the sender needs to update these parameters at some point after the recipient’s registration, but does not need to update them separately for each recipient, because one update may include the Secret Key of multiple recipients. Overall, the interaction of message sending is more than IBE, but less than using the Public Key directory.
Interactive decryption:
- Similar to encryption, the recipient needs auxiliary information that matches the public parameter version used during encryption. When a new user registers in a certain group, the public parameters and auxiliary information will be updated, allowing the decryption of the Ciphertext corresponding to the public parameter version used during encryption. Users can choose to regularly obtain auxiliary information updates instead of updating immediately every time, unless decryption fails. Unlike public parameter updates, more frequent auxiliary information updates will not leak privacy information.
Sender anonymous:
- Similar to the situation with the Public Key directory, the sender can independently encrypt messages (as long as it has the latest parameters) without needing to query specific information related to the recipient. When the sender needs to read information from the on-chain, this information is unrelated to the target recipient (unless the sender only requests a specific parameter to be grouped, but this may leak partial information).
Transparency:
- Although the system needs to be set up through a trust setup (possibly distributed or externally managed) and outputs a corrected CRS (Common Reference String), once set up, it no longer relies on any trusted third party or arbitration group. While it relies on a coordinating third party (Smart Contract), the system is fully transparent, and anyone can act as a coordinator or check its honest operation by verifying state transitions (which is also why it can be implemented as a Smart Contract). In addition, users can request a concise (non) membership proof to check whether they or others are registered in the system. This is different from IBE systems, where it is difficult for trusted third parties to prove that they have not secretly disclosed the decryption Secret Key (such as keeping a secret copy or disclosing it to others). In contrast, the Public Key directory is fully transparent.
Restricted set of IDs:
- This describes the basic version constructed by RBE. In order to transparently determine the group to which an ID belongs, the ID must have a common and definite order. Phone numbers can be simply sorted, but sorting any string may be very complex or even impossible, because the number of groups may be very large or infinite. This can be mitigated by providing a separate contract to calculate this mapping, or by adopting the cuckoo-hashing method proposed in subsequent work.
Recipient anonymous:
- This method can prevent the Ciphertext from leaking the recipient’s identity.
