Variational Quantum Algorithms for Structured Lattices

点击翻译按钮获取中文摘要

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.