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 提出了一种有效解决这些问题的算法 - 因式分解和离散对数 - 基本上无论我们选择参数有多大，即他在量子计算机上找到了多项式时间算法。迄今为止，没有人有宣布了一台足够大的量子计算机来运行 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