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.
|