Post-Quantum Cryptography

The Quantum Threat

Shor's algorithm, running on a sufficiently large quantum computer, can factor integers and compute discrete logarithms in polynomial time. This breaks RSA, ECDSA, and every widely-deployed public-key cryptosystem. Grover's algorithm provides a quadratic speedup for brute-force search, effectively halving symmetric key lengths.

The timeline is uncertain, but the threat is not: “harvest now, decrypt later” attacks mean that data encrypted today with vulnerable algorithms may already be at risk.

NIST Post-Quantum Standards

In 2024, NIST finalized three post-quantum cryptographic standards after an eight-year evaluation process. These algorithms are built on mathematical problems believed to be hard for both classical and quantum computers.

Standard	Algorithm	Type	Hard Problem
FIPS 204	ML-DSA (Dilithium)	Digital Signature	Module-LWE
FIPS 203	ML-KEM (Kyber)	Key Encapsulation	Module-LWE
FIPS 205	SLH-DSA (SPHINCS+)	Digital Signature	Hash functions

Lattice-Based Cryptography

The dominant approach to post-quantum cryptography is built on lattice problems. A lattice is a regular grid of points in high-dimensional space. Two problems form the security foundation:

• Learning With Errors (LWE): Given a system of approximate linear equations over a finite field, recover the secret vector. The “errors” (small noise terms) make this problem exponentially hard in the lattice dimension.
• Shortest Vector Problem (SVP): Find the shortest nonzero vector in a lattice. No known quantum algorithm provides better than marginal improvement over classical approaches.

Blockchain Integration: Tezos tz5 Addresses

Blockchain systems face an acute PQC challenge: addresses are derived directly from public keys, and transactions are authenticated by digital signatures. Every on-chain asset is ultimately protected by the signature scheme.

Tezos is actively developing tz5 addresses based on ML-DSA (Dilithium) for quantum-resistant account security. Key developments:

• New tz5 address prefix for ML-DSA-44 public keys
• Larger transaction sizes due to PQC signature overhead
• Initial restrictions: tz5 accounts may have limited smart contract interaction
• Protocol-level changes required for consensus participation

We track tz5 development through the Tezos GitLab, monitoring merge requests, protocol proposals, and test network deployments.

Current Address Types in Tezos

Prefix	Curve / Algorithm	Status
tz1	Ed25519	Active (most common)
tz2	secp256k1	Active
tz3	P-256 (NIST)	Active
tz4	BLS12-381	Active (consensus)
tz5	ML-DSA-44 (Dilithium)	In development

The Transition Challenge

Migrating to post-quantum cryptography is not a simple algorithm swap. It requires:

• Hybrid schemes: Running classical and PQC algorithms in parallel during the transition period
• Key management: PQC keys are 10-50x larger, impacting storage and bandwidth
• Performance testing: Signature generation and verification times differ significantly from classical algorithms
• Protocol updates: Consensus mechanisms, smart contracts, and wallet software all need adaptation

Key Resources

• NIST Post-Quantum Cryptography project
• Open Quantum Safe — open-source PQC implementations (liboqs)
• Tezos Improvement Proposals for tz5
• ETSI Quantum-Safe Cryptography working group