DOI: 10.17587/prin.10.344-352

An Overview of the History and Trends of Post-Quantum Cryptography based on the Lattice Theory

A. V. Komarova, piter-ton@mail.ru, St. Petersburg National Research University of Information Technologies, Mechanics and Optics, St. Petersburg, 197101, Russian Federation, A. G. Korobeynikov, korobeynikov_a_g@mail.ru, Institute of Terrestrial Magnetism, Ionosphere and Radio Wave Propagation of the Russian Academy of Sciences St.-Petersburg Filial, St. Petersburg, 199034, Russian Federation

Corresponding author: Komarova Antonina V., Postgraduate Student, St. Petersburg National Research University of Information Technologies, Mechanics and Optics, St. Petersburg, 197101, Russian Federation, E-mail: piter-ton@mail.ru

Every year quantum computing and quantum computer becomes more and more actual topic of the world scientific researches. In case of its appearance such а device will be able to compromise most of the asymmetric schemes used today. To ensure а proper level of security in single-key (symmetric) schemes and hash functions organizations will have to use so long keys and hash values, respectively, that will make it impossible to realize such schemes in real information and communication systems. The post-quantum cryptography began to rapidly develop after the sensational appearance of quantum Shors algorithm in 1994. This direction includes a number of approaches, however from the authors point of view, the most promising approach is a lattices-based cryptography. Unfortunately, in the Russian literature there are very few manuals devoted to post-quantum cryptography, in particular the lattice theory. The goal of this article is to fill this gap. The article deals with the main provisions, definitions and main lattice problems. The background information about the history as well as the latest trends is given. The studied question is relevant because the most part of popular cryptographic protocols, schemes and algorithms based on the number theory will become unsecure in the case of the quantum computer appearance.

Keywords: cryptography, post-quantum cryptography, lattices-based cryptography, shortest vector problem, closest vector problem, learning with errors problem, short integer solution problem, public-key cryptography, qTESLA, CRYSTALS-DILITHIUM, FALCON

pp. 344–352.

For citation:
Komarova A. V., Korobeynikov A. G. An Overview of the History and Trends of Post-Quantum Cryptography based on the Lattice Theory, Programmnaya Ingeneria, 2019, vol. 10, no. 7—8, pp. 344—352.

The work was supported by the National Research University of Information Technologies, Mechanics and Optics project nos. 619296 "Development of methods for the creation and implementation of cyberphysical systems"