Cryptography

Problem

Shor’s algorithm1 allows a sufficiently powerful quantum computer to recover private keys from public keys for legacy cryptosystems, in particular by factoring RSA public moduli2 and breaking the (EC)DLP3.

This drives the need to replace all public key algorithms, particularly digital signatures and key exchange / encapsulation.

RSA and integer factoring Diffie-Hellman and Discrete Logarithm

Solution

Post-quantum cryptography is about finding new problems that are presumed to be difficult to solve on both classical and quantum computers – until proven otherwise – and building new cryptosystems on these problems.

New Post-quantum Cryptography Standards

References

  1. Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484–1509. https://doi.org/10.1137/s0097539795293172 ↩︎

  2. Ekerå, M. (2021). On completely factoring any integer efficiently in a single run of an order-finding algorithm. Quantum Information Processing, 20(6). https://doi.org/10.1007/s11128-021-03069-1 ↩︎

  3. Roetteler, M., Naehrig, M., Svore, K. M., and Lauter, K. (2017). Quantum resource estimates for computing elliptic curve discrete logarithms. Cryptology ePrint Archive, Paper 2017/598. https://eprint.iacr.org/2017/598 ↩︎

Last updated on