a16z's three best solutions to solve the core problems of public key cryptography

Source: Noemi Glaeser, a16z crypto

In public key cryptography, there has always been a difficult problem, that 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 an open and consistent way to show the relationship between identity and 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 cause encrypted information to be sent to the wrong person, resulting in information leakage or other serious consequences. In Web3, this problem still exists.

For the above problems, 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 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

In general, the common method of associating encryption keys with identity information is to use a public key infrastructure (PKI), in which the core part is a public key directory. In this method, the person sending the information needs to interact with a trusted third party (i.e., 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 of possible abuse of power by certificate authorities.

Some alternatives proposed by cryptographers 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 directly used as a public key. This approach eliminates the need to maintain a public key directory, but introduces a new problem: having 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 requires relying on a strong trust assumption, that is, trusting the keys generated by the third party.

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

Advantages and Disadvantages

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

Users will not update or revoke their keys: This means that in this discussion it is assumed that each user's key is fixed and will not change.

Smart contracts do not use any off-chain data availability services (DAS) or blob data: In other words, 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 that is not occupied by others, that is, an (id, pk) entry, to the on-chain directory by calling a smart contract.

Decentralized PKI refers to the use of smart contracts to maintain an identity (ID) and its corresponding public key directory. This directory is public and does not rely on a centralized third party. For example, in the case of ENS, it maintains a mapping between a domain name (i.e., an 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, he first needs to generate a pair of keys (public and private keys), or use an already generated key pair and send his identity ID and public key to the smart contract (possibly paying a fee). The smart contract will check whether 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 obtain the public key corresponding to a certain ID by asking the smart contract to encrypt and send a message to the user. If the sender has encrypted a message to the user before and already has the user's public key, 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 advantages and disadvantages of this method:

AdvantagesDisadvantagesNon-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 succinct in some aspects, which may mean higher complexity, larger data volume, or more resources. Transparency: The system may be transparent in some aspects, meaning that the operation is public and can be reviewed. Interactive encryption: The encryption process may require some interaction with other parties, which increases complexity. Arbitrary ID: Users are free to choose or use any identity ID without being restricted by a specific format or rules. Sender non-anonymity: The sender's identity may not remain completely anonymous in the system.

Identity-based encryption (IBE)

The identity of a 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 reliance on one or more trusted third parties who are responsible for generating and issuing keys. In addition, these third parties are required 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 an 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 a master private key msk and a 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 is exclusive to the user. The generated private key needs to be passed to the user through a secure channel, which is generally established using a key exchange protocol.

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 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 needs 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 as 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 keep a copy of the user's private key at any time, or use the master private key to recalculate the user's private key.

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

Advantages Disadvantages Constant/minimal storage on the chain: The amount of storage required by the system on the blockchain is small or constant and will not increase over time. Strong trust assumption: The system relies on one or more trusted third parties, which means that there needs to be strong trust in these third parties. If these third parties are damaged or unreliable, the security of the system will be 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 sender's identity anonymous and protect privacy. Arbitrary ID: Users are free to choose or use any identity ID, not restricted by a specific format or rules.

Registration-based Encryption (RBE)

Like IBE, in this system, the user's identity (such as an 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 RBE construction in this section because, as far as I know, this has a significant advantage over other practical RBE constructions in that 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 public and private keys) 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 updated 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 save some information locally that helps them decrypt messages. This information needs to be updated when a new user is registered to the same group as them. Users can monitor the blockchain themselves to manually update this information, or the smart contract can provide information about recently registered users, and users can obtain 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 the Public Parameters: The sender needs to occasionally download the latest public parameters. What is important to the sender is 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.

Then, the sender uses the downloaded CRS, public parameters, and the receiver's identity ID to encrypt the message and send it to the receiver. This means that the sender does not need to update the data frequently, as long as it ensures that the public parameters contain the receiver'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 verification check). If the user cannot find a value that meets the condition locally, it means that they need to get the latest updated information from the smart contract. Once the user finds a suitable 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 schemes. But it requires less on-chain storage than the public key directory and avoids the strong trust assumption of IBE.

Simple parameters:

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

Encryption with some interactivity:

• When sending a message, the sender needs a copy of the public parameters for 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 individually for each recipient, as a single update may contain the keys of multiple recipients. Overall, message sending is more interactive than IBE, but less interactive 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 when encrypting. 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 when encrypting. Users can choose to get auxiliary information updates periodically, rather than immediately every time unless decryption fails. Unlike public parameter updates, getting side information updates more frequently does not leak private information.

Sender Anonymity:

• Similar to the case of a public key directory, a 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 is irrelevant to the intended receiver (unless the sender only requests a specific set of parameter scores, which may leak some information).

Transparency:

• Although the system needs to be set up through 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 contracts), 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 succinct proof of (non-)membership 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:

• Here is described a basic version of the RBE construction. In order to transparently determine which group an ID belongs to, the IDs must have a public 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 can be very large or infinite. This complexity can be mitigated by providing a separate contract to compute this mapping, or by using the cuckoo-hashing method proposed in subsequent work.

Recipient anonymity:

• This method allows the ciphertext to not reveal the identity of the recipient.