oa Lattices are Good for Communication, Security, and Almost Everything

Mathematicians considered lattices as early as the first half of the nineteenth century, e.g. Johann Carl Friedrich Gauss and Joseph-Louis Lagrange explored point lattices in small dimensions. After the pioneering work of Hermann Minkowski around 1900, lattices were extensively studied in the twentieth century until engineering applications in the areas of digital communications, data compression, and cryptography were recently discovered. Nowadays it is admitted that lattices are good for almost everything, including many new fields such as physical-layer security, post-quantum cryptographic primitives, and coding for wireless mobile channels.

In this talk, after introducing the mathematical background for point lattices in multi-dimensional Euclidean spaces, we shall describe how lattices are used to guarantee reliable and secure communications. The talk will include strong technical material but it is intended to a large audience including engineers and scientists from all areas. The talk shall also present new results on lattices found in Qatar under projects NPRP 6-784-2-329 and NPRP 5-597-2-241 funded by QNRF.

Lattices are mathematical structures with specific algebraic and topological properties. We consider the simplest form of lattices, i.e. lattices in real Euclidean spaces equipped with the standard scalar product. In communication theory, lattices can play different roles in the processing and the transmission of information. They are suitable for vector quantization of analog sources, for channel coding as coded modulations, and also for joint source-channel coding. In the recent literature, lattices are found to be good tools in network coding and secure coding at the physical layer. More information on lattice for communications can be found in [1] and references therein. A lattice is a Z-module of the Euclidean vector space R^N or equivalently it is a discrete additive subgroup of R^N. A new family of lattices, referred to as Generalized Low-Density Lattices (GLD) was built in Qatar. GLD lattices are obtained by Construction A from non-binary GLD codes. Their impressive performance and analysis can be found in [2].

In his seminal paper [3], Miklos Ajtai showed how lattices could be used as cryptographic primitives. Since Ajtai's result, lattice-based cryptography became very popular in the cryptography community. One important area is Learning With Errors (LWE), see [4]. LWE is a clear example of elementary mathematical problem with an algorithmically complex solution. Thanks to its intrinsic connection with lattice-based problems that are known to be hard also for quantum algorithms, LWE has raised much interest in the last decade, it is part of the so-called post-quantum cryptography. Another area in lattice-based cryptography is GGH. This is the first McEliece-like scheme for lattices, referred to as GGH cryptosystem, and was proposed by Goldreich, Goldwasser, and Halevi in 1997. GGH is a lattice equivalent of the McEliece cryptosystem based on error-correcting codes. Many other cryptosystems based on lattices were investigated and proposed by several researchers. In this talk, after presenting how lattices are used for reliable communications, we also present how lattices are used to secure data communications. The attached slides constitute a draft mainly focusing on the communication aspects of lattices. These slides will be completed by a second part on security based on lattices.

[1] R. Zamir, Lattice Coding for Signals and Networks, Cambridge, 2014.

[2] J.J. Boutros, N. di Pietro, and Y.C. Huang, “Spectral thinning in GLD lattices”, Information Theory and Applications Workshop (ITA), La Jolla, pp. 1-9, Feb. 2015. Visit http://www.ita.ucsd.edu/workshop/15/files/paper/paper_31.pdf

[3] M. Ajtai, “Generating Hard Instances of Lattice Problems,” Proc. of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 99-108. doi:10.1145/237814.237838, 1996.

[4] V. Lyubashevsky, C. Peikert, and O. Regev, “A Toolkit for Ring-LWE Cryptography,” in EUROCRYPT, pp. 35-54, 2013.