Post-quantum cryptography

Post-quantum cryptography research is mostly focused on six different approaches:

{{Main|Lattice-based cryptography}}

This approach includes cryptographic systems such as learning with errors, ring learning with errors (ring-LWE),{{cite web|last=Peikert|first=Chris|title=Lattice Cryptography for the Internet|url=http://eprint.iacr.org/2014/070.pdf|publisher=IACR|access-date=10 May 2014|archive-url=https://web.archive.org/web/20140512214902/http://eprint.iacr.org/2014/070.pdf|archive-date=12 May 2014|year=2014|url-status=bot: unknown}}{{cite web|url=http://emsec.rub.de/media/sh/veroeffentlichungen/2014/06/12/lattice_signature.pdf|title=Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems|last1=Güneysu|first1=Tim|last2=Lyubashevsky|first2=Vadim|last3=Pöppelmann|first3=Thomas|year=2012|publisher=INRIA|access-date=12 May 2014}}{{cite web|last1=Zhang|first1=jiang|title=Authenticated Key Exchange from Ideal Lattices|url=http://eprint.iacr.org/2014/589.pdf|website=iacr.org|publisher=IACR|access-date=7 September 2014|archive-url=https://web.archive.org/web/20140907212538/http://eprint.iacr.org/2014/589.pdf|archive-date=7 September 2014|year=2014|url-status=bot: unknown}} the ring learning with errors key exchange and the ring learning with errors signature, the older NTRU or GGH encryption schemes, and the newer NTRU signature and BLISS signatures. Some of these schemes like NTRU encryption have been studied for many years without anyone finding a feasible attack. Others like the ring-LWE algorithms have proofs that their security reduces to a worst-case problem.{{cite web|last=Lyubashevsky|first=Vadim|title=On Ideal Lattices and Learning with Errors Over Rings|url=http://eprint.iacr.org/2012/230.pdf|publisher=IACR|access-date=14 May 2013|author2=Peikert|author3=Regev|archive-url=https://web.archive.org/web/20140131051244/http://eprint.iacr.org/2012/230.pdf|archive-date=31 January 2014|year=2013|url-status=bot: unknown}} The Post-Quantum Cryptography Study Group sponsored by the European Commission suggested that the Stehle–Steinfeld variant of NTRU be studied for standardization rather than the NTRU algorithm.{{cite web|url = http://pqcrypto.eu.org/docs/initial-recommendations.pdf|title = Initial recommendations of long-term secure post-quantum systems|date = 7 September 2015|access-date = 13 September 2015|website = PQCRYPTO|last = Augot|first = Daniel}}{{cite journal|title = Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices|url = http://eprint.iacr.org/2013/004|date = 2013-01-01|first1 = Damien|last1 = Stehlé|first2 = Ron|last2 = Steinfeld| journal=Cryptology ePrint Archive }} At that time, NTRU was still patented. Studies have indicated that NTRU may have more secure properties than other lattice based algorithms.{{cite book|date = 2019-02-01|first = Chuck|last = Easttom| title=2019 IEEE 9th Annual Computing and Communication Workshop and Conference (CCWC) |chapter = An Analysis of Leading Lattice-Based Asymmetric Cryptographic Primitives|pages = 0811–0818|doi = 10.1109/CCWC.2019.8666459|isbn = 978-1-7281-0554-3|s2cid = 77376310}}

{{Main|Multivariate cryptography}}

This includes cryptographic systems such as the Rainbow (Unbalanced Oil and Vinegar) scheme which is based on the difficulty of solving systems of multivariate equations. Various attempts to build secure multivariate equation encryption schemes have failed. However, multivariate signature schemes like Rainbow could provide the basis for a quantum secure digital signature.{{cite book |last=Ding |first=Jintai |title=Applied Cryptography and Network Security |author2=Schmidt |date=7 June 2005 |isbn=978-3-540-26223-7 |editor1-last=Ioannidis |editor1-first=John |series=Lecture Notes in Computer Science |volume=3531 |pages=64–175 |language=en-us |contribution=Rainbow, a New Multivariable Polynomial Signature Scheme |doi=10.1007/11496137_12 |s2cid=6571152}} The Rainbow Signature Scheme is patented (the patent expires in August 2029).

{{Main|Hash-based cryptography}}

This includes cryptographic systems such as Lamport signatures, the Merkle signature scheme, the XMSS,{{cite conference|last1=Buchmann|first1=Johannes|last2=Dahmen|first2=Erik|last3=Hülsing|first3=Andreas|contribution=XMSS – A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions|series=Lecture Notes in Computer Science|volume=7071|pages=117–129|title=Post-Quantum Cryptography. PQCrypto 2011|year=2011|issn=0302-9743|doi=10.1007/978-3-642-25405-5_8|isbn=978-3-642-25404-8 |citeseerx=10.1.1.400.6086}} the SPHINCS,{{Cite book|issue=Advances in Cryptology – EUROCRYPT 2015|last1=Bernstein|first1=Daniel J.|last2=Hopwood|first2=Daira|last3=Hülsing|first3=Andreas|last4=Lange|first4=Tanja|author4-link=Tanja Lange|last5=Niederhagen|first5=Ruben|last6=Papachristodoulou|first6=Louiza|last7=Schneider|first7=Michael|last8=Schwabe|first8=Peter|last9=Wilcox-O'Hearn|first9=Zooko|chapter=SPHINCS: Practical Stateless Hash-Based Signatures |title=Advances in Cryptology -- EUROCRYPT 2015|year=2015|publisher=Springer Berlin Heidelberg|isbn=9783662467992|editor-last=Oswald|editor-first=Elisabeth|editor-link= Elisabeth Oswald |series=Lecture Notes in Computer Science|volume=9056|pages=368–397|language=en|doi=10.1007/978-3-662-46800-5_15|editor-last2=Fischlin|editor-first2=Marc|citeseerx = 10.1.1.690.6403}} and the WOTS schemes. Hash based digital signatures were invented in the late 1970s by Ralph Merkle and have been studied ever since as an interesting alternative to number-theoretic digital signatures like RSA and DSA. Their primary drawback is that for any hash-based public key, there is a limit on the number of signatures that can be signed using the corresponding set of private keys. This fact reduced interest in these signatures until interest was revived due to the desire for cryptography that was resistant to attack by quantum computers. There appear to be no patents on the Merkle signature scheme{{Citation needed|date=August 2015}} and there exist many non-patented hash functions that could be used with these schemes. The stateful hash-based signature scheme XMSS developed by a team of researchers under the direction of Johannes Buchmann is described in RFC 8391.{{cite journal|title=RFC 8391 – XMSS: eXtended Merkle Signature Scheme|url=https://tools.ietf.org/html/rfc8391|website=tools.ietf.org|year=2018 |doi=10.17487/RFC8391 |language=en|last1=Huelsing |first1=A. |last2=Butin |first2=D. |last3=Gazdag |first3=S. |last4=Rijneveld |first4=J. |last5=Mohaisen |first5=A. }}

Note that all the above schemes are one-time or bounded-time signatures, Moni Naor and Moti Yung invented UOWHF hashing in 1989 and designed a signature based on hashing (the Naor-Yung scheme){{citation |last1=Naor |first1=Moni |title=Universal One-Way Hash Functions and their Cryptographic Applications .STOC |date=1989 |pages=33–43 |last2=Yung |first2=Moti}} which can be unlimited-time in use (the first such signature that does not require trapdoor properties).

This includes cryptographic systems which rely on error-correcting codes, such as the McEliece and Niederreiter encryption algorithms and the related Courtois, Finiasz and Sendrier Signature scheme. The original McEliece signature using random Goppa codes has withstood scrutiny for over 40 years. However, many variants of the McEliece scheme, which seek to introduce more structure into the code used in order to reduce the size of the keys, have been shown to be insecure.{{cite book|last=Overbeck|first=Raphael|author2=Sendrier|title=Post-Quantum Cryptography |chapter=Code-based cryptography |date=2009|pages=95–145|doi=10.1007/978-3-540-88702-7_4|editor1-first=Daniel|editor1-last=Bernstein|isbn=978-3-540-88701-0}} The Post-Quantum Cryptography Study Group sponsored by the European Commission has recommended the McEliece public key encryption system as a candidate for long term protection against attacks by quantum computers.

These cryptographic systems rely on the properties of isogeny graphs of elliptic curves (and higher-dimensional abelian varieties) over finite fields, in particular supersingular isogeny graphs, to create cryptographic systems. Among the more well-known representatives of this field are the Diffie–Hellman-like key exchange CSIDH, which can serve as a straightforward quantum-resistant replacement for the Diffie–Hellman and elliptic curve Diffie–Hellman key-exchange methods that are in widespread use today,{{Cite book |last1=Castryck |first1=Wouter |last2=Lange |first2=Tanja |last3=Martindale |first3=Chloe |last4=Panny |first4=Lorenz |last5=Renes |first5=Joost |title=Advances in Cryptology – ASIACRYPT 2018 |chapter=CSIDH: An Efficient Post-Quantum Commutative Group Action |date=2018 |editor-last=Peyrin |editor-first=Thomas |editor2-last=Galbraith |editor2-first=Steven |chapter-url=https://hdl.handle.net/handle/1854/LU-8619033 |series=Lecture Notes in Computer Science |volume=11274 |language=en |location=Cham |publisher=Springer International Publishing |pages=395–427 |doi=10.1007/978-3-030-03332-3_15 |hdl=1854/LU-8619033 |isbn=978-3-030-03332-3|s2cid=44165584 }} and the signature scheme SQIsign which is based on the categorical equivalence between supersingular elliptic curves and maximal orders in particular types of quaternion algebras.{{Cite book |last1=De Feo |first1=Luca |last2=Kohel |first2=David |last3=Leroux |first3=Antonin |last4=Petit |first4=Christophe |last5=Wesolowski |first5=Benjamin |title=Advances in Cryptology – ASIACRYPT 2020 |chapter=SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies |date=2020 |editor-last=Moriai |editor-first=Shiho |editor2-last=Wang |editor2-first=Huaxiong |chapter-url=https://hal.archives-ouvertes.fr/hal-03038004/file/2020-1240.pdf |series=Lecture Notes in Computer Science |volume=12491 |language=en |location=Cham |publisher=Springer International Publishing |pages=64–93 |doi=10.1007/978-3-030-64837-4_3 |isbn=978-3-030-64837-4|s2cid=222265162 }} Another widely noticed construction, SIDH/SIKE, was spectacularly broken in 2022.{{Citation |last1=Castryck |first1=Wouter |title=An Efficient Key Recovery Attack on SIDH |date=2023 |url=https://link.springer.com/10.1007/978-3-031-30589-4_15 |work=Advances in Cryptology – EUROCRYPT 2023 |volume=14008 |pages=423–447 |editor-last=Hazay |editor-first=Carmit |access-date=2023-06-21 |place=Cham |publisher=Springer Nature Switzerland |language=en |doi=10.1007/978-3-031-30589-4_15 |isbn=978-3-031-30588-7 |last2=Decru |first2=Thomas |s2cid=258240788 |editor2-last=Stam |editor2-first=Martijn}} The attack is however specific to the SIDH/SIKE family of schemes and does not generalize to other isogeny-based constructions.{{Cite web |title=Is SIKE broken yet? |url=https://issikebrokenyet.github.io/ |access-date=2023-06-23}}

Provided one uses sufficiently large key sizes, the symmetric key cryptographic systems like AES and SNOW 3G are already resistant to attack by a quantum computer.{{cite conference|last=Perlner|first=Ray|title=Quantum Resistant Public Key Cryptography: A Survey|url=https://www.nist.gov/manuscript-publication-search.cfm?pub_id=901595|conference=8th Symposium on Identity and Trust on the Internet (IDtrust 2009)|publisher=NIST|access-date=23 Apr 2015|author2=Cooper|year=2009}} Further, key management systems and protocols that use symmetric key cryptography instead of public key cryptography like Kerberos and the 3GPP Mobile Network Authentication Structure are also inherently secure against attack by a quantum computer. Given its widespread deployment in the world already, some researchers recommend expanded use of Kerberos-like symmetric key management as an efficient way to get post-quantum cryptography today.{{cite web|last=Campagna|first=Matt|title=Kerberos Revisited Quantum-Safe Authentication|url=http://docbox.etsi.org/Workshop/2013/201309_CRYPTO/S03_INDUSTRY_SESSION/PITNEYBOWES_PINTSOV.pdf|publisher=ETSI|author2=Hardjono|author3= Pintsov|author4= Romansky|author5= Yu|year=2013}}

In cryptography research, it is desirable to prove the equivalence of a cryptographic algorithm and a known hard mathematical problem. These proofs are often called "security reductions", and are used to demonstrate the difficulty of cracking the encryption algorithm. In other words, the security of a given cryptographic algorithm is reduced to the security of a known hard problem. Researchers are actively looking for security reductions in the prospects for post-quantum cryptography. Current results are given here:

{{further|Ring learning with errors key exchange}}

In some versions of Ring-LWE there is a security reduction to the shortest-vector problem (SVP) in a lattice as a lower bound on the security. The SVP is known to be NP-hard.{{cite web|last1=Lyubashevsky|first1=Vadim|author2=Peikert|author3=Regev|title=On Ideal Lattices and Learning with Errors Over Rings|url=https://web.eecs.umich.edu/~cpeikert/pubs/ideal-lwe.pdf|publisher=Springer|access-date=19 June 2014|date=25 June 2013}} Specific ring-LWE systems that have provable security reductions include a variant of Lyubashevsky's ring-LWE signatures defined in a paper by Güneysu, Lyubashevsky, and Pöppelmann. The GLYPH signature scheme is a variant of the Güneysu, Lyubashevsky, and Pöppelmann (GLP) signature which takes into account research results that have come after the publication of the GLP signature in 2012. Another Ring-LWE signature is Ring-TESLA.{{Cite journal |last1=Akleylek |first1=Sedat |last2=Bindel |first2=Nina |last3=Buchmann |first3=Johannes |last4=Krämer |first4=Juliane |last5=Marson |first5=Giorgia Azzurra |date=2016 |title=An Efficient Lattice-Based Signature Scheme with Provably Secure Instantiation|journal=Cryptology ePrint Archive |url=https://eprint.iacr.org/2016/030}} There also exists a "derandomized variant" of LWE, called Learning with Rounding (LWR), which yields "improved speedup (by eliminating sampling small errors from a Gaussian-like distribution with deterministic errors) and bandwidth".{{Cite journal|last1=Nejatollahi|first1=Hamid|last2=Dutt|first2=Nikil|last3=Ray|first3=Sandip|last4=Regazzoni|first4=Francesco|last5=Banerjee|first5=Indranil|last6=Cammarota|first6=Rosario|date=2019-02-27|title=Post-Quantum Lattice-Based Cryptography Implementations: A Survey|url=https://dl.acm.org/doi/10.1145/3292548|journal=ACM Computing Surveys|language=en|volume=51|issue=6|pages=1–41|doi=10.1145/3292548|s2cid=59337649|issn=0360-0300}} While LWE utilizes the addition of a small error to conceal the lower bits, LWR utilizes rounding for the same purpose.

The security of the NTRU encryption scheme and the BLISS{{cite journal|title = Lattice Signatures and Bimodal Gaussians|url = http://eprint.iacr.org/2013/383|date = 2013|access-date = 2015-04-18|first1 = Léo|last1 = Ducas|first2 = Alain|last2 = Durmus|first3 = Tancrède|last3 = Lepoint|first4 = Vadim|last4 = Lyubashevsky|journal=Cryptology ePrint Archive}} signature is believed to be related to, but not provably reducible to, the closest vector problem (CVP) in a lattice. The CVP is known to be NP-hard. The Post-Quantum Cryptography Study Group sponsored by the European Commission suggested that the Stehle–Steinfeld variant of NTRU, which does have a security reduction be studied for long term use instead of the original NTRU algorithm.

{{further|Multivariate cryptography}}

Unbalanced Oil and Vinegar signature schemes are asymmetric cryptographic primitives based on multivariate polynomials over a finite field {{tmath|1= \mathbb{F} }}. Bulygin, Petzoldt and Buchmann have shown a reduction of generic multivariate quadratic UOV systems to the NP-Hard multivariate quadratic equation solving problem.{{cite book|last1=Bulygin|first1=Stanislav|author2=Petzoldt|author3=Buchmann|contribution=Towards Provable Security of the Unbalanced Oil and Vinegar Signature Scheme under Direct Attacks|title=Progress in Cryptology – INDOCRYPT 2010|date=2010|volume=6498|pages=17–32|series=Lecture Notes in Computer Science|doi=10.1007/978-3-642-17401-8_3|citeseerx=10.1.1.294.3105|isbn=978-3-642-17400-1}}

{{further|Hash-based cryptography|Merkle signature scheme}}

In 2005, Luis Garcia proved that there was a security reduction of Merkle Hash Tree signatures to the security of the underlying hash function. Garcia showed in his paper that if computationally one-way hash functions exist then the Merkle Hash Tree signature is provably secure.{{cite journal|last1=Pereira|first1=Geovandro|last2=Puodzius| first2 =Cassius|last3 = Barreto|first3 = Paulo|title = Shorter hash-based signatures|journal=Journal of Systems and Software|doi=10.1016/j.jss.2015.07.007|volume=116|pages=95–100|year=2016}}

Therefore, if one used a hash function with a provable reduction of security to a known hard problem one would have a provable security reduction of the Merkle tree signature to that known hard problem.{{cite web|last1 = Garcia|first1=Luis|title=On the security and the efficiency of the Merkle signature scheme|url=http://eprint.iacr.org/2005/192.pdf|website=Cryptology ePrint Archive|publisher=IACR|access-date=19 June 2013}}

The Post-Quantum Cryptography Study Group sponsored by the European Commission has recommended use of Merkle signature scheme for long term security protection against quantum computers.

{{further|McEliece cryptosystem}}

The McEliece Encryption System has a security reduction to the syndrome decoding problem (SDP). The SDP is known to be NP-hard.{{cite book|last1=Blaum|first1=Mario|author2=Farrell|author3=Tilborg|title=Information, Coding and Mathematics|date=31 May 2002|publisher=Springer|isbn=978-1-4757-3585-7}} The Post-Quantum Cryptography Study Group sponsored by the European Commission has recommended the use of this cryptography for long term protection against attack by a quantum computer.

In 2016, Wang proposed a random linear code encryption scheme RLCE{{cite journal |last=Wang |first=Yongge |title=Quantum resistant random linear code based public key encryption scheme RLCE|journal=Proceedings of Information Theory (ISIT)|date=2016|pages=2519–2523|series=IEEE ISIT|arxiv=1512.08454|bibcode=2015arXiv151208454W}} which is based on McEliece schemes. RLCE scheme can be constructed using any linear code such as Reed-Solomon code by inserting random columns in the underlying linear code generator matrix.

{{further|Supersingular isogeny key exchange}}

Security is related to the problem of constructing an isogeny between two supersingular curves with the same number of points. The most recent investigation of the difficulty of this problem is by Delfs and Galbraith indicates that this problem is as hard as the inventors of the key exchange suggest that it is.{{cite arXiv|last1=Delfs|first1=Christina|author2=Galbraith|title=Computing isogenies between supersingular elliptic curves over F_p|eprint=1310.7789|class=math.NT|year=2013}} There is no security reduction to a known NP-hard problem.

One common characteristic of many post-quantum cryptography algorithms is that they require larger key sizes than commonly used "pre-quantum" public key algorithms. There are often tradeoffs to be made in key size, computational efficiency and ciphertext or signature size. The table lists some values for different schemes at a 128-bit post-quantum security level.

A practical consideration on a choice among post-quantum cryptographic algorithms is the effort required to send public keys over the internet. From this point of view, the Ring-LWE, NTRU, and SIDH algorithms provide key sizes conveniently under 1 kB, hash-signature public keys come in under 5 kB, and MDPC-based McEliece takes about 1 kB. On the other hand, Rainbow schemes require about 125 kB and Goppa-based McEliece requires a nearly 1 MB key.

{{further|Ring learning with errors key exchange}}

The fundamental idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The basic idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper{{Cite journal|title = A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem|url = http://eprint.iacr.org/2012/688|date = 2012-01-01|first1 = Jintai |last1 = Ding|first2 = Xiang |last2 = Xie|first3 = Xiaodong|last3 = Lin| journal=Cryptology ePrint Archive }} appeared in 2012 after a provisional patent application was filed in 2012.

In 2014, Peikert{{Cite journal|title = Lattice Cryptography for the Internet|url = http://eprint.iacr.org/2014/070|date = 2014-01-01|first = Chris|last = Peikert| journal=Cryptology ePrint Archive }} presented a key transport scheme following the same basic idea of Ding's, where the new idea of sending additional 1 bit signal for rounding in Ding's construction is also utilized. For somewhat greater than 128 bits of security, Singh presents a set of parameters which have 6956-bit public keys for the Peikert's scheme.{{cite journal|title = A Practical Key Exchange for the Internet using Lattice Cryptography|url = http://eprint.iacr.org/2015/138|date = 2015|access-date = 2015-04-18|first = Vikram|last = Singh|journal =Cryptology ePrint Archive}} The corresponding private key would be roughly 14,000 bits.

In 2015, an authenticated key exchange with provable forward security following the same basic idea of Ding's was presented at Eurocrypt 2015,{{Cite book|contribution = Authenticated Key Exchange from Ideal Lattices|publisher = Springer Berlin Heidelberg|date = 2015-04-26|isbn = 978-3-662-46802-9|pages = 719–751|series = Lecture Notes in Computer Science|first1 = Jiang|last1 = Zhang|first2 = Zhenfeng|last2 = Zhang|first3 = Jintai|last3 = Ding|first4 = Michael|last4 = Snook|first5 = Özgür|last5 = Dagdelen| volume=9057 |editor-first = Elisabeth|editor-last = Oswald|editor-first2 = Marc|editor-last2 = Fischlin|doi = 10.1007/978-3-662-46803-6_24|citeseerx = 10.1.1.649.1864|title=Advances in Cryptology – EUROCRYPT 2015}} which is an extension of the HMQV{{Cite book|publisher = Springer|date = 2005-08-14|isbn = 978-3-540-28114-6|pages = 546–566|series = Lecture Notes in Computer Science|first = Hugo|last = Krawczyk|editor-first = Victor|editor-last = Shoup|doi = 10.1007/11535218_33|title = Advances in Cryptology – CRYPTO 2005|volume = 3621|chapter = HMQV: A High-Performance Secure Diffie–Hellman Protocol}} construction in Crypto2005. The parameters for different security levels from 80 bits to 350 bits, along with the corresponding key sizes are provided in the paper.

{{further|NTRUEncrypt}}

For 128 bits of security in NTRU, Hirschhorn, Hoffstein, Howgrave-Graham and Whyte, recommend using a public key represented as a degree 613 polynomial with coefficients {{tmath|1= \bmod{\left(2^{10}\right)} }} This results in a public key of 6130 bits. The corresponding private key would be 6743 bits.{{cite web|last=Hirschborrn|first=P|title=Choosing NTRUEncrypt Parameters in Light of Combined Lattice Reduction and MITM Approaches|url=https://www.securityinnovation.com/uploads/Crypto/params.pdf|publisher=NTRU|access-date=12 May 2014|author2=Hoffstein|author3=Howgrave-Graham|author4=Whyte|archive-url=https://web.archive.org/web/20130130160705/https://securityinnovation.com/uploads/Crypto/params.pdf|archive-date=30 January 2013|url-status=dead}}

{{further|Multivariate cryptography}}

For 128 bits of security and the smallest signature size in a Rainbow multivariate quadratic equation signature scheme, Petzoldt, Bulygin and Buchmann, recommend using equations in GF(31) with a public key size of just over 991,000 bits, a private key of just over 740,000 bits and digital signatures which are 424 bits in length.{{cite web|last=Petzoldt|first=Albrecht|title=Selecting Parameters for the Rainbow Signature Scheme – Extended Version -|url=http://eprint.iacr.org/2010/437.pdf|access-date=12 May 2014|author2=Bulygin|author3=Buchmann|archive-date=4 March 2016|archive-url=https://web.archive.org/web/20160304001111/http://eprint.iacr.org/2010/437.pdf|year=2010|url-status=bot: unknown}}

{{further|Hash-based cryptography|Merkle signature scheme}}

In order to get 128 bits of security for hash based signatures to sign 1 million messages using the fractal Merkle tree method of Naor Shenhav and Wool the public and private key sizes are roughly 36,000 bits in length.{{cite web|last=Naor|first=Dalit|title=One-Time Signatures Revisited: Practical Fast Signatures Using Fractal Merkle Tree Traversal|url=http://www.eng.tau.ac.il/~yash/Naor_Shenhav_Wool.pdf|publisher=IEEE|access-date=13 May 2014|author2=Shenhav|author3= Wool|year=2006}}

{{further|McEliece cryptosystem}}

For 128 bits of security in a McEliece scheme, The European Commission's Post-Quantum Cryptography Study group recommends using a binary Goppa code of length at least {{nowrap|1=n = 6960}} and dimension at least {{nowrap|1=k = 5413}}, and capable of correcting {{nowrap|1=t = 119}} errors. With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes {{nowrap|1=k × (n − k) = 8373911}} bits. The corresponding private key, which consists of the code support with {{nowrap|1=n = 6960}} elements from GF(2¹³) and a generator polynomial of with {{nowrap|1=t = 119}} coefficients from GF(2¹³), will be 92,027 bits in length.

The group is also investigating the use of Quasi-cyclic MDPC codes of length at least {{nowrap|1=n = 2¹⁶ + 6 = 65542}} and dimension at least {{nowrap|1=k = 2¹⁵ + 3 = 32771}}, and capable of correcting {{nowrap|1=t = 264}} errors. With these parameters the public key for the McEliece system will be the first row of a systematic generator matrix whose non-identity part takes {{nowrap|1=k = 32771}} bits. The private key, a quasi-cyclic parity-check matrix with {{nowrap|1=d = 274}} nonzero entries on a column (or twice as much on a row), takes no more than {{nowrap|1=d × 16 = 4384}} bits when represented as the coordinates of the nonzero entries on the first row.

Barreto et al. recommend using a binary Goppa code of length at least {{nowrap|1=n = 3307}} and dimension at least {{nowrap|1=k = 2515}}, and capable of correcting {{nowrap|1=t = 66}} errors. With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes {{nowrap|1=k × (n − k) = 1991880}} bits.{{cite book|title = A Panorama of Post-quantum Cryptography|publisher = Springer International Publishing|date = 2014|isbn = 978-3-319-10682-3|pages = 387–439|first1 = Paulo S. L. M.|last1 = Barreto|first2 = Felipe Piazza|last2 = Biasi|first3 = Ricardo|last3 = Dahab|first4 = Julio César|last4 = López-Hernández|first5 = Eduardo M. de|last5 = Morais|first6 = Ana D. Salina de|last6 = Oliveira|first7 = Geovandro C. C. F.|last7 = Pereira|first8 = Jefferson E.|last8 = Ricardini|editor-first = Çetin Kaya|editor-last = Koç|doi = 10.1007/978-3-319-10683-0_16}} The corresponding private key, which consists of the code support with {{nowrap|1=n = 3307}} elements from GF(2¹²) and a generator polynomial of with {{nowrap|1=t = 66}} coefficients from GF(2¹²), will be 40,476 bits in length.

{{further|Supersingular isogeny key exchange}}

For 128 bits of security in the supersingular isogeny Diffie–Hellman (SIDH) method, De Feo, Jao and Plut recommend using a supersingular curve modulo a 768-bit prime. If one uses elliptic curve point compression the public key will need to be no more than 8x768 or 6144 bits in length.{{cite web|last=De Feo|first=Luca|title=Towards Quantum-Resistant Cryptosystems From Supersingular Elliptic Curve Isogenies|url=http://eprint.iacr.org/2011/506.pdf|access-date=12 May 2014|author2=Jao|author3=Plut|archive-date=11 February 2014|archive-url=https://web.archive.org/web/20140211082622/http://eprint.iacr.org/2011/506.pdf|year=2011|url-status=bot: unknown}} A March 2016 paper by authors Azarderakhsh, Jao, Kalach, Koziel, and Leonardi showed how to cut the number of bits transmitted in half, which was further improved by authors Costello, Jao, Longa, Naehrig, Renes and Urbanik resulting in a compressed-key version of the SIDH protocol with public keys only 2640 bits in size. This makes the number of bits transmitted roughly equivalent to the non-quantum secure RSA and Diffie–Hellman at the same classical security level.{{Cite web|url = http://eprint.iacr.org/2016/229|title = Cryptology ePrint Archive: Report 2016/229|website = eprint.iacr.org|access-date = 2016-03-02}}

As a general rule, for 128 bits of security in a symmetric-key–based system, one can safely use key sizes of 256 bits. The best quantum attack against arbitrary symmetric-key systems is an application of Grover's algorithm, which requires work proportional to the square root of the size of the key space. To transmit an encrypted key to a device that possesses the symmetric key necessary to decrypt that key requires roughly 256 bits as well. It is clear that symmetric-key systems offer the smallest key sizes for post-quantum cryptography.{{citation needed|date=February 2024}}

A public-key system demonstrates a property referred to as perfect forward secrecy when it generates random public keys per session for the purposes of key agreement. This means that the compromise of one message cannot lead to the compromise of others, and also that there is not a single secret value which can lead to the compromise of multiple messages. Security experts recommend using cryptographic algorithms that support forward secrecy over those that do not.{{cite web|last1=Ristic|first1=Ivan|title=Deploying Forward Secrecy|url=https://community.qualys.com/blogs/securitylabs/2013/06/25/ssl-labs-deploying-forward-secrecy|publisher=SSL Labs|access-date=14 June 2014|date=2013-06-25}} The reason for this is that forward secrecy can protect against the compromise of long term private keys associated with public/private key pairs. This is viewed as a means of preventing mass surveillance by intelligence agencies.

Both the Ring-LWE key exchange and supersingular isogeny Diffie–Hellman (SIDH) key exchange can support forward secrecy in one exchange with the other party. Both the Ring-LWE and SIDH can also be used without forward secrecy by creating a variant of the classic ElGamal encryption variant of Diffie–Hellman.

The other algorithms in this article, such as NTRU, do not support forward secrecy as is.

Any authenticated public key encryption system can be used to build a key exchange with forward secrecy.{{cite web|url=https://crypto.stackexchange.com/a/19115 |title=Does NTRU provide Perfect Forward Secrecy?|website=crypto.stackexchange.com}}

The Open Quantum Safe (OQS) project was started in late 2016 and has the goal of developing and prototyping quantum-resistant cryptography.{{cite web|url=https://openquantumsafe.org/|title=Open Quantum Safe|website=openquantumsafe.org}}{{cite web|last1=Stebila|first1=Douglas|last2=Mosca|first2=Michele|title=Post-Quantum Key Exchange for the Internet and the Open Quantum Safe Project|url=http://eprint.iacr.org/2016/1017|website=Cryptology ePrint Archive, Report 2016/1017, 2016|access-date=9 April 2017}} It aims to integrate current post-quantum schemes in one library: liboqs.{{cite web|url=https://github.com/open-quantum-safe/liboqs|title=liboqs: C library for quantum-resistant cryptographic algorithms|date=26 November 2017|via=GitHub}} liboqs is an open source C library for quantum-resistant cryptographic algorithms. It initially focuses on key exchange algorithms but by now includes several signature schemes. It provides a common API suitable for post-quantum key exchange algorithms, and will collect together various implementations. liboqs will also include a test harness and benchmarking routines to compare performance of post-quantum implementations. Furthermore, OQS also provides integration of liboqs into OpenSSL.{{cite web|url=https://github.com/open-quantum-safe/oqs-provider/|title=oqsprovider: Open Quantum Safe provider for OpenSSL (3.x)|date=12 August 2024|via=GitHub}}

As of March 2023, the following key exchange algorithms are supported:

As of August 2024, NIST has published 3 algorithms below as FIPS standards and the 4th is expected near end of the year:{{cite web|url=https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards|title=NIST Releases First 3 Finalized Post-Quantum Encryption Standards|work=NIST |date=13 August 2024 }}

Older supported versions that have been removed because of the progression of the NIST Post-Quantum Cryptography Standardization Project are:

One of the main challenges in post-quantum cryptography is considered to be the implementation of potentially quantum safe algorithms into existing systems. There are tests done, for example by Microsoft Research implementing PICNIC in a PKI using Hardware security modules.{{Cite web|url=https://github.com/Microsoft/Picnic/blob/master/spec/design-v1.0.pdf|title=Microsoft/Picnic|website=GitHub|language=en|access-date=2018-06-27}} Test implementations for Google's NewHope algorithm have also been done by HSM vendors. In August 2023, Google released a FIDO2 security key implementation of an ECC/Dilithium hybrid signature schema which was done in partnership with ETH Zürich.{{Cite web |title=Toward Quantum Resilient Security Keys |url=https://security.googleblog.com/2023/08/toward-quantum-resilient-security-keys.html |access-date=2023-08-19 |website=Google Online Security Blog |language=en}}

The Signal Protocol uses Post-Quantum Extended Diffie–Hellman (PQXDH).

{{cite web

| url = https://signal.org/blog/pqxdh/

| title = Quantum Resistance and the Signal Protocol

| author = Ehren Kret, Rolfe Schmidt

| date = September 19, 2023

}}

On February 21, 2024, Apple announced that they were going to upgrade their iMessage protocol with a new PQC protocol called "PQ3", which will utilize ongoing keying.

{{cite web

| url = https://security.apple.com/blog/imessage-pq3

| title = iMessage with PQ3: The new state of the art in quantum-secure messaging at scale

| author = Apple Security Engineering and Architecture (SEAR)

| date = February 21, 2024

| website = Apple Security Research

| access-date = 2024-02-22

| publisher = Apple Inc.

| quote = With compromise-resilient encryption and extensive defenses against even highly sophisticated quantum attacks, PQ3 is the first messaging protocol to reach what we call Level 3 security — providing protocol protections that surpass those in all other widely deployed messaging apps.

}}

{{cite web

| url = https://www.macrumors.com/2024/02/21/apple-announces-imessage-security-upgrade/

| title = Apple Announces 'Groundbreaking' New Security Protocol for iMessage

| first = Joe

| last = Rossignoi

| date = February 21, 2024

| website = MacRumors

| access-date = 2024-02-22

}}

{{cite web

| url = https://9to5mac.com/2024/02/21/imessage-quantum-security-ios-17-4/

| title = Apple launching quantum computer protection for iMessage with iOS 17.4, here's what that means

| first = Michael

| last = Potuck

| date = February 21, 2024

| website = 9to5Mac

| access-date = 2024-02-22

}}

Apple stated that, although quantum computers don't exist yet, they wanted to mitigate risks from future quantum computers as well as so-called "Harvest now, decrypt later" attack scenarios. Apple stated that they believe their PQ3 implementation provides protections that "surpass those in all other widely deployed messaging apps", because it utilizes ongoing keying.

Apple intends to fully replace the existing iMessage protocol within all supported conversations with PQ3 by the end of 2024. Apple also defined a scale to make it easier to compare the security properties of messaging apps, with a scale represented by levels ranging from 0 to 3: 0 for no end-to-end by default, 1 for pre-quantum end-to-end by default, 2 for PQC key establishment only (e.g. PQXDH), and 3 for PQC key establishment and ongoing rekeying (PQ3).

Other notable implementations include:

• bouncycastle{{Cite web|url=https://downloads.bouncycastle.org/betas|title=Bouncy Castle Betas}}
• liboqs{{Cite web|url=https://openquantumsafe.org/liboqs/|title=Open Quantum Safe}}

File:Cloudflare Post-Quantum Key Agreement on Firefox 135.0 screenshot.webp Post-Quantum Key Agreement test page showing Firefox 135.0 using X25519MLKEM768]]

Google has maintained the use of "hybrid encryption" in its use of post-quantum cryptography: whenever a relatively new post-quantum scheme is used, it is combined with a more proven, non-PQ scheme. This is to ensure that the data are not compromised even if the relatively new PQ algorithm turns out to be vulnerable to non-quantum attacks before Y2Q. This type of scheme is used in its 2016 and 2019 tests for post-quantum TLS,{{cite web |last1=Bernstein |first1=Dainel J |title=Double encryption: Analyzing the NSA/GCHQ arguments against hybrids. #nsa #quantification #risks #complexity #costs |url=https://blog.cr.yp.to/20240102-hybrid.html|date=2024-01-02}} and in its 2023 FIDO2 key. Indeed, one of the algorithms used in the 2019 test, SIKE, was broken in 2022, but the non-PQ X25519 layer (already used widely in TLS) still protected the data. Apple's PQ3 and Signal's PQXDH are also hybrid.

The NSA and GCHQ argues against hybrid encryption, claiming that it adds complexity to implementation and transition. Daniel J. Bernstein, who supports hybrid encryption, argues that the claims are bogus.

• NIST Post-Quantum Cryptography Standardization
• Quantum cryptography – cryptography based on quantum mechanics
• Crypto-shredding – Deleting encryption keys

{{reflist}}

• [https://signal.org/docs/specifications/pqxdh/ The PQXDH Key Agreement Protocol Specification]
• {{cite book |title=Post-Quantum Cryptography |url=https://www.springer.com/mathematics/numbers/book/978-3-540-88701-0 |publisher=Springer |pages=245 |isbn=978-3-540-88701-0 |year=2008}}
• [http://ecc2011.loria.fr/slides/jao.pdf Isogenies in a Quantum World] {{Webarchive|url=https://web.archive.org/web/20140502063037/http://ecc2011.loria.fr/slides/jao.pdf |date=2014-05-02 }}
• [https://www.di.ens.fr/~pnguyen/LCD/LCD_Vadim.pdf On Ideal Lattices and Learning With Errors Over Rings]
• [http://docbox.etsi.org/Workshop/2013/201309_CRYPTO/S03_INDUSTRY_SESSION/PITNEYBOWES_PINTSOV.pdf Kerberos Revisited: Quantum-Safe Authentication]
• [https://github.com/Microsoft/Picnic/blob/master/spec/design-v1.0.pdf The picnic signature scheme]
• {{cite book |last1=Buchmann |first1=Johannes A. |last2=Butin |first2=Denis |last3=Göpfert |first3=Florian |last4=Petzoldt |first4=Albrecht |title=The New Codebreakers: Essays Dedicated to David Kahn on the Occasion of His 85th Birthday |date=2016 |publisher=Springer |isbn=978-3-662-49301-4 |pages=88–108 |chapter-url=https://link.springer.com/chapter/10.1007/978-3-662-49301-4_6?fromPaywallRec=true |language=en |chapter=Post-Quantum Cryptography: State of the Art|doi=10.1007/978-3-662-49301-4_6 }}
• {{cite journal |last1=Bernstein |first1=Daniel J. |last2=Lange |first2=Tanja |title=Post-quantum cryptography |journal=Nature |date=2017 |volume=549 |issue=7671 |pages=188–194 |doi=10.1038/nature23461|pmid=28905891 |bibcode=2017Natur.549..188B }}
• {{cite book |last1=Kumar |first1=Manoj |last2=Pattnaik |first2=Pratap |chapter=Post Quantum Cryptography(PQC) - an overview: (Invited Paper) |title=2020 IEEE High Performance Extreme Computing Conference (HPEC) |date=2020 |pages=1–9 |doi=10.1109/HPEC43674.2020.9286147|isbn=978-1-7281-9219-2 }}
• {{cite journal |last1=Campagna |first1=Matt |last2=LaMacchia |first2=Brian |last3=Ott |first3=David |title=Post Quantum Cryptography: Readiness Challenges and the Approaching Storm |date=2021 |journal=Computing Community Consortium |arxiv=2101.01269}}
• {{cite journal |last1=Yalamuri |first1=Gagan |last2=Honnavalli |first2=Prasad |last3=Eswaran |first3=Sivaraman |title=A Review of the Present Cryptographic Arsenal to Deal with Post-Quantum Threats |journal=Procedia Computer Science |date=2022 |volume=215 |pages=834–845 |doi=10.1016/j.procs.2022.12.086 |doi-access=free}}
• {{cite arXiv |last1=Bavdekar |first1=Ritik |last2=Chopde |first2=Eashan Jayant |last3=Bhatia |first3=Ashutosh |last4=Tiwari |first4=Kamlesh |last5=Daniel |first5=Sandeep Joshua |title=Post Quantum Cryptography: Techniques, Challenges, Standardization, and Directions for Future Research |date=2022 |class=cs.CR |eprint=2202.02826}}
• {{cite journal |last1=Joseph |first1=David |last2=Misoczki |first2=Rafael |last3=Manzano |first3=Marc |last4=Tricot |first4=Joe |last5=Pinuaga |first5=Fernando Dominguez |last6=Lacombe |first6=Olivier |last7=Leichenauer |first7=Stefan |last8=Hidary |first8=Jack |last9=Venables |first9=Phil |last10=Hansen |first10=Royal |title=Transitioning organizations to post-quantum cryptography |journal=Nature |date=2022 |volume=605 |issue=7909 |pages=237–243 |doi=10.1038/s41586-022-04623-2|pmid=35546191 |bibcode=2022Natur.605..237J }}
• {{cite journal |last1=Richter |first1=Maximilian |last2=Bertram |first2=Magdalena |last3=Seidensticker |first3=Jasper |last4=Tschache |first4=Alexander |title=A Mathematical Perspective on Post-Quantum Cryptography |journal=Mathematics |date=2022 |volume=10 |issue=15 |pages=2579 |doi=10.3390/math10152579 |doi-access=free}}
• {{cite journal |last1=Li |first1=Silong |last2=Chen |first2=Yuxiang |last3=Chen |first3=Lin |last4=Liao |first4=Jing |last5=Kuang |first5=Chanchan |last6=Li |first6=Kuanching |last7=Liang |first7=Wei |last8=Xiong |first8=Naixue |title=Post-Quantum Security: Opportunities and Challenges |journal=Sensors |date=2023 |volume=23 |issue=21 |pages=8744 |doi=10.3390/s23218744 |doi-access=free|pmid=37960442 |pmc=10648643 |bibcode=2023Senso..23.8744L }}
• {{cite journal |last1=Dam |first1=Duc-Thuan |last2=Tran |first2=Thai-Ha |last3=Hoang |first3=Van-Phuc |last4=Pham |first4=Cong-Kha |last5=Hoang |first5=Trong-Thuc |title=A Survey of Post-Quantum Cryptography: Start of a New Race |journal=Cryptography |date=2023 |volume=7 |issue=3 |pages=40 |doi=10.3390/cryptography7030040 |doi-access=free}}
• {{cite book |last1=Bavdekar |first1=Ritik |last2=Jayant Chopde |first2=Eashan |last3=Agrawal |first3=Ankit |last4=Bhatia |first4=Ashutosh |last5=Tiwari |first5=Kamlesh |chapter=Post Quantum Cryptography: A Review of Techniques, Challenges and Standardizations |title=2023 International Conference on Information Networking (ICOIN) |date=2023 |pages=146–151 |doi=10.1109/ICOIN56518.2023.10048976|isbn=978-1-6654-6268-6 }}
• {{cite journal |last1=Sood |first1=Neerav |title=Cryptography in Post Quantum Computing Era |journal=SSRN Electronic Journal |date=2024 |doi=10.2139/ssrn.4705470 |doi-access=free}}
• {{cite journal |last1=Rawal |first1=Bharat S. |last2=Curry |first2=Peter J. |title=Challenges and opportunities on the horizon of post-quantum cryptography |journal=APL Quantum |date=2024 |volume=1 |issue=2 |doi=10.1063/5.0198344 |doi-access=free}}
• {{cite journal |last1=Bagirovs |first1=Emils |last2=Provodin |first2=Grigory |last3=Sipola |first3=Tuomo |last4=Hautamäki |first4=Jari |title=Applications of Post-quantum Cryptography |journal=European Conference on Cyber Warfare and Security |date=2024 |volume=23 |issue=1 |pages=49–57 |doi=10.34190/eccws.23.1.2247 |arxiv=2406.13258}}
• {{cite arXiv |last1=Mamatha |first1=G S |last2=Dimri |first2=Namya |last3=Sinha |first3=Rasha |title=Post-Quantum Cryptography: Securing Digital Communication in the Quantum Era |date=2024 |class=cs.CR |eprint=2403.11741}}
• {{cite book |last1=Singh |first1=Balvinder |last2=Ahateshaam |first2=Md |last3=Lahiri |first3=Abhisweta |last4=Sagar |first4=Anil Kumar |chapter=Future of Cryptography in the Era of Quantum Computing |title=Innovations in Electrical and Electronic Engineering |series=Lecture Notes in Electrical Engineering |date=2024 |volume=1115 |pages=13–31 |doi=10.1007/978-981-99-8661-3_2|isbn=978-981-99-8660-6 }}

• [http://www.pqcrypto.org/ PQCrypto, the post-quantum cryptography conference]
• [http://www.etsi.org/news-events/news/947-2015-03-news-etsi-launches-quantum-safe-cryptography-specification-group ETSI Quantum Secure Standards Effort]
• [http://csrc.nist.gov/groups/ST/post-quantum-crypto/ NIST's Post-Quantum crypto Project]
• [https://ianix.com/pqcrypto/pqcrypto-deployment.html PQCrypto Usage & Deployment]
• [https://www.siscertifications.com/iso-27001-certification/ ISO 27001 Certification Cost]
• [https://pacificcert.com/iso-22301-2019-security-and-resilience-in-the-united-states/ ISO 22301:2019 – Security and Resilience in the United States]

{{Quantum mechanics topics}}

{{quantum information}}

Category:Cryptography