Bridging the Gap Between Lattice Coding and Lattice Cryptography - Post-Quantum Cryptography

点击翻译按钮获取中文摘要

Lattices play an important role in various areas of engineering and computer science. In coding theory, lattice codes bring significant advantages such as concrete implementation and complexity reduction, thus overcoming the limitation of random codes in practical applications. More recently, it became widely appreciated that algebraic structures of lattice codes greatly facilitate coordination among multiple users in wireless networks.In a world where quantum computers exist, current public key cryptographic schemes will become vulnerable to attacks that exploit the nature of quantum mechanics. This is a central concern to our modern data-driven society, which has been extensively considered by governments, companies and research institutions. For instance, the National Institute of Standards and Technology (NIST, USA) launched in 2016 a call for the standardisation of quantum-resistant cryptography. Among the prospective methods which are expected to be implemented for post-quantum cryptography, lattice-based cryptography figures as a front runner. This form of cryptography explores the theory of lattices and the hardness of lattice-related problems to build primitives such as encryption schemes, one-way functions, digital signatures and fully-homomorphic encryption.While both lattice coding and lattice cryptography are concerned with the same mathematical objects --- lattices --- they consider these objects from disparate vantage points. Coding theory uses lattices to protect correctness against noise, whereas cryptography adds noise to protect security. As a consequence, both fields ask different questions of lattices: coding theory is mainly concerned with lattices that are easy to decode, whereas cryptography is focused on lattices that are hard.Despite these different perspectives, lattice coding has a lot to contribute to lattice cryptography. Firstly, in order to encrypt messages we need to encode them and the more efficient our coding schemes, the smaller will be our ciphertexts. This is particularly relevant since the size of ciphertexts is one of the key drawbacks of lattice-based cryptography. That is, these schemes are typically very fast but produce large ciphertexts. Secondly, lattice coding has and can be used to improve the security analysis of lattice-based cryptography. In this area, we study algorithms for breaking cryptographic schemes so that we can pick parameters in such a way to avoid such attacks.