NIST Post-Quantum-Cryptography Standardization Process and What it means for Ethereum

Zhenfei Zhang | July 11, 2022

1. Introduction

On July 5, 2022, the US National Institute of Standards and Technology (NIST) announced it will standardize four quantum-safe cryptography algorithms, including

• Kyber, a lattice based public-key encryption (PKE) and key-establishment algorithm,
• Dilithium, a lattice based digital signature scheme,
• Falcon, another lattice based digital signature scheme,
• SPHINCS+, a hash based digital signature scheme.

This semi-concludes a half-decade long search for quantum-safe alternatives to existing public key infrastructure.

1.1 The so-called Quantum Apocalypse

Today, our entire public key infrastructure is built on top of two mathematical problems: integer factorization and discrete logarithm problems. When you open an HTTPS link, it runs the TLS protocol under the hood, which negotiates a session key via the Diffie-Hellman key exchange protocol over a certain elliptic curve group. Another example, a step closer to our blockchain community, when you make an ETH transfer, you sign your transaction with your secret key, using the ECDSA digital signature scheme.

Almost 40 years ago, Peter Shor discovered an algorithm that runs in linear time over a quantum computer, that finds the period of a given function. This result implies that both the integer factorization and the discrete logarithm problems are easy to solve with quantum computers, and hence, eliminate existing PKIs that we are using today.

2. NIST's search for quantum-safe candidates

Although cryptographic research in quantum-safe cryptography is piloted back in 1960s, this space did not receive much attention till the winter of 2016, when NIST, the de facto standard body to make cryptographic standards for almost the entire world, publicly announced its call for proposals for the quantum-safe cryptography solutions for both key establishment and digital signatures. A year later, NIST received 81 submissions from academic thought leaders and industry pioneers, consists of the following 5 categories,

• lattice based cryptography, for both PKEs and signatures;
• code based cryptography, for PKEs;
• multivariate cryptography, for signatures;
• hash based cryptography, for signatures;
• supersingular isogeny cryptography, for PKEs.

The evaluation and cryptanalysis has began since then, with interesting modifications, breaks, fixes, and optimizations. In early 2019 and mid 2020, NIST announced their 2nd and 3rd round picks, reducing candidates from 81 to 26 then to 15. On July 5, 2022, NIST finally concluded the processes and chose to standardize Kyber for key establishment, Dilithium, Falcon and SPHINCS+ for digital signatures.

As NIST remarked in their own report, the security of both Kyber and Dilithium are well understood; they both offer great performance and suit a wide range of applications. Falcon is based on a stronger assumption, and is an alternative to Dilithium in the use cases where signature sizes are sensitive. SPHINCS+ is ideal for users who are conservative in their trust assumptions because SPHINCS+ only relies on hash functions.

3. NIST's next steps

NIST plans to standardize both Kyber and Dilithium first, followed by Falcon and SPHINCS+. Each standard is expected to take roughly one year to complete. Changes in parameters are possible between the final standard and what is submitted to the 3rd round.

In the meantime, note that the selected algorithms are build from lattices and hashes, while it is wise to standardize schemes from various of hardness assumptions, in case of breakthroughs in cryptanalytic research. NIST plans to take further actions in parallel with the standardization effort:

• NIST will started a 4th round, analyzing key establishment schemes from code (BIKE, classic McEliece and HQC) and supersingular isogeny (SIKE);
• NIST will start a call for proposal for post-quantum signature schemes with a preference of neither lattice nor hash based construction.

4. What are the implications for Ethereum

First, it is safe to assume that there does not exist a general purpose quantum computer that is capable of breaking ECC as of today. There are various estimations of when or whether a quantum computer will arrive. This is out of the scope of this blog. Here we assume that we have sufficient time to deploy counter measures.

A natural question is when do we need to be quantum ready? In traditional world, it is advised to be quantum-safe as soon as possible due to the so-called harvest-then-decrypt attacks, where an attacker may collect all the data sent over encrypted channels (for example, over TLS 1.3) and decrypt them when quantum computers become available. In the blockchain world, it becomes more severe if an application is required to store encrypted files on chain. However, for most use cases where cryptography is used for integrity or authenticity, it can wait a bit, since a future quantum attacker cannot come back in time and break the authenticity of today. This gives us some buffer time to study and deploy counter measures.

So, it becomes important to know the building blocks that are potentially vulnerable to quantum computers; and their quantum-safe alternatives.

4.1 Digital Signatures

Ethereum right now use ECDSA for authentication. As stated earlier, this is vulnerable to quantum attackers. We may switch to one of the above three quantum-safe signature schemes. We expect a (significant) decrease of performance due to the large size of signatures and public keys, listed below:

As one can see, the smallest quantum-safe signature scheme requires some 666 bytes for a signature, increased by 10x from 64 bytes as in ECDSA. We do not consider this to be scalable. Active research has been done in this domain to aggregate signatures, either natively or through a quantum-safe snark (more on this later). We may also hope for a new multivariate based signature scheme (which tend to have similar signature size as ECC, albeit a gigantic public key).

4.2 Verkle Tree

Verkle tree is build on top of the Pedersen commitment scheme and Inner Product Arguments (IPAs), which assumes discrete logarithm is hard. There exist quantum-safe alternatives to vector commitments build on top of lattices, but all of the candidates perform a few magnitudes worse than ECC based solutions. Our best candidate thus far is to move back to Merkle Patricia tree that only relies on the hash assumption.

4.3 Zero Knowledge Proofs and their applications

Zero knowledge proofs enable a large number of applications, ranging from private transactions, Verifiable Delay Function, single secret leader selection, zk-rollups, zkEVMs and more. There exist a various flavours of snark systems, split into two categories:

• pairing or elliptic curve based, such as Groth16, vanilla PLONK, Marlin, BulletProof, etc.
• hash based, such as Stark and Plonky2.

The first category will be vulnerable to quantum computers.

Note that there are also lattice based constructions. Despite breakthrough works in the last few years, their performance is still multiple magnitude worse than hash based solutions, as of today.

Here we briefly mention two applications that will be essential for the proof of state consensus. For both applications, switching to a quantum-safe snark system such as Stark or Plonky2 results into solid solutions, although substantial work is needed to concretize the solutions.

Verifiable Delay Function

The beacon chain used in proof of stake will use a snark based VDF for validator and committee selection. The current design is to build it from the Nova proof system which requires the discrete logarithm assumption. Replacing Nova with Stark or Plonky2 may be sufficient. In addition, we may use verifiable random functions, for which there are hash based and lattice based candidates.

Single secret leader selection

Single secret leader selection is used in a proof of stake protocol for block proposer selection. This is still an active research area. The major candidate under examination as of right now is whisk which uses a shuffling approach, and uses an adaptation of the Bayer-Groth protocol to prove shuffling correctness. This protocol relies on pairing and discrete logarithm assumptions. Switching to quantum-safe ZKPs will like decrease performance.

5. Conclusion

NIST's conclusion of its standardization process is our first step entering the quantum-safe world. It gives us semi-satisfactory replacements to the existing public key infrastructure, and implies NIST's strong confidence in hash and lattice based constructions, which will guide us to identify better and more scalable quantum-safe candidates for blockchain cryptography.

Acknowledgement

We would like to thank Mary Maller for suggesting this blog; Mary and Dankrad Feist for feedbacks on earlier versions of this blog.