Research in Lattice-Based Cryptography

基于格的密码学研究

• 批准号: 2767355
• 金额: --
• 依托单位: Imperial College London
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2022
• 资助国家: 英国
• 起止时间: 2022 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2767355
• 关键词: Research; Lattice; Based; Cryptography

Current cryptosystems are based on computationally difficult problems such as factorisation and the discrete logarithm problem. However, recent advances in the development of quantum computers threaten these existing schemes which protect data, communications, and form the backbone of many, if not all, online processes, such as digital transactions. As such, research into post-quantum cryptography has become increasingly active and relevant. Post-quantum cryptography involves the construction and analysis of new cryptographic primitives that are difficult enough that a quantum computer cannot solve them easily and are therefore secure against quantum attacks. There are several candidate problems for making post-quantum cryptography secure enough against quantum computers. One class of these are lattice problems, such as finding the shortest vector in a lattice. A lattice is the set of all integer linear combinations of its basis vectors. Multiple bases can represent the same lattice, and lattice-based cryptography uses this fact to its advantage. Often, breaking a lattice-based cryptosystem requires finding vectors which are close to a certain target or finding short vectors, which is difficult without some secret knowledge. This secret knowledge could be a "good" basis, a basis containing short vectors, which makes the problem easier to solve. However, this secret information is protected by the fact that it is hard to recover it. The project aims to investigate a lattice problem known as the Lattice Isomorphism Problem, which has not yet gotten as much attention as others. This problem's hardness comes from the nontrivial task of distinguishing if two lattices are isomorphic, or in other words, similar in structure and properties. If an attacker knew the transformation which relates two lattices to each other, any schemes using this problem would easily be broken. However, it is believed that finding this transformation or even just deciding if two lattices are isomorphic is difficult even for quantum computers. Particularly, this problem is looked at in the context of signature schemes. The advantages of a signature scheme using the Lattice Isomorphism Problem is simplicity compared to signature schemes using different lattice problems, but there is still much to be done to improve its efficiency and test its security. To achieve these goals, the approaches used in this project will be mathematical, borrowing methods from number theory, coding theory, probability theory, and algorithmic analysis. The novelty of this research will come from the combination of techniques used to improve important algorithms in the signature scheme. This project aligns with EPSRC's research in information and communications technologies, as well as number theory and mathematical sciences which the methods used to analyse the security of lattice-based cryptographic schemes rely heavily on.

目前的密码系统是基于计算困难的问题，如因子分解和离散对数问题。然而，量子计算机发展的最新进展威胁到了这些现有的保护数据、通信的方案，这些方案构成了许多（如果不是全部的话）在线流程（如数字交易）的支柱。因此，对后量子密码学的研究变得越来越活跃和相关。后量子密码学涉及到新的密码原语的构建和分析，这些原语非常困难，量子计算机无法轻松解决它们，因此可以安全地抵御量子攻击。要使后量子密码术对量子计算机足够安全，有几个候选问题。其中一类是格问题，例如在格中寻找最短向量。格是其基向量的所有整数线性组合的集合。多个基可以表示相同的格，基于格的密码学利用了这一事实。通常，破解基于格的密码系统需要找到接近某个目标的向量或找到短向量，这在没有一些秘密知识的情况下是困难的。这个秘密知识可能是一个“好”基，一个包含短向量的基，这使得问题更容易解决。然而，这些秘密信息受到保护的事实是很难恢复它。该项目旨在研究一个被称为格同构问题的格问题，这还没有得到像其他人一样多的关注。这个问题的困难来自于区分两个格是否同构的重要任务，或者换句话说，在结构和性质上相似。如果攻击者知道将两个格相互关联的变换，那么任何使用这个问题的方案都很容易被破解。然而，人们认为，即使对于量子计算机来说，找到这种变换或者仅仅决定两个晶格是否同构也是困难的。特别是，这个问题是在签名方案的背景下看。利用格同构问题构造的签名方案相对于利用其他格问题构造的签名方案具有简单的优点，但其效率和安全性还有待进一步提高。为了实现这些目标，在这个项目中使用的方法将是数学，借用数论，编码理论，概率论和算法分析的方法。这项研究的新奇将来自于用于改进签名方案中重要算法的技术的组合。该项目与EPSRC在信息和通信技术以及数论和数学科学方面的研究保持一致，用于分析基于格的加密方案安全性的方法严重依赖于这些研究。