Abstract:

There are two computationally hard problems that justify the security of the currently used asymmetric cryptographic schemes, namely the integer factorization problem and the discrete logarithm problem (DLP). Fast growth of sophisticated quantum technologies brings us closer to the emergence of so highly efficient quantum computers that each of these problems will be trivially simple. This is because the famous Shor’s algorithm [12] is able to factor an integer, or find a solution to DLP within polynomial time (degree is less by 3). As a consequence of this facts, we see there is an urgent need to develop and implement a new generation of asymmetric schemes that are, first and foremost, resistant to classical and quantum attacks. To this end, National Institute of Standards and Technologies (NIST) of the United States began a competition to create a post-quantum cryptographic standard in 2016. The idea was to standardize on both a public-key encryption and digital signature algorithm that is resistant to quantum computing. In 2017, NIST presented a list of sixty-nine submissions to be Round 1 candidates. Twenty-six advanced to Round 2 in 2019, and seven (plus another eight alternates) were announced as Round 3 finalists in 2020. On the 5th of July 2022, NIST released the announcement on the finalization of the 3rd round of the competition, and have chosen the following four algorithms: CRYSTALSKyber for Key Encapsulation Mechanism (KEM) and CRYSTALS-Dilithium, Falcon, and SPHINCS+ for digital signatures. It is worth to notice that among these algorithms, all but one are based on lattice theory. All of this only strengthens the common faith that the lattice is the most reliable, stable and flexible source of security for modern public key schemes.