Written by Noemi Glaeser, a16z crypto

Written by: Chris, Techub News

In public key cryptography, there has always been a difficult problem, which is how to correctly associate a cryptographic key (such as a public key) with a specific identity (such as a person or organization). The key to this problem is to have a public and consistent way to show the relationship between the identity and the public key so that everyone can use these public keys to encrypt information with confidence.

Without such a clear relationship, others may not be able to determine who a public key belongs to, which may lead to sending encrypted information to the wrong person, resulting in information leakage or other serious consequences. In Web3, this problem still exists.

There are currently three solutions to the above problems: Public Key Directory, Identity-Based Encryption (IBE), and Registration-Based Encryption (RBE). These three methods have their own advantages in anonymity, interactivity, and efficiency. For example, IBE requires a strong trust foundation, but in some cases, IBE performs better in anonymity and efficiency. This article aims to explore the application of these three methods on blockchain and compare their advantages and disadvantages.

Three methods

Generally speaking, the common way to associate encryption keys with identity information is to use a public key infrastructure (PKI), the core of which is a public key directory. In this method, the person sending the information needs to interact with a trusted third party (the organization that maintains this directory, usually a certificate authority) in order to send encrypted information.

However, in the Web2 environment, maintaining this public key directory requires high costs and cumbersome operations. In addition, users are also faced with the risk that certificate authorities may abuse their power.

Cryptographers have proposed some alternatives to solve the problems of public key infrastructure (PKI). In 1984, Adi Shamir proposed identity-based encryption (IBE), in which a party's identity (such as a phone number, email, or ENS domain name) can be used directly as a public key. This approach eliminates the need to maintain a public key directory, but introduces a new problem: it is necessary to rely on a trusted third party (key generator) to generate private keys.

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 some closed ecosystems, such as enterprise or government deployment environments. One of the reasons why IBE is not widely used may be that it relies on a strong trust assumption, that is, trusting the keys generated by a third party.

However, as will be discussed later in this article, this trust issue can be resolved by relying on a trusted multi-party (i.e. a quorum of a group of participants), which can be easily achieved with blockchain technology.

Advantages and Disadvantages

There are many different factors to consider when comparing these encryption schemes, and I make two assumptions:

Users do not update or revoke their keys: This means that the discussion assumes that each user's key is fixed and does not change.

Smart contracts do not use any off-chain data availability services (DAS) or blob data: that is, it is assumed that smart contracts rely entirely on on-chain data and do not involve off-chain data services or additional data storage.

Public Key Directory

Anyone can add an ID (id, pk) entry that is not occupied by anyone else to the on-chain directory by calling a smart contract.

A decentralized PKI is a smart contract that maintains a directory of identities (IDs) and their corresponding public keys. This directory is public and does not rely on a centralized third party. For example, ENS maintains a mapping between a domain name (i.e., identity) and related metadata, including the addresses resolved by the domain name (the public key can be derived from the transactions of these addresses). ENS is a more complex system that not only records public keys, but also stores other metadata. The function of a decentralized PKI is relatively simple: the smart contract only needs to maintain a list of the public keys corresponding to each identity.

When a user wants to register an identity, they first need to generate a pair of keys (public and private), or use an already generated key pair and send their identity ID and public key to the smart contract (possibly paying a fee). The smart contract will check if the ID has been registered by someone else. If it is not occupied, the smart contract will add the ID and public key to the directory. Once registered, anyone can ask the smart contract to get the public key corresponding to a certain ID in order to encrypt and send a message to that user. If the sender has encrypted a message to this user before and already has the public key of the user, there is no need to request the public key from the smart contract again. With the public key, the sender can use it to encrypt a message as usual, and then send the encrypted message to the receiver, who uses the corresponding private key to decrypt the message and restore the original text.

Let’s look at the pros and cons of this approach:

Identity-Based Encryption (IBE)

The identity of the user is represented by their public key, that is, the public key is not only used for encryption, but also as a unique identifier for the user. However, this method requires relying on one or more trusted third parties who are responsible for generating and issuing keys. In addition, these third parties also need to keep a master key throughout the life cycle of the system, which may be used for decryption or other important operations in some cases.

In the IBE system, users do not generate a pair of public and private keys themselves as in traditional encryption systems. Instead, users need to register with a trusted key generator. The key generator has a pair of master keys (including the master private key msk and the master public key mpk). When the user provides his or her ID, the key generator uses the master private key msk and the user's ID to calculate a private key that belongs exclusively to the user. The generated private key needs to be delivered to the user through a secure channel, and generally a key exchange protocol is used to establish this 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 key generator once, and then can use the ID to encrypt the message. For the receiver, decryption is also simple. Registered users can use the private key sent to them by the key generator to decrypt the received ciphertext.

The master private key (msk) of the key generator must be retained for a long time because it is needed to continuously generate new user private keys during the operation of the system. This is different from some SNARK systems, which are generated during the trusted setup process but can be destroyed after the setup is completed. In the IBE system, the master private key cannot be deleted after initialization like in SNARK.

Even if the master private key (msk) is properly kept, each registered user still needs to trust the key generator not to read their messages. This is because the key generator can always save a copy of the user's private key, or use the master private key to recalculate the user's private key.

The key generator may also provide the user with a problematic or limited private key, which can decrypt most messages but cannot decrypt certain messages set by the key generator. This means that the key generator has the ability to manipulate the user's decryption ability, and thus may be able to control or restrict the user's communications to a certain extent.

Registration-Based Encryption (RBE)

Like IBE, in this system, a user's identity (e.g., email address or phone number) directly acts as their public key. But unlike IBE, this system no longer relies on a trusted third party or a quorum to manage keys. Instead, this trusted third party is replaced by a key curator.

I will discuss an efficient way of constructing RBE in this part because as far as I know this has a significant advantage over other practical RBE constructs, it can be deployed on the blockchain because it is pairing-based, Rather than lattice-based.

In the RBE system, each user generates a pair of keys (including a public key and a private key) for himself. Users also need to calculate some update values ​​(marked as a in the figure) based on their private keys and a public reference string (CRS). These update values ​​are used for further operations in the system. The existence of the public reference string (CRS) means that the system is not completely trustless. However, the generation process of CRS uses a construction method called the power of tau. This construction method can be completed on the chain through collaborative calculations by multiple participants. As long as at least one participant is honest, this CRS is safe.

The smart contract is set up for the expected number of users N, who are grouped into different buckets. When a user registers in the system, he needs to send his identity ID, public key, and update value to the smart contract. The smart contract maintains a set of public parameters pp, which are different from the public reference string (CRS) mentioned above. pp can be understood as a concise summary of the public keys of all registered users in the system. After the smart contract receives the user's registration request, it checks the update values ​​to verify their correctness. Once verified, the smart contract multiplies the user's public key into the corresponding buckets in pp. This step is equivalent to incorporating the new user's public key into the system's public parameter set for subsequent operations.

In a registration-based encryption (RBE) system, users need to keep some information locally that helps them decrypt messages. This information needs to be updated when new users register to the same group as them. Users can monitor the blockchain themselves to manually update this information, or smart contracts can provide information about recently registered users, and users can get these updates regularly to keep their decryption information up to date.

In this system, the sender only needs to do two things:

Download the Common Reference String (CRS): This only needs to be downloaded once and does not need to be updated afterwards.

Download public parameters: The sender needs to occasionally download the latest public parameters. For the sender, it is important that these public parameters contain the receiver's public key, and it is not necessary to download the latest version every time, as long as the receiver's public key can be found.

The sender can then use the downloaded CRS, public parameters, and the recipient's ID to encrypt the message and send it to the recipient. This means that the sender does not need to update the data frequently, as long as it ensures that the public parameters contain the recipient's public key.

When a user receives an encrypted message, they first check their locally stored auxiliary information to see if there is a value that meets a certain condition (such as a value that passes a certain validation check). If the user cannot find a matching value locally, this means they need to get the latest updated information from the smart contract. Once the user finds the appropriate auxiliary information value, they can use this value and their private key to decrypt the received ciphertext and recover the original message.

Obviously, this scheme is more complicated than the other two. But it requires less on-chain storage than the public key directory and avoids the strong trust assumption of IBE.

Concise parameters:

The size of the parameters stored on-chain grows sublinearly with the number of users, which is much smaller than the storage required for the public key directory (linear growth), but still not a constant, so it is inferior to the IBE (identity-based encryption) system in this respect.

Somewhat interactive encryption:

When sending a message, the sender needs a copy of the public parameters that contain the intended recipient. This means that the sender needs to update these parameters at some point after the recipient registers, but does not need to update them separately for each recipient, as a single update may contain the keys of multiple recipients. Overall, message sending is more interactive than IBE, but less than using a public key directory.

Decryption with some interactivity:

Similar to encryption, the recipient needs a copy of the auxiliary information that matches the version of the public parameters used during encryption. When a new user registers in a group, the public parameters and auxiliary information are updated, and the value that can decrypt the ciphertext corresponds to the version of the public parameters used during encryption. Users can choose to get auxiliary information updates periodically, rather than immediately every time, unless decryption fails. Unlike public parameter updates, getting auxiliary information updates more frequently does not leak private information.

Sender Anonymous:

Similar to the case of the public key directory, the sender can encrypt messages independently (as long as it has the latest parameters) without having to query specific information about the receiver. When the sender needs to read information from the chain, this information has nothing to do with the intended receiver (unless the sender only requests a certain set of parameter scores, which may leak some information).

Transparency:

Although the system needs to be set up via a trusted setup (which may be distributed or externally managed) and outputs a modified CRS (public reference string), once it is set up it no longer relies on any trusted third party or arbitration group. Although it relies on a coordinating third party (smart contract), the system is completely transparent and anyone can act as a coordinator or check that it is operating honestly by verifying state transitions (which is why it can be implemented as a smart contract). In addition, users can ask for a concise (non-)membership proof to check whether themselves or others are registered in the system. This is different from IBE systems, where it is difficult for a trusted third party to prove that they have not secretly leaked the decryption key (such as saving a secret copy or leaking it to others). In contrast, public key directories are completely transparent.

Restricted set of IDs:

A basic version of the RBE construction is described here. In order to transparently determine which group an ID belongs to, the IDs must have a common and deterministic order. Phone numbers can be sorted trivially, but sorting arbitrary strings can be very complex or even impossible because the number of groups may be very large or infinite. This complexity can be mitigated by providing a separate contract to compute this mapping, or by adopting the cuckoo-hashing approach proposed in subsequent work.

Recipient Anonymous:

This method ensures that the ciphertext does not reveal the identity of the recipient.