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.

This research is concerned with the security and efficiency of post-quantum constructions to replace e.g. RSA and discrete-logarithm based schemes. Such alternatives are currently being sought after by standardisation bodies such as NIST in the US and ETSI in the EU. In particular, NIST is currently evaluating post-quantum candidates and NIST cryptographic standards have previously become de facto world-wide standards (e.g. AES, SHA-3). A strong contender in this area are lattice-based schemes. Similarly, homomorphic encryption (computing with encrypted data) is in the process of being standardised after having seen a rapid speed of innovation since the first proposal was published in 2009.

The primary impact of this research will be to inform these standardisation processes which will decide on the next generation of cryptographic schemes. Through this mediation, this research will impact public-key cryptography in the long term. Impact in this regard will be achieved by publishing in high-profile academic venues which are currently being watched closely by standards bodies. Specifically, we envisage both the message encoding scheme and novel attacks to be developed in this project would impact the NIST process.

Government bodies will be impacted by the research performed here as it will provide material for their own security evaluation of post-quantum and homomorphic candidates (cf.~letter of support by NCSC).

End-users will be affected when the security mechanisms in their devices and software products changes. However, it is expected that on a high-level their user experience will not change, i.e. cryptography usually works hidden from view of the average users.