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. (ArXiv'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.
This will be a hybrid seminar. The speaker will be giving the talk from ENS de Lyon.
Katharina Boudgoust is a postdoctoral researcher in the Cryptography and Security team of the Aarhus University, Denmark, under the supervision of Peter Scholl. She is interested in lattice-based cryptography, and more specifically in the computational hardness assumptions underlying lattice-based cryptosystems and threshold cryptography. From September 2018 to November 2021, Katharina was a PhD student with the EMSEC team at IRISA Laboratory in Rennes, France, under the supervision of Adeline Roux-Langlois and Pierre-Alain Fouque. Her PhD thesis focused on the theoretical hardness of algebraically structured Learning With Errors.