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

Katharina Boudgoust*, Erell Gachon, Alice Pellet-Mary

*Corresponding author for this work

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings
Number of pages30
PublisherSpringer
Publication date2022
Pages480-509
ISBN (Print)9783031159787
DOIs
Publication statusPublished - 2022
Event42nd Annual International Cryptology Conference, CRYPTO 2022 - Santa Barbara, United States
Duration: 15 Aug 202218 Aug 2022

Conference

Conference42nd Annual International Cryptology Conference, CRYPTO 2022
Country/TerritoryUnited States
CitySanta Barbara
Period15/08/202218/08/2022
SeriesLecture Notes in Computer Science
Number13508

Fingerprint

Dive into the research topics of 'Some Easy Instances of Ideal-SVP and Implications on the Partial Vandermonde Knapsack Problem'. Together they form a unique fingerprint.

Cite this