Post-Quantum Cryptography

Classical cryptography safeguards information by leveraging the inherent difficulty of certain mathematical problems. Such group of problems as prime factoring, discrete logarithm, graph isomorphism, and the shortest vector problem etc. fall under the area of mathematical research called the Hidden Subgroup Problem (HSP).

In essence, these problems makes determining the structure of a secret subgroup (size, elements) within a large group computationally intractable without the knowledge of a "secret" (private) key. This one-way "trapdoor function" is employed by public-key cryptography algorithms for their security.

RSA's security rests on the factoring of large prime numbers. In contrast, ECDSA's security is based on the elliptic curve discrete logarithm problem. Solving either of these hidden subgroup problems becomes exponentially harder as the key size increases, making them computationally infeasible for classical computers to crack. This fundamental difficulty safeguards encrypted data.

However, the landscape is shifting.

Quantum computers, harnessing the principles of quantum mechanics, offer novel computational approaches. Certain quantum algorithms can solve these classical cryptographic problems with exponential efficiency compared to their classical counterparts. This newfound capability poses a significant threat to the security of data encrypted with classical cryptography. If large-scale quantum computers are ever built, they will be able to break many of the public-key cryptography currently in use.

Shor's algorithm for integer factorization is the most celebrated application of quantum computing. It factors n-digit integers in a time complexity less than $O(n^3)$ , a significant improvement over the best classical algorithms.

This is where the field of post-quantum cryptography comes in. It aims to develop new algorithms that remain secure even in the presence of powerful quantum computers.

Timeline

According to the survey done for "Quantum Threat Timeline Report 2020" most experts believe that there is <5% threat to the public-key cryptography until 2030. However, it is predicted that the risk substantially increases to about 50% by 2050.

Currently, the most advanced quantum computers have <2000 physical qubits. Breaking Bitcoin's encryption within an hour (ideal time window) requires approximately 317 million physical qubits.

Steady progress is being made in quantum research; one survey respondent notes:

It is not always the case [..] but I find that my predictions are often more pessimistic than what actually happens. I take this as a sign that the research is accelerating.

Note that these predictions are somewhat subjective and might not reflect real progress which is mostly not open to public. Advanced threat actor might have access to powerful quantum computing sooner than public and use strategies like retrospective decryption.

2025

In Feb 2025, Microsoft announced a million qubits on a single chip.. Video explanation with context.

Post-Quantum risk to Ethereum

Ethereum accounts are secured by a two-tier cryptosystem. A private key is used to generate a public key through elliptic curve multiplication. This public key is hashed using keccak256 to derive the Ethereum address.

The immediate post-quantum threat is the ability to reverse elliptic curve multiplication securing ECDSA thus exposing the private key. This makes all externally owned accounts (EOA) vulnerable to a quantum attack. Assuming the hashing function that maps a public-key to an ethereum address is still safe, extracting its private key is still challenging but vulnerable nonetheless.

In practice, most users’ private keys are themselves the result of a bunch of hash calculations using BIP-32, which generates each address through a series of hashes starting from a master seed phrase. This makes revealing the private key even more computationally expensive.

EthResearch has an ongoing proposal for a hard-fork in the event of a post-quantum emergency, the key actions being:

Revert all blocks after the first block where it’s clear that large-scale theft is happening
Traditional EOA-based transactions are disabled
A new transaction type is added to allow transactions from smart contract wallets (eg. part of RIP-7560), if this is not available already
A new transaction type or opcode is added by which you can provide a STARK proof which proves knowledge of (i) a private preimage x, (ii) a hash function ID 1 <= i < k from a list of k approved hash functions, and (iii) a public address A, such that keccak(priv_to_pub(hashes[i](x)))[12:] = A. The STARK also accepts as a public input the hash of a new piece of validation code for that account. If the proof passes, your account’s code is switched over to the new validation code, and you will be able to use it as a smart contract wallet from that point forward.

The approach, however, is not perfect. Some users will still loose funds since not all blocks from the event of an attack will be reverted. This is because it is incredibly hard to reliably detect a quantum attack on the network as domothy highlights:

Picture a single large exchange wallet being drained by a quantum computer. Everyone would naturally assume it was a security failure of some kind on the exchange’s end. Or if a smart wallet relying on discrete log assumption gets drained, a smart contract bug/exploit would be the first thing that comes to mind. Or the quantum-enabled attacker avoids high profile targets altogether and slowly steals funds from various large EOAs, and we never even know a quantum attack took place.

Further, KZG commitment schemes powering EIP-4844 would also need to be upgraded to prevent fraudulent commits.

Research

Post-quantum cryptography is an active area of research. Several organizations are working on prototyping, development, and standardization of new post-quantum algorithms.

NIST Post-Quantum Cryptography

The NIST Post-Quantum Cryptography standardization effort is a competition like process to solicit, evaluate, and standardize one or more quantum-resistant public-key cryptographic algorithms.

Selected Algorithms by NIST as part of third round in 2022

I. Public-key Encryption and key-establishment algorithms

CRYSTALS-KYBER by Peter Schwabe et al.

II. Digital signature algorithm

CRYSTALS-DILITHIUM by Vadim Lyubashevsky et al.
FALCON by Thomas Prest et al.
SPHINCS+ by Andreas Hulsing et al.

NIST's "2022 status report" documents the standardization process, evaluation criteria, and security models.

Anchor Vault is a chrome plugin allows adding a quantum-resistant proof using Lamport's signature for securing ERC tokens.
Signal has implemented "Post-Quantum Extended Diffie-Hellman" in production for key agreement protocol.
Chromium started supporting "Hybrid Kyber KEM" to protect data in transit.
Apple has implemented PQ3 to protect iMessage against key compromise from a quantum attack.

Resources

📝 Daniel J. Bernstein and et al, "Introduction to post-quantum cryptography"
📝 Wikipedia, "Quantum algorithm."
📝 P.W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring."
📝 NIST, "Post-Quantum Cryptography."
📝 ETHResearch, "How to hard-fork to save most users’ funds in a quantum emergency."
📝 ETHResearch, "ETHResearch: Post-Quantum"
📝 Vitalik Buterin, "STARKs, Part I: Proofs with Polynomials."
📝 Wikipedia, "Lamport's Signature."