Lattice-Based Cryptography

BKZ算法运行多长时间？这个听起来只是理论上的计算机科学家感兴趣的小众问题，实际上是一个核心的悬而未决的问题，为了确保数字经济和私人生活的安全，需要解决这个问题。虽然密码学在很大程度上隐藏在人们的视线之外，但它支撑着现代生活的许多方面，如商业、银行、治理或长途个人通信。保护数字通信的加密方案反过来又依赖于其核心的两个数学难题中的一个。然而，这些数学问题虽然在普通计算机上仍然很难解决，但实际上在量子计算机上很容易解决。也就是说，1994年，Peter Shor提出了一种算法来高效地解决这些问题--因式分解和离散对数--基本上无论我们选择多大的参数，也就是说，他在量子计算机上发现了一个多项式时间算法。到目前为止，还没有人宣布有足够大的量子计算机来运行Shor算法来处理任何非平凡的问题，目前还不清楚这是否可能。尽管如此，量子计算领域最近的理论和实践进展还是引起了许多人的关注。一个动机是以下情景：攻击者现在可以收集加密的流量，并将其存储，直到有足够大的量子计算机可用。一旦出现这种情况，攻击者就可以使用他们的能力来解密存储的密文。因此，如果加密技术应该在未来提供安全保障，那么它可能已经受到量子计算机的威胁……即使它们还不存在。一些估计预测，第一台足够强大的量子计算机最早将于2030年破解真正的RSA密钥。另一方面，采用新的加密技术通常需要数十年的时间。因此，现在是解决这个问题的时候了。当代密码学的第二个挑战是使用模式的变化。近年来，云服务变得越来越重要。这些都带来了巨大的隐私挑战，因为这些服务依赖于访问个人数据来增加价值。理想情况下，我们希望在不交出敏感私人数据的情况下利用第三方服务的能力。对于这两个挑战，基于格子的密码学是解决它们的关键构件。也就是说，我们可以从硬格子问题中建立密码系统，这些密码系统被认为是安全的，甚至可以抵御量子攻击者。这些密码系统还能够计算加密的数据，也称为“完全同态加密”。在这两个领域，目前正在进行标准化工作，以使这些计划得以广泛采用。然而，在我们能够做到这一点之前，我们需要完善我们对攻击者需要多长时间才能破解这些计划的理解。实用的加密方案从来不是无条件安全的，但它们是“足够安全”的，其中“足够安全”可能意味着不同的事情，具体取决于所需的性能/安全权衡。因此，我们希望确保它将花费太长的时间才能可行，同时不会选择太大的参数来过度减慢我们的通信速度。回答这个问题“攻击者需要多长时间才能破解下一代加密方案”与最初的问题--“BKZ算法需要多长时间运行？”--相同，因为BKZ算法是攻击者尝试破解基于网格的密码术的卓越算法。目前，密码界对该算法的真实成本意见不一。因此，本项目着手解决这一问题，以便我们能够满怀信心地部署下一代密码学。

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.