Hello, Habr. Recently, NIST announced on its website the start of the third phase of standardization of post-quantum cryptography . 3 candidates for digital signature and 4 candidates for asymmetric encryption passed to the third stage. 8 alternative candidates were also presented. I thought that the Khabrovites would be interested in this event. More details under the cut.
A bit of history
The idea of ββquantum computing was first proposed in the early 1980s to simulate complex quantum mechanical systems. It soon turned out that quantum computing could provide tremendous speed-ups for other problems, such as factorizing numbers and discrete logarithms in a group of points on an elliptic curve.
This has become a significant problem for cryptography, since the security of common standardized systems depends on the complexity of solving these problems.
Nevertheless, quantum computing for quite a long time remained just a beautiful abstraction that was not technically possible to implement. But recently, the possibility of creating quantum computers has been revised and this has prompted NIST to launch an open competition in 2016 to create new post-quantum standards. More specifically, NIST is interested in creating new standards for Public-Key Encryption and Digital Signatures.
69 teams from all over the world applied for participation in the competition. This topic was widely covered and there were even posts on HabrΓ©. Of the proposed schemes, only 26 passed to the second stage. And so, on July 22, 2020, the finalists of the second stage were announced, who went on. Only 4 candidates for asymmetric encryption and 3 candidates for digital signature remain.
Candidates who have passed to the third stage
So, the candidates for the new post-quantum digital signature standard are:
- CRYSTALS-DILITHIUM - Representative of lattice cryptography. It is based on the Fiat-Shamir circuit with interruptions. Cryptanalysis is reduced to solving the problems Module-LWE and Module-SIS. It has good performance and can be effectively implemented on low-resource devices. NIST asked the authors to add a set of system-wide parameters for security level 5.
- FALCON β . GPV. SIS NTRU-. . , , .
- Rainbow β . UOV. . - , .
NIST CRYSTALS-DILITHIUM FALCON . , . Rainbow.
:
- Classic McEliece β . 1979 . , . - , Rainbow .
- CRYSTALS-KYBER β . Module-LWE. -. , NIST , Module-LWE β .
- NTRU β . NTRUEncryt, 20 . NTRU, Module-LWE ( ) , .
- SABER β . MLWR (Module-LWE,
). -, CRYSTALS-KYBER.
, β . NIST , (CRYSTALS-KYBER, NTRU, SABER) .
NIST 8 , , .
:
- SPHINCS+ Picnic β . SPHINCS+ -, Picnic NIZK . . , .
- GeMSS β Rainbow, HFE, UOV. . Rainbow.
:
- BIKE β . .
- FrodoKEM β . LWE, Module-LWE ( ). \.
- HQC β . . \.
- NTRU Prime β . .
- SIKE β ( ), . .
Over the past four years, NIST has analyzed proposed post-quantum circuits from around the world. Among the proposed schemes, the dominant position is occupied by lattice schemes. But they (like other areas) require more detailed study. NIST plans to conduct a detailed analysis of the remaining candidates over the next 3 years.
It is worth noting that there are already standardized lattice schemes in the world: one , two . So, most likely, it is cryptography on lattices that in the coming years will increasingly displace the usual RSA and ECDSA. But at the same time, other solutions will be popular in highly specialized areas.