Quantum lattice problems

Hans A. De Raedt, Wolfgang von der Linden

Harshana Bandara, Yasitha Herath, Thushara Weerasundara +1 more

Lattice-based cryptography is centered around the hardness of problems on lattices. A lattice is a grid of points that stretches to infinity. With the development of quantum computers, existing cryptographic schemes are at risk because the underlying mathematical problems can, in theory, be easily solved by quantum computers. Since lattice-based mathematical problems are hard to be solved even by quantum computers, lattice-based cryptography is a promising foundation for future cryptographic schemes. In this paper, we focus on lattice-based public-key encryption schemes. This survey presents the current status of the lattice-based public-key encryption schemes and discusses the existing implementations. Our main focus is the learning with errors problem (LWE problem) and its implementations. In this paper, the plain lattice implementations and variants with special algebraic structures such as ring-based variants are discussed. Additionally, we describe a class of lattice-based functions called lattice trapdoors and their applications.

Felderhoff, Joël

The security of cryptographic protocols is based on the presumed difficulty of algorithmic problems. Among those identified so far, some of the best problems to serve as a foundation for quantum-proof cryptography come from lattices. Lattices are a mathematical structure defined as a set of space vectors generated by integer combinations of a finite number of linearly independent real vectors (its basis). A typical example of a related security problem is the Shortest Vector Problem (SVP). Given a base of an n-dimensional lattice, find a non-zero short vector. For efficiency reasons, these problems are restricted to lattices arising from number theory, known as structured lattices. As the security assumptions for these particular lattices are different from those for unstructured lattices, it is necessary to study them specifically, which is the aim of this thesis.We have studied the case of NTRU and uSVP modules in rank 2, proving that the SVP problem is equivalent on these two families of lattices. We also show a worst-case to average-case reduction for rank-2 uSVP lattices. Then we show that solving SVP on a prime ideal of small norm is no easier than solving SVP on any ideal.

J. Chris Eilbeck

Jincheng Zhang

Quantum-Inspired Lattice Optimization (QILO) is a novel optimization algorithm designed to address complex geometries in problems by leveraging the principles of quantum lattices. This paper introduces a new framework centered around the concept of mapping a problem to a discrete lattice structure, employing quantum-inspired techniques to guide the search for optimal solutions. The core mechanism of QILO involves translating a problem into a lattice representation, utilizing quantum-inspired methods to facilitate efficient exploration and potentially uncover solutions more effectively than traditional methods. This work offers a promising new direction in optimization, particularly for problems with intricate geometric constraints.