In 1994, Peter Shor presented an efficient quantum algorithm for solving the computational problems (factoring and discrete logarithms in abelian groups) underpinning current public-key cryptography, invalidating their security in a world where large-scale quantum computers exist. To date, nobody has announced a sufficiently big quantum computer to run Shor's algorithm for any non-trivial problem and it remains unclear if it is at all possible. Nevertheless, recent progress in the area of quantum computing has researchers, standards bodies and governments concerned, especially given that previous transitions of cryptographic algorithms have taken about 20 years in the past. To address this issue, researchers are studying quantum-safe alternatives to the current generation of public-key cryptography. Furthermore, standards bodies have initiated processes to select algorithms for post-quantum cryptography.

As alluded to above, several candidates for post-quantum cryptography exist. However, there are still many challenges to overcome, before we can deploy these candidates with confidence. For example, these candidates have received much less scrutiny than e.g. RSA. It might be possible to find efficient quantum or even classical algorithms for solving some of the problems underlying these candidates. While this may seem unlikely, it is imperative to investigate this possibility in earnest to gain confidence. Furthermore, if our schemes are secure in principle, we still need to choose parameters to ensure security well into the future. Just as we use the best available cryptanalysis to pick the required bit-size for RSA to remain secure for 50 or 100 years (in a pre-quantum world), we will have to rely on the best available cryptanalysis to pick parameters for quantum-safe schemes.

It is worth noting that quantum-safe cryptography is something rather different to quantum key distribution (QKD), which uses quantum mechanics to establish secure keying material between two parties. The former is concerned with drop-in replacements for current-generation cryptography usable without specialised hardware, yet secure against quantum adversaries. In contrast, QKD only covers limited distances so that trusted relays are needed for larger distances, invalidating end-to-end security.

As of writing NIST is finalising its post-quantum standardisation process of public-key encryption and signature schemes. ISG researchers have made significant contributions to the process, including as part of the submission team of one of the finalists (the code-based KEM scheme “Classic McEliece”). However, even if we consider this “done” there is still much to be done to get ready for a post-quantum world. Many currently deployed solutions have no efficient post-quantum replacements yet, such as oblivious PRFs (enabling anonymous credentials), verifiable random functions (proposed for DNSSEC), private set intersection (used for privacy-preserving contact discovery), blind signatures (e-cash, e-voting, anonymous credentials). This is a next frontier for practical post-quantum cryptography, and an active area of research in the ISG.

• Martin Albrecht
• Carlos Cid
• Sean Murphy
• Rachel Player
• Simon Blackburn (Mathematics)
• Ruediger Schack (Quantum Dynamics Group, Mathematics)

• Carlos Cid, Akinori Hosoyamada, Yunwen Liu and Siang Meng Sim. Quantum cryptanalysis on contracting Feistel structures and observation on related-key settings. In: INDOCRYPT 2020. Springer 2020, pp. 373-394.
• Martin R. Albrecht, Shi Bai, Pierre-Alain Fouque, Paul Kirchner, Damien Stehlé, Weiqiang Wen. Faster Enumeration-Based Lattice Reduction: Root Hermite Factor k1/(2k) Time kk/8+o(k). CRYPTO (2) 2020: 186-212
• Morten Øygarden, Patrick Felke, Håvard Raddum and Cid, Carlos. Cryptanalysis of the multivariate encryption scheme EFLASH. In: Topics in Cryptology – CT-RSA 2020. Springer, 2020. p. 85–105. 
• Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W Postlethwaite, and Marc Stevens. “The general sieve kernel and new records in lattice reduction”. In: EUROCRYPT 2019. Springer. 2019, pp. 717–746. https://github.com/fplll/g6k
• Sean Murphy and Rachel Player. “δ-subgaussian Random Variables in Cryptography”. In: Australasian Conference on Information Security and Privacy. Springer. 2019, pp. 251–268
• Ward Beullens and Simon R. Blackburn. Practical Attacks Against the Walnut Digital Signature Scheme. In: ASIACRYPT 2018, Part I. ed. by Thomas Peyrin and Steven Galbraith. Vol. 11272. LNCS. Springer, Heidelberg, Dec. 2018, pp. 35–61. doi: 10.1007/978-3-030-03326-22
• Martin R. Albrecht, Florian Göpfert, Fernando Virdia, and Thomas Wunderer. Revisiting the expected cost of solving uSVP and applications to LWE. in: ASIACRYPT 2017. Springer. 2017, pp. 297–322
• Martin R. Albrecht, Rachel Player, and Sam Scott. “On the concrete hardness of Learning with Errors”. In: Journal of Mathematical Cryptology 9.3 (2015), pp. 169–203. https://bitbucket.org/malb/lwe-estimator
• FPLLL: This open source library is the de facto standard for fast lattice reduction, which is a key technique to assess the security of lattice-based cryptography, one of the main quantum-safe cryptography candidates https://github.com/fplll/fplll. See also https://github.com/fplll/fpylll