The US National Institute of Standards and Technology (NIST) has announced the winners of the competition for crypto algorithms resistant to selection on a quantum computer. The competition was organized six years ago and is aimed at choosing post-quantum cryptography algorithms suitable for promotion as standards. During the competition, the algorithms proposed by international research teams were studied by independent experts for possible vulnerabilities and weaknesses.
The winner among the universal algorithms that can be used to protect the transmission of information in computer networks is CRYSTALS-Kyber, whose strengths are a relatively small key size and high speed. CRYSTALS-Kyber is recommended for conversion to standards. In addition to CRYSTALS-Kyber, four more general-purpose algorithms have been identified - BIKE, Classic McEliece, HQC and SIKE, which need to be improved. The authors of these algorithms are given the opportunity to update the specifications and eliminate shortcomings in the implementations until October 1, after which they can also be included in the finalists.
Of the algorithms aimed at working with digital signatures, CRYSTALS-Dilithium, FALCON and SPHINCS+ have been singled out. The CRYSTALS-Dilithium and FALCON algorithms are highly efficient. CRYSTALS-Dilithium is recommended as the primary algorithm for digital signatures, while FALCON is focused on solutions that require a minimum signature size. SPHINCS+ lags behind the first two algorithms in terms of signature size and speed, but it was left among the finalists as a fallback option, since it is based on fundamentally different mathematical principles.
In particular, the CRYSTALS-Kyber, CRYSTALS-Dilithium and FALCON algorithms use cryptography methods based on solving problems of lattice theory, the solution time of which does not differ on ordinary and quantum computers. The SPHINCS+ algorithm uses hash-based cryptography techniques.
The universal algorithms left for revision are also based on other principles - BIKE and HQC use elements of algebraic coding theory and linear codes, which are also used in error correction schemes. NIST intends to further standardize one of these algorithms to provide an alternative to the already chosen lattice theory-based CRYSTALS-Kyber algorithm. The SIKE algorithm is based on the use of supersingular isogeny (circling in a supersingular isogeny graph) and is also considered as a candidate for standardization, since it has the smallest key size. The Classic McEliece algorithm is among the finalists, but will not yet be standardized due to the very large size of the public key.
The need to develop and standardize new cryptographic algorithms is due to the fact that quantum computers, which have been actively developing recently, solve the problems of decomposing a natural number into prime factors (RSA, DSA) and discrete logarithm of elliptic curve points (ECDSA), which underlie modern asymmetric encryption algorithms by public keys and are not effectively solvable on classical processors. At the current stage of development, the capabilities of quantum computers are not yet enough to break the current classical encryption algorithms and digital signatures based on public keys, such as ECDSA, but it is assumed that the situation may change within 10 years and it is necessary to prepare the basis for the transfer of cryptosystems to new standards.
Source: opennet.ru