Lattice-Based Cryptography

How long does the BKZ algorithm run? What sounds like a rather niche question only of interest to theoretical computer scientists, is in fact a central open problem that needs to be resolved in order to keep the digital economy and private life safe. While largely hidden from view, cryptography underpins many aspects of modern life such as commerce, banking, governance or long distance personal communication. The cryptographic schemes securing digital communication, in turn, rely on one of two hard mathematical problems at their core. However, these mathematical problems, while still difficult to solve on a normal computer, are, in fact, easy to solve on a quantum computer. That is, in 1994, Peter Shor presented an algorithm for solving these problems - factoring and discrete logarithms - efficiently, essentially regardless of how big we choose parameters, i.e. he found a polynomial-time algorithm on a quantum computer.

To date, nobody has announced a sufficiently big quantum computer to run Shor's algorithm for any non-trivial problem and it remains unclear if it is at all possible. Still, recent theoretical and practical progress in the area of quantum computing has many people concerned. One motivation is the following scenario: an attacker could collect encrypted traffic now and store it until sufficiently big quantum computers are available. Once this is the case, the attacker can use their capabilities to decrypt the stored ciphertexts. Thus, if encryption ought to provide security well into the future, it might be under threat already by quantum computers ... even if they do not exist yet. Some estimates foresee the first quantum computer powerful enough to break real RSA keys for as early as 2030. On the other hand, the adoption of new cryptography often takes decades. Thus, the time to address this problem is now.

A second challenge for current generation cryptography is changes in usage pattern. In recent years, cloud services became increasingly relevant. These brought with them significant privacy challenges as these services rely on having access to personal data to add value. Ideally, we would like to utilise the power of third-party services without handing over sensitive private data.

For both of these challenges, lattice-based cryptography is a key building block to resolving them. That is, from hard lattice problems we can build cryptosystems which are believed to be secure even against quantum attackers. These cryptosystems also enable to compute with encrypted data also known as "fully homomorphic encryption". In both of these areas, standardisation efforts are currently underway to enable widespead adoption of these schemes.

However, before we can do that, we need to refine our understanding of how long it would take an attacker to break these schemes. Practical cryptographic schemes are never unconditionally secure, but they are "secure enough" where "secure enough" can mean different things depending on the desired performance/security trade-off. Thus, we want to make sure that it would take too long to be feasible while not picking our parameters so big to slow down our communications unduly. To answer this question "How long would it taken for an attacker to break the next generation of encryption schemes" is the same as the initial question - "How long does the BKZ algorithm take to run?" - since the BKZ algorithm is the preeminent algorithm with which an attacker would attempt break latticed-based cryptography. Currently, the cryptographic community disagrees on the true cost of this algorithm. Thus, this project sets out to resolve this question so that we can deploy the next generation of cryptography with confidence.

This research is concerned with establishing the security of post-quantum constructions to replace e.g. RSA and discrete-logarithm based schemes. Such alternatives are currently being sought by standardisation bodies such as NIST in the US and ETSI in 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.

Thus, 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 and by engaging in the standardisation process itself, e.g. through attending and contributing to the relevant meetings.

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.

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.