Paper 2022/709

Some Easy Instances of Ideal-SVP and Implications on the Partial Vandermonde Knapsack Problem

Katharina Boudgoust, Aarhus University
Erell Gachon, Université de Bordeaux
Alice Pellet-Mary, French National Centre for Scientific Research, Université de Bordeaux

In this article, we generalize the works of Pan et al. (Eurocrypt’21) and Porter et al. (ArXiv’21) 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 generalize it to any ideal (whose prime factors are not ramified) of any number field. 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.

Note: update 01/09/2022: fixed a small bug in preliminaries

Available format(s)
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in CRYPTO 2022
Ideal Lattices Shortest Vector Problem Partial Vandermonde Problems
Contact author(s)
katharina boudgoust @ cs au dk
erell gachon @ u-bordeaux fr
alice pellet-mary @ math u-bordeaux fr
2022-09-01: revised
2022-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Katharina Boudgoust and Erell Gachon and Alice Pellet-Mary},
      title = {Some Easy Instances of Ideal-SVP and Implications on the Partial Vandermonde Knapsack Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2022/709},
      year = {2022},
      doi = {10.1007/978-3-031-15979-4_17},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.