Post-Quantum Cryptography Standardization

Short description: Project by NIST to standardize post-quantum cryptography

Post-Quantum Cryptography Standardization is a project by NIST to standardize post-quantum cryptography.[1] 23 signature schemes were submitted, 59 encryption/KEM schemes were submitted[2] by the initial submission deadline at the end of 2017, of which 69 total were deemed complete and proper and participated in the first round. 26 of these have advanced to the second round (17 encryption/key-establishment and 9 signature schemes).

## Contents

* 1 Background
* 2 Round One
* 2.1 Round One submissions published attacks
* 3 Round Two
* 4 Round Three
* 5 See also
* 6 References
* 7 External links

## Background

A NIST published report from April 2016 cites experts that acknowledge the possibility of quantum technology to render the commonly used RSA algorithm insecure by 2030.[3] As a result, a need to standardize quantum-secure cryptographic primitives arose. Since most symmetric primitives are relatively easy to modify in a way that makes them quantum resistant, efforts have focused on public-key cryptography, namely digital signatures and key encapsulation mechanisms. In December 2016 NIST initiated a standardization process by announcing a call for proposals.[4]

The competition is now in its second round out of expected three, where in each round some algorithms are discarded and others are studied more carefully. NIST hopes to publish the standardization documents by 2024, but may speed up the process if major breakthroughs in quantum computing are made.

It is currently undecided whether the future standards be published as FIPS or as NIST Special Publication (SP).

## Round One

Under consideration were:[5]
( ~~strikethrough~~ means it had been withdrawn)

Type  | PKE/KEM  | Signature  | Signature & PKE/KEM

|
|
|

Lattice  |

* Compact LWE
* CRYSTALS-KYBER
* Ding Key Exchange
* EMBLEM and R.EMBLEM
* FrodoKEM
* ~~HILA5~~ (withdrawn and merged into Round5)
* KCL (pka OKCN/AKCN/CNKE)
* KINDI
* LAC
* LIMA
* Lizard
* LOTUS
* NewHope
* NTRUEncrypt[6]
* NTRU-HRSS-KEM
* NTRU Prime
* Odd Manhattan
* ~~Round2~~ (withdrawn and merged into Round5)
* Round5 (merger of Round2 and Hila5, announced 4 August 2018)[7]
* SABER
* Three Bears
* Titanium

* CRYSTALS-DILITHIUM
* DRS
* FALCON
* pqNTRUSign[6]
* qTESLA

Code-based  |

* BIG QUAKE
* BIKE
* Classic McEliece
* DAGS
* ~~Edon-K~~
* HQC
* ~~LAKE~~ (withdrawn and merged into ROLLO)
* LEDAkem
* LEDApkc
* Lepton
* ~~LOCKER~~ (withdrawn and merged into ROLLO)
* McNie
* NTS-KEM
* ROLLO (merger of Ouroboros-R, LAKE and LOCKER) [8]
* ~~Ouroboros-R~~ (withdrawn and merged into ROLLO)
* QC-MDPC KEM
* Ramstake
* RLCE-KEM
* RQC

* pqsigRM
* RaCoSS
* ~~RankSign~~

Hash-based  |  |

* Gravity-SPHINCS
* SPHINCS+

Multivariate  |

* CFPKM
* Giophantus

* DualModeMS
* GeMSS
* Gui
* HiMQ-3
* LUOV
* MQDSS
* Rainbow

* ~~SRTPI~~
* DME

Braid group  |  |

* WalnutDSA

Supersingular Elliptic Curve Isogeny  |

* SIKE

|  |
Satirical submission  |  |  |

* pqRSA[9][10]

Other  |

* Guess Again
* ~~HK17~~
* Mersenne-756839
* ~~RVB~~

* Picnic

### Round One submissions published attacks

* Guess Again by Lorenz Panny [11]
* RVB by Lorenz Panny[12]
* RaCoSS by Daniel J. Bernstein, Andreas Hülsing, Tanja Lange and Lorenz Panny[13]
* HK17 by Daniel J. Bernstein and Tanja Lange[14]
* SRTPI by Bo-Yin Yang[15]
* WalnutDSA
* by Ward Beullens and Simon R. Blackburn[16]
* by Matvei Kotov, Anton Menshov and Alexander Ushakov[17]
* DRS by Yang Yu and Léo Ducas [18]
* DAGS by Elise Barelli and Alain Couvreur[19]
* Edon-K by Matthieu Lequesne and Jean-Pierre Tillich[20]
* RLCE by Alain Couvreur, Matthieu Lequesne, and Jean-Pierre Tillich[21]
* Hila5 by Daniel J. Bernstein, Leon Groot Bruinderink, Tanja Lange and Lorenz Panny[22]
* Giophantus by Ward Beullens, Wouter Castryck and Frederik Vercauteren[23]
* RankSign by Thomas Debris-Alazard and Jean-Pierre Tillich [24]
* McNie by Philippe Gaborit [25]; Terry Shue Chien Lau and Chik How Tan [26]

## Round Two

Candidates moving on to the second round were announced on January 30, 2019. They are:[27]

Type  | PKE/KEM  | Signature

|
|

Lattice  |

* CRYSTALS-KYBER[28]
* FrodoKEM[29]
* LAC
* NewHope[30]
* NTRU (merger of NTRUEncrypt and NTRU-HRSS-KEM)[6]
* NTRU Prime[31]
* Round5 (merger of Round2 and Hila5, announced 4 August 2018)[7]
* SABER[32]
* Three Bears[33]

* CRYSTALS-DILITHIUM[28]
* FALCON[34]
* qTESLA[35]

Code-based  |

* BIKE[36]
* Classic McEliece
* HQC[37]
* LEDAcrypt (merger of LEDAkem[38] and LEDApkc[39])
* NTS-KEM[40]
* ROLLO (merger of Ouroboros-R, LAKE and LOCKER) [8]
* RQC[41]

Hash-based  |  |

* SPHINCS+[42]

Multivariate  |  |

* GeMSS[43]
* LUOV[44]
* MQDSS[45]
* Rainbow

Supersingular Elliptic Curve Isogeny  |

* SIKE[46]

Zero-knowledge proofs  |  |

* Picnic[47]

## Round Three

Albeit unplanned at first, it is likely that NIST will hold a third round in June 2020. By that point NIST will have selected fewer schemes and focus on standardization efforts[48]. The work is expected to end and draft standards made publicly available between 2022 and 2024.[49]

## See also

* Advanced Encryption Standard process
* NIST hash function competition

## References

1. ↑ "Post-Quantum Cryptography Standardization - Post-Quantum Cryptography". 3 January 2017. https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization. Retrieved 31 January 2019.
2. ↑ "Archived copy". https://post-quantum.ch/#.
3. ↑ "NIST Released NISTIR 8105, Report on Post-Quantum Cryptography". https://csrc.nist.gov/News/2016/NIST-Released-NISTIR-8105,-Report-on-Post-Quantum. Retrieved 5 November 2019.
4. ↑ "NIST Asks Public to Help Future-Proof Electronic Information". https://www.nist.gov/news-events/news/2016/12/nist-asks-public-help-future-proof-electronic-information. Retrieved 5 November 2019.
5. ↑ Computer Security Division, Information Technology Laboratory (3 January 2017). "Round 1 Submissions - Post-Quantum Cryptography - CSRC". https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions. Retrieved 31 January 2019.
6. ↑ 6.0 6.1 6.2 "Archived copy". https://www.onboardsecurity.com/nist-post-quantum-crypto-submission.
7. ↑ 7.0 7.1 "Google Groups". https://groups.google.com/a/list.nist.gov/forum/#!topic/pqc-forum/YsGkKEJTt5c. Retrieved 31 January 2019.
8. ↑ 8.0 8.1 "ROLLO". http://www.pqc-rollo.org/. Retrieved 31 January 2019.
9. ↑ RSA using 231 4096-bit primes for a total key size of 1 TiB. "Key almost fits on a hard drive" Bernstein, Daniel (2010-05-28). "McBits and Post-Quantum RSA". http://cr.yp.to/talks/2010.05.28/slides.pdf#page=29.
10. ↑ Bernstein, Daniel; Heninger, Nadia (2017-04-19). "Post-quantum RSA". https://cr.yp.to/papers/pqrsa-20170419.pdf.
11. ↑ "Dear all, the following Python script quickly recovers the message from a given "Guess Again" ciphertext without knowledge of the private key". https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/guess-again-official-comment.pdf. Retrieved 30 January 2019.
12. ↑ Panny, Lorenz (25 December 2017). "Fast key recovery attack against the "RVB" submission to #NISTPQC: t …. Computes private from public key.". Twitter. https://twitter.com/yx7__/status/945283780851400704. Retrieved 31 January 2019.
13. ↑ "Archived copy". https://helaas.org/racoss/.
14. ↑ "Archived copy". https://helaas.org/hk17/.
15. ↑ "Dear all, We have broken SRTPI under CPA and TPSig under KMA.". https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/SRTPI-official-comment.pdf. Retrieved 30 January 2019.
16. ↑ Beullens, Ward; Blackburn, Simon R. (2018). Practical attacks against the Walnut digital signature scheme. https://eprint.iacr.org/2018/318.
17. ↑ Kotov, Matvei; Menshov, Anton; Ushakov, Alexander (2018). AN ATTACK ON THE WALNUT DIGITAL SIGNATURE ALGORITHM. https://eprint.iacr.org/2018/393.
18. ↑ Yu, Yang; Ducas, Léo (2018). Learning strikes again: the case of the DRS signature scheme. https://eprint.iacr.org/2018/294.
19. ↑ Barelli, Elise; Couvreur, Alain (2018). "An efficient structural attack on NIST submission DAGS". arXiv:1805.05429 [cs.CR].
20. ↑ Lequesne, Matthieu; Tillich, Jean-Pierre (2018). "Attack on the Edon-K Key Encapsulation Mechanism". arXiv:1802.06157 [cs.CR].
21. ↑ Couvreur, Alain; Lequesne, Matthieu; Tillich, Jean-Pierre (2018). "Recovering short secret keys of RLCE in polynomial time". arXiv:1805.11489 [cs.CR].
22. ↑ Bernstein, Daniel J.; Groot Bruinderink, Leon; Lange, Tanja; Lange, Lorenz (2017). Hila5 Pindakaas: On the CCA security of lattice-based encryption with error correction. https://eprint.iacr.org/2017/1214.
23. ↑ "Official Comments". 13 September 2018. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/Giophantus-official-comment.pdf.
24. ↑ Debris-Alazard, Thomas; Tillich, Jean-Pierre (2018). "Two attacks on rank metric code-based schemes: RankSign and an Identity-Based-Encryption scheme". arXiv:1804.02556 [cs.CR].
25. ↑ "I am afraid the parameters in this proposal have at most 4 to 6‐bits security under the Information Set Decoding (ISD) attack.". https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/McNie-official-comment.pdf. Retrieved 30 January 2019.
26. ↑ Lau, Terry Shue Chien; Tan, Chik How (31 January 2019). "Key Recovery Attack on McNie Based on Low Rank Parity Check Codes and Its Reparation". Advances in Information and Computer Security. Lecture Notes in Computer Science. 11049. Springer International Publishing. pp. 19–34. doi:10.1007/978-3-319-97916-8_2. ISBN 978-3-319-97915-1.
27. ↑ Computer Security Division, Information Technology Laboratory (3 January 2017). "Round 2 Submissions - Post-Quantum Cryptography - CSRC". https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions. Retrieved 31 January 2019.
28. ↑ 28.0 28.1 Schwabe, Peter. "CRYSTALS". https://pq-crystals.org/. Retrieved 31 January 2019.
29. ↑ "FrodoKEM". https://frodokem.org/. Retrieved 31 January 2019.
30. ↑ Schwabe, Peter. "NewHope". https://newhopecrypto.org/. Retrieved 31 January 2019.
31. ↑ "Archived copy". https://ntruprime.cr.yp.to/.
32. ↑ "SABER". https://www.esat.kuleuven.be/cosic/pqcrypto/saber/index.html. Retrieved 17 June 2019.
33. ↑ "ThreeBears". https://sourceforge.net/projects/threebears/. Retrieved 31 January 2019.
34. ↑ "Falcon". https://falcon-sign.info/. Retrieved 26 June 2019.
35. ↑ "qTESLA – Efficient and post-quantum secure lattice-based signature scheme". https://qtesla.org/. Retrieved 31 January 2019.
36. ↑ "BIKE - Bit Flipping Key Encapsulation". https://bikesuite.org/. Retrieved 31 January 2019.
37. ↑ "HQC". http://pqc-hqc.org/. Retrieved 31 January 2019.
38. ↑ "LEDAkem Key Encapsulation Module". https://www.ledacrypt.org/LEDAkem/. Retrieved 31 January 2019.
39. ↑ "LEDApkc Public Key Cryptosystem". https://www.ledacrypt.org/LEDApkc/. Retrieved 31 January 2019.
40. ↑ "Archived copy". https://nts-kem.io/.
41. ↑ "RQC". http://pqc-rqc.org/. Retrieved 31 January 2019.
42. ↑ [1]
43. ↑ "Archived copy". https://www-polsys.lip6.fr/Links/NIST/GeMSS.html.
44. ↑ "LUOV -- An MQ signature scheme". https://www.esat.kuleuven.be/cosic/pqcrypto/luov/. Retrieved 22 January 2020.
45. ↑ "MQDSS post-quantum signature". http://mqdss.org/. Retrieved 31 January 2019.
46. ↑ "SIKE – Supersingular Isogeny Key Encapsulation". http://sike.org/. Retrieved 31 January 2019.
47. ↑ "Picnic. A Family of Post-Quantum Secure Digital Signature Algorithms". https://microsoft.github.io/Picnic/. Retrieved 26 February 2019.
48. ↑ "Some announcements". https://groups.google.com/a/list.nist.gov/forum/#!topic/pqc-forum/-rKSOqFAQeI. Retrieved 6 October 2019.
49. ↑ "NIST Workshops and Timeline". https://csrc.nist.gov/Projects/post-quantum-cryptography/workshops-and-timeline. Retrieved 6 October 2019.

## External links

* Post-quantum cryptography website by djb
* First round candidates by field by Ryo Fujita
* First round candidates by field (revised)
* First round candidates by field (revised again)

0.00

(0 votes)

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Post-Quantum_Cryptography_Standardization&oldid=228248"