Lattice-Based Cryptography

基于格的密码学

• 批准号: EP/S020330/1
• 负责人: Martin Albrecht
• 金额: $ 61.42万
• 依托单位: Royal Holloway University of London
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2019
• 资助国家: 英国
• 起止时间: 2019 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FS020330%2F1
• 关键词: 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.

BKZ算法运行多长时间？听起来像是一个相当利基的问题仅引起了理论计算机科学家的兴趣，实际上是一个核心开放问题，需要解决，以确保数字经济和私人生活的安全。虽然在很大程度上隐藏了隐藏，但密码学基于现代生活的许多方面，例如商业，银行业，治理或长途个人交流。加密方案依次确保数字通信的核心依赖两个硬性数学问题之一。但是，这些数学问题虽然仍然难以在普通计算机上解决，但实际上很容易在量子计算机上解决。也就是说，在1994年，彼得（Peter Shor）提出了一种用于解决这些问题的算法 - 保理和离散的对数 - 有效地，本质上，无论我们选择参数多大，即他在量子计算机上的多项式算法都在量子计算机上的多项式算法。 可能的。尽管如此，量子计算领域的最新理论和实践进步仍与许多人有关。一种动机是以下方案：攻击者现在可以收集加密的流量并将其存储直到有足够大的量子计算机可用。发生这种情况后，攻击者可以使用其功能来解密存储的密文。因此，如果加密应该在未来提供良好的安全性，那么它可能已经受到量子计算机的威胁……即使它们还不存在。一些估计预见到，第一台量子计算机早在2030年就足以打破真正的RSA键。另一方面，采用新的加密术通常需要数十年。因此，现在解决这个问题的时间是。当前一代密码学的第二个挑战是使用模式的变化。近年来，云服务变得越来越重要。由于这些服务依靠访问个人数据来增加价值，因此这带来了重大隐私挑战。理想情况下，我们想利用第三方服务的力量而不交出敏感的私人数据。对于这两个挑战，基于晶格的加密技术都是解决这些挑战的关键基础。也就是说，从硬晶格问题中，我们可以构建加密系统，这些密码系统被认为甚至是针对量子攻击者也是安全的。这些密码系统还可以使用加密数据计算，也称为“完全同构加密”。在这两个领域中，目前正在进行标准化的努力，以使这些方案的广泛采用。实用的加密计划永远不会无条件安全，但是它们“足够安全”，“安全”可能意味着不同的事情，具体取决于所需的性能/安全性权衡。因此，我们要确保在不挑选我们的参数太大以降低我们的通信的情况下会花费太长时间。要回答这个问题：“攻击者打破下一代加密方案需要多长时间“与最初的问题相同 - “ BKZ算法需要多长时间运行？” - 由于BKZ算法是攻击者将尝试基于格子的密码学的杰出算法。目前，密码社区不同意该算法的真实成本。因此，该项目着手解决这个问题，以便我们可以充满信心地部署下一代密码学。

项目成果

Implementing RLWE-based Schemes Using an RSA Co-Processor

• DOI: 10.13154/tches.v2019.i1.169-208
• 发表时间: 2018-11
• 期刊: IACR Trans. Cryptogr. Hardw. Embed. Syst.
• 作者: Martin R. Albrecht;Christian H. Hanser;Andrea Höller;T. Pöppelmann;Fernando Virdia;Andreas Wallner

Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part II

密码学进展 - ASIACRYPT 2020 - 第 26 届密码学理论与应用与信息安全国际会议，韩国大田，2020 年 12 月 7-11 日，会议记录，第二部分

• DOI: 10.1007/978-3-030-64834-3_20
• 发表时间: 2020
• 作者: Albrecht M

Variational quantum solutions to the Shortest Vector Problem

• DOI: 10.22331/q-2023-03-02-933
• 发表时间: 2022-02
• 期刊: ArXiv
• 作者: Martin R. Albrecht;Milos Prokop;Yixin Shen;P. Wallden

Lattice Reduction with Approximate Enumeration Oracles: Practical Algorithms and Concrete Performance

• DOI: 10.1007/978-3-030-84245-1_25
• 发表时间: 2020
• 期刊: IACR Cryptol. ePrint Arch.
• 作者: Martin R. Albrecht;Shi Bai;Jianwei Li;Joe Rowell