logo IMB
Retour

Séminaire de Théorie Algorithmique des Nombres

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

Èrell Gachon

( - )

-

le 18 octobre 2022 à 10:00

In our 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.