Quantum & AI
QUAIL: Quantum Artificial Intelligence Lab
The impact of quantum information can be both constructive and destructive: one the one hand quantum parallelism offers unprecedented computational power; on the other hand it can be used to break cryptosystems. QUAIL is uniquely positioned to address both sides of quantum information science in a holistic approach, namely, not only harnessing the power of quantum computers for artificial intelligence, but also securing communications and computation for machine learning under the threat of quantum computing attacks in the post-quantum era.
Lattice-based cryptography is a highly active area of post-quantum cryptography research. Regular meetings to learn about current research in the field are held to keep up to date with developments in the field and encourage discourse with other researchers. Information for the next Lattice Coding & Crypto meeting is included on this page.
Led by Dr Roberto Bondesan and Dr Cong Ling
Lattice Coding & Crypto Meeting
July 19, Room MOOREAX-034B, Moore Annexe Building, Egham Campus, Royal Holloway
Additive Generalization of Voronoi Theory for Algebraic Number Fields 12:00-13:00
Alar Leibak
Alar Leibak is a senior lecturer in mathematics at Tallinn University of Technology and an associated professor (docent) at Tallinn University. His research interests include Voronoi theory for algebraic number fields and applications of algebra and number theory. Alar Leibak received his PhD in Natural Sciences from Tallinn University of Technology in 2006 and his dissertation focused on the perfect forms over algebraic number fields. He has also published papers in Advances in Mathematics of Communications and International Journal of Control.
Abstract: On the space of positive definite quadratic forms of m variables, one can consider the function gamma(f)= min{f} ⁄ m.5d(f) where d(f) denotes the determinant of the matrix of the quadratic form f. A quadratic form f is called extreme if this function attains local maxima at f. Recall that a lattice associated with the extreme quadratic forms gives dense lattice packing of equal spheres in the corresponding vector space. Voronoi proved that positive definite quadratic form is extreme if and only if it is perfect (i.e. f is uniquely determined by its minimal vectors and by m(f)) and eutactic (the adjoint of f lies in the open convex cone spanned by vvt, where v runs over the set of minimal vectors of f). Furthermore, Voronoi developed an algorithm for finding (at least in theory) all perfect forms (up to homothety and equivalence). Hence, he also gave a method for finding extreme forms (and dense lattice packings). Many extreme forms and dense lattices can be constructed using algebraic number fields (see J. H. Conway and N. J. A. Sloane, Sphere packing, lattices, and groups, or M. Craig, Extreme forms and cyclotomy, etc.). Koecher generalized the Voronoi theory (the Hermite’ function and perfect forms) for algebraic number fields by considering the so-called Humbert tuple of quadratic or Hermitian forms. His work has been developed further by H. Ong, T. Watanabe, A. Leibak, D. Yasaki, K. Okuda, S. Yano, and others. Recently, C. Ling and C. Porter introduced \textit{unit-reducible number fields}. It turned out that real quadratic unit-reducible fields can be characterized in terms of unary perfect forms over those fields. The aim of this talk is to give a survey of the additive generalization of Voronoi’s theory for algebraic number fields.
13:00-14:00 Lunch
Revisiting Security Estimation for LWE with Hints from a Geometric Perspective 14:00-15:00
Hunter Kippen
Hunter Kippen is a Ph.D. candidate at the University of Maryland advised by Prof. Dana Dachman-Soled. His main research focus is on the cryptanalysis of lattice problems. He is a recipient of the Clark Doctoral Fellowship and a best paper honorable mention at ACM CCS 2022.
Abstract: The Distorted Bounded Distance Decoding Problem (DBDD) was introduced by Dachman-Soled et al. [Crypto ’20] as an intermediate problem between LWE and unique-SVP (uSVP). They presented an approach that reduces an LWE instance to a DBDD instance, integrates side information (or “hints”) into the DBDD instance, and finally reduces it to a uSVP instance, which can be solved via lattice reduction. This current work focuses on new methods for integrating hints into a DBDD instance. We view hints from a geometric perspective, as opposed to the distributional perspective from the prior work. Our approach provides the rigorous promise that, as hints are integrated into the DBDD instance, the correct solution remains a lattice point contained in the specified ellipsoid.
We instantiate our approach with two new types of hints: (1) Inequality hints, corresponding to the region of intersection of an ellipsoid and a halfspace; (2) Combined hints, corresponding to the region of intersection of two ellipsoids. We apply our techniques to the decryption failure and side-channel attack settings. We show that “inequality hints” can be used to model decryption failures, and that our new approach yields a geometric analogue of the “failure boosting” technique of D’anvers et al. [ePrint, ’18]. We also show that “combined hints” can be used to fuse information from a decryption failure and a side-channel attack, and provide rigorous guarantees despite the data being non-Gaussian.
15:00-15:30 Break
Subfield Algorithms for Ideal and Module-SVP Based on the Decomposition Group 15:30-16:30
Christian Porter
Dr. Christian Porter received his Ph.D. from Imperial College London in 2022 and currently holds a post-doctoral researcher position at Imperial College London. In 2022, he was a Lead Researcher in cryptography at Silence Laboratories. His primary interests revolve around the geometry of numbers and reduction theory of quadratic forms, particularly concerning modules spanned over algebraic rings and lattice-based cryptography. His recent research publications appear in IEEE Transactions on Signal Processing, Banach Center Publications, Journal de Théorie des Nombres de Bordeaux, and Number-Theoretic Methods in Cryptology (NuTMiC’2021).
Abstract: Whilst lattice-based cryptosystems are believed to be resistant to quantum attack, they are often forced to pay for that security with inefficiencies in implementation. This problem is overcome by ring- and module-based schemes such as Ring-LWE or Module-LWE, whose keysize can be reduced by exploiting its algebraic structure, allowing for faster computations. Many rings may be chosen to define such cryptoschemes, but cyclotomic rings, due to their cyclic nature allowing for easy multiplication, are the community standard. However, there is still much uncertainty as to whether this structure may be exploited to an adversary’s benefit. In this paper, we show that the decomposition group of a cyclotomic ring of arbitrary conductor can be utilised to significantly decrease the dimension of the ideal (or module) lattice required to solve a given instance of SVP. Moreover, we show that there exist a large number of rational primes for which, if the prime ideal factors of an ideal lie over primes of this form, give rise to an “easy” instance of SVP. It is important to note that the work on ideal SVP does not break Ring-LWE, since its security reduction is from worst case ideal SVP to average case Ring-LWE, and is one way. Based on a paper published in Number-Theoretic Methods in Cryptology (NuTMiC’2021).
Some Easy Instances of Ideal-SVP and Implications on the Partial Vandermonde Knapsack Problem 16:30-17:30
Katharina Boudgoust
Katharina is a postdoctoral researcher in the Cryptography and Security team of the Aarhus University, Denmark, hosted by Peter Scholl. She is interested in lattice-based cryptography, and more specifically in the computational hardness assumptions underlying lattice-based cryptosystems. In November 2021, Katharina finished her PhD at the IRISA laboratory in Rennes, France, under the supervision of Adeline Roux-Langlois and Pierre-Alain Fouque.
Abstract: This talk focuses on the shortest vector problem over so-called ideal lattices. Whereas it is believed to be hard in the worst-case, prior works have shown that there are several specific cases, where the problem becomes easy to solve. We continue this line of work and provide a simple condition under which an ideal lattice defines an easy instance of the shortest vector problem. Namely, we show that the more automorphisms stabilize the ideal, the easier it is to find a short vector in it. This observation was already made for prime ideals in Galois fields, and we extend it to any ideal (whose prime factors are not ramified) of any number field, generalizing the works of Pan et al. (Eurocrypt’21) and Porter et al. (NuTMiC’21). We then provide a cryptographic application of this result by showing that particular instances of the partial Vandermonde knapsack problem, also known as partial Fourier recovery problem, can be solved classically in polynomial time. As a proof of concept, we implemented our attack and managed to solve those particular instances for concrete parameter settings proposed in the literature. For random instances, we can halve the lattice dimension with non-negligible probability. We conclude the presentation by clarifying the impacts of our results to lattice-based cryptography. This is a joint work with Erell Gachon and Alice Pellet-Mary.
