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

Katharina Boudgoust*, Erell Gachon, Alice Pellet-Mary

*Corresponding author af dette arbejde

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer 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.

OriginalsprogEngelsk
TitelAdvances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings
Antal sider30
ForlagSpringer
Publikationsdato2022
Sider480-509
ISBN (Trykt)9783031159787
DOI
StatusUdgivet - 2022
Begivenhed42nd Annual International Cryptology Conference, CRYPTO 2022 - Santa Barbara, USA
Varighed: 15 aug. 202218 aug. 2022

Konference

Konference42nd Annual International Cryptology Conference, CRYPTO 2022
Land/OmrådeUSA
BySanta Barbara
Periode15/08/202218/08/2022
NavnLecture Notes in Computer Science
Nummer13508

Fingeraftryk

Dyk ned i forskningsemnerne om 'Some Easy Instances of Ideal-SVP and Implications on the Partial Vandermonde Knapsack Problem'. Sammen danner de et unikt fingeraftryk.

Citationsformater