Research in Lattice-Based Cryptography

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

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.