Variational Quantum Algorithms for Structured Lattices

追求能够抵抗量子攻击的经典加密协议被称为后量子加密（PQC）。这些协议中的大多数都是基于基于格的加密，它使用高维格对数据进行加密。基于格的密码学利用格理论和格相关问题的硬度来构建密码原语。与当前基于因子分解或离散对数的公钥方案不同，基于格的密码术似乎可以抵抗量子攻击。最短向量问题（SVP）寻求给定晶格的最短非零向量，是这些协议的核心。具有一定结构的格，即结构化格，通常用于提高这些协议的效率。事实上，NIST最近标准化的四种PQC方案中有三种是基于结构化晶格的。然而，人们对结构晶格的量子硬度知之甚少。我们已经在平面晶格的量子算法方向上取得了进展。该项目的目标是将这一方向的研究推向更高的水平，即解决结构化晶格的问题，这是NIST PQC协议的基础。在这个项目中，我们的目标是开发变分量子算法，利用这些晶格的结构来解决它们的SVP，从而允许对PQC协议进行适当的量子密码分析。密码分析的目的不是危害信息安全，而是揭示加密协议的潜在弱点，从而确保更强的安全性。

The pursuit of classical encryption protocols that are resistant to quantum attacks is known as post-quantum cryptography (PQC). The majority of these protocols are based on lattice-based cryptography, which encrypts data using high-dimensional lattices. Lattice-based cryptography builds cryptographic primitives by utilising lattice theory and the hardness of lattice-related problems. Unlike current public-key schemes based on factoring or discrete logarithm, lattice-based cryptography appears to be resistant to quantum attacks. The shortest vector problem (SVP), which seeks the shortest non-zero vector of a given lattice, is at the heart of these protocols. Lattices with some structure, i.e. structured lattices, are typically used to improve the efficiency of these protocols. In fact, three out of the four PQC schemes recently standardized by NIST, are based on structured lattices. However, the quantum hardness of structured lattices is poorly understood.We have already made inroads into the direction of quantum algorithms for plain lattices. The ambition of this project is to advance the research in this direction to a higher level, namely, to tackle the problems of structured lattices, which underpin NIST's PQC protocols. In this project, we aim to develop variational quantum algorithms that take advantage of the structure of these lattices to solve their SVP, thereby permitting a proper quantum cryptanalysis of PQC protocols. The goal of cryptanalysis is not to jeopardize information security, but to reveal potential weaknesses of encryption protocols so that stronger security can be assured.