Lattice-Based Cryptography

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