Public-key cryptosystems (PKC) based on codes, lattices and LPN
Grigory Kabatyansky
Skolkovo Institute of Science and Technology (Skoltech), Moscow
In this lecture we will describe the main constructions of code-based cryptography, starting from famous McEliece scheme. We discuss why we believe that this scheme is safe and why, in fact, our belief is too optimistic. We suggest a novel PKC which is more close to be considered as safe. At the end we briefly discuss similarities be-tween codes, lattices and LPN (learning parities with noise), and how to move re-sults from coding theory to lattices and vice versa. The main element of our ap-proach is a design of codes which we can decode effectively beyond GV-bound.
Grigory Kabatiansky received the PhD degree in Theoretical Informatics in 1979. His probably mostly known result is so-called Kabatiansky-Levenshtein theory, see Chapter 9 J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups , 3rd ed. Springer-Verlag, New York-Berlin, 1999.
He worked for more than quarter of a century at the Institute for Information Transmission Problems, where such famous in information and coding theory scien-tists as Dobrushin, Pinsker, Zyablov, Zinoviev, Bassalygo work or worked. From 2016 Grigory works at the newly established university Skoltech.