Bit Security of Learning with Errors for Post-Quantum Cryptography and Fully Homomorphic Encryption

后量子密码学和全同态加密的错误学习的比特安全性

• 批准号: EP/P009417/1
• 负责人: Martin Albrecht
• 金额: $ 10.22万
• 依托单位: Royal Holloway University of London
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2017
• 资助国家: 英国
• 起止时间: 2017 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FP009417%2F1
• 关键词: Bit; Security; Learning; Errors; Post

LWE can be summarised as: given a matrix `A` and a vector `b` modulo `q`, decide if `b` is uniform or if `b = A * s + e` for some small error `e`. Hence, the problem is essentially to solve a noisy linear system of equations modulo `q`. It was shown by Regev that this problem is as hard as assumed-to-be-hard problems. The problem has become a central building block of modern cryptographic constructions.1. Modern cybersecurity relies on cryptographic algorithms such as RSA encryption and digital signatures as well as the Diffie-Hellman key exchange. It is well-known that the hard mathematical problems underlying these algorithms can be solved efficiently on a quantum computer. While the advent of quantum computers has been promised many times before, recent developments in the area have convinced many actors, especially those with a long-term security mission, to actively seek alternative algorithms which promise post-quantum security. As a result, post-quantum cryptography has recently developed from a niche area of cryptography to a mainstream concern. With the American standards body NIST announcing it would hold a competition for post-quantum proposals, the field is posed to become a central area of cryptographic research in the coming years. LWE is one of the central candidates for a hard problem withstanding attacks using quantum computers and first proposals for key exchange algorithms for Internet communication based on LWE are available.2. Fully homomorphic encryption, the ability to compute with encrypted data, has progressed considerably since a first solution was proposed in Gentry's seminal work. The most recent generation of such schemes have become efficient enough to the point that first prototype applications, such as privacy-preserving computations with genome data, are being developed. All such constructions rely on the difficulty of solving LWE.While it is encouraging to have Regev's proof that solving LWE is no easier than solving problems widely believed to be hard as we increase parameters, this does not settle the question of how big we should choose our parameters to provide security against real world attacks. The purpose of this project is to provide more refined answers to this question, allowing us to rely on LWE with more confidence.

LWE 可以概括为：给定一个矩阵“A”和一个模“q”的向量“b”，对于一些小误差“e”，判断“b”是否一致或者“b = A * s + e”。因此，问题本质上是求解模“q”的噪声线性方程组。 Regev 表明这个问题与假设的困难问题一样困难。该问题已成为现代密码学结构的核心组成部分。1．现代网络安全依赖于加密算法，例如 RSA 加密和数字签名以及 Diffie-Hellman 密钥交换。众所周知，这些算法背后的数学难题可以在量子计算机上有效解决。虽然量子计算机的出现之前已经多次被承诺，但该领域最近的发展已经说服了许多参与者，尤其是那些肩负长期安全使命的参与者，积极寻求能够保证后量子安全的替代算法。因此，后量子密码学最近已经从密码学的一个小众领域发展成为一个主流关注点。随着美国标准机构 NIST 宣布将举办后量子提案竞赛，该领域有望成为未来几年密码学研究的中心领域。 LWE 是抵御使用量子计算机攻击的难题的核心候选者之一，并且基于 LWE 的互联网通信密钥交换算法的第一个提案已经可用。2。自从 Gentry 的开创性工作中提出第一个解决方案以来，完全同态加密（即使用加密数据进行计算的能力）已经取得了长足的进步。最新一代的此类方案已经变得足够高效，以至于正在开发第一个原型应用程序，例如使用基因组数据进行隐私保护计算。所有这些构造都依赖于解决 LWE 的难度。虽然令人鼓舞的是，Regev 证明解决 LWE 并不比解决人们普遍认为随着参数增加而困难的问题更容易，但这并不能解决我们应该选择多大的问题我们的参数可提供针对现实世界攻击的安全性。这个项目的目的就是为这个问题提供更精细的答案，让我们更加放心地依赖LWE。

项目成果

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

Breaking Bridgefy, again: Adopting libsignal is not enough

再次破坏 Bridgefy：采用 libsignal 还不够

• 发表时间: 2022
• 期刊: Proceedings of the 31st USENIX Security Symposium, Security 2022
• 作者: Albrecht M.R.

Prime and Prejudice

最初与偏见

• DOI: 10.1145/3243734.3243787
• 发表时间: 2018
• 作者: Albrecht M