Cryptographically relevant quantum computer, if built, could enable Shor’s algorithm and Grover’s algorithm. These completely break ECDSA / ECDH, and reduce hash function (& cipher) strength from 2^n to 2^\frac{n}{2}
There are some non-obvious parts of ETH which would need to be upgraded.
What is still OK
bip39 (pbkdf2-sha512) seems just fine
eip2333 validator withdrawal keys are also fine!
What needs upgrading
bip32 hdkey derivation
Should be replaced by something post-quantum and better (no “non-hardened” keys)
New scheme could be based on HKDF (like EIP-2333), but not HKDF-SHA256
Alternative KDF is Blake3 in context mode (pq security is unclear)
The proposed scheme should support both ECC and new pq mode
Transaction signing
Should be replaced by lattice-based Falcon (FN-DSA / FIPS-206),
or hash-based Sphincs-plus (SLH-DSA / FIPS-205)
New keys and signatures will consume more space
Falcon-1024 has 1.75KB keys and 1.25KB sigs
SLH-DSA-256 has 48-128B keys and 17-51KB sigs
Sender address recovery
It was feature of ECDSA (not available in Schnorr, for example)
Perhaps txs (and not sigs) should encode sender addresses
Address format
Currently it’s 40 hex characters, keccak256(pubkey)
keccak256 should be replaced by keccak512 / sha3-512 / sha512 / blake3-512
How does Grover algo affect brute-forcing of addresses? Should 40 characters be upped to 80-128?
Longer address formats should probably use something like bech32 for checksumming & human-friendliness
How would new addresses interop with old addresses / EVM?
Encrypted wallets
Should upgrade from AES-128 to AES-256 or chacha20
hmac-sha256 should upgrade to hmac-sha512 / kmac / blake3-512 (keyed mode)
KZG EIP-4844 verification
Should be replaced by a post-quantum scheme
Algorithms are unclear for now, any suggestions?
EVM 0x20 opcode (KECCAK256)
Should be replaced by keccak512 / sha3-512 / sha512 / blake3-512 (new opcode)
EVM precompile for ECRECOVER
See address recovery above
EVM precompiles for BN / BLS / KZG
Should be replaced by newer schemes (unclear which ones?)
No more Groth16, vanilla PLONK, Marlin, BulletProof
Consensus layer signature aggregation
Currently aggregates signatures of all validators once per epoch (6 mins)
More than 1M signatures right now?
Algorithms are unclear for now, any suggestions?
ZK-rollups (non STARK)
Anything else?
Final thoughts
I’m confident all of these problems can be solved even in limited time. Let’s start solving them.
I might point out that while Grover gives an asymptotic sqrt advantage, currently the consensus is that the attack concrete costs are large enough that it is not much better than classical methods.
See (I can’t link) csrc nist gov/csrc/media/Events/2024/fifth-pqc-standardization-conference/documents/papers/on-practical-cost-of-grover.pdf for example.
This is why the NIST-PQC standard still recommends AES-128 as the symmetric component in most of these ciphers.
Some chains (e.g. Polygon or ZKsync) have already implemented RIP-7212, i.e. the P256VERIFY precompile at address 0x100 for the non-Ethereum-native NIST P-256 elliptic curve (also known as secp256r1). Other chains will follow in the near future and even Ethereum mainnet will eventually ship it probably.
Node discovery (DevP2P): The current Kademlia DHT employs secp256k1 for node identity, which would require quantum-resistant replacements to ensure security. Handshake protocols and all p2p encryption mechanisms must be upgraded to post-quantum schemes. Additionally, Ethereum Node Records (ENR) would need new identity schemes, and - if I’m not completely wrong - the Discovery v5 protocol would require significant modifications to support these changes. Ethereum relies on the Node Discovery v5 protocol for bootstrap and peer discovery. Furthermore, IMHO (also not 100% sure) the boot node infrastructure needs a comprehensive security reassessment to address vulnerabilities in a post-quantum environment.
Light client sync protocols need quantum-resistant proofs.
if the hash function property we need is collision resistance, difficulty is n/2, quantum computing reduces it to n/3, so 384 bits might be enough (while 512 could still be a conservative choice).
the end game being ZK, while replacing keccak, a ZK-friendly (ie NTT friendly) hash function might be pushed instead of larger keccak sizes.
RIP7212 has been pushed because of Passkey/FIDO, for sure one standard will be pushed as a replacement when the threat is considered high enough.
there is a potential key recovery mechanism in FALCON.
instead of pushing a precise lattice candidate, which might change, the efforts could focus on NTT, both a building block for ZK schemes and PQ-sig schemes. This precompile could provide large speed-ups for STARKS (potential replacement for KZG).
While there is a sudden FUD around quantum threat, which shall be taken seriously, ciphering is considered from today because of Forward secrecy. The transition must be prepared, but authentication is less threatened. (looking at GAFAM, ciphering like in e-message already migrates, not auth.). There is a lot to do and we shall prepare those rn, sustainability of solutions shall be preferred.
I’m not sure if this is what you were suggesting but replacing the opcode in place is not a good idea, it’s better to have lower security contracts than completely broken ones (in the sense that they can’t even run because the hash function was rug pulled). We should add a new opcode for a higher security hash function and let developers and users migrate. The same applies to other opcodes and precompiles.
Probably just say “hardened keys only” because it’s not clear how to do non-hardened derivation as that depends on having a homomorphism. Something lattice-based eventually?
Agree we should dump this and just include sender address in the tx. The AA standards (eg. EIP-7701) already do this.
Address format
Grover reduces brute-force cost from 2^160 to 2^80, still extremely high esp if you take into account quantum computers realistically being much slower per computation step. So, not worried here.
Encrypted wallets
Agree it’s worth looking into.
KZG EIP-4844 verification
STARKed Merkelized erasure coded blobs.
EVM 0x20 opcode (KECCAK256)
I don’t think 256-bit hashes will be a problem, same reason as why addresses are ok
EVM precompile for ECRECOVER
EVM precompiles for BN / BLS / KZG
Yeah we will phase ECDSA out entirely, so at some point just replace this with EVM code for backwards compatibility and dump the precompile.
ZK-rollups (non STARK)
Replace with STARKs, and consider adding in-protocol aggregation to make it more cost-friendly in the protocol.
For bip32 i’ve meant that if wallets would be switching to pq sigs, there would be no need in bip32, which even in hardened version rejects keys over curve order. If we modify bip32 to remove this check, it would no longer be bip32. And pqc may need keys larger than amount of bytes bip32 can produce.
Better to just invent a completely new scheme which plays nicely with both ECC and PQC. EIP2333 is a great starting point.
Non hardened version of course belongs to trash bin. Never liked it much bc of address associativity. In pq setting it’s particularly bad.