Some Easy Instances of Ideal-SVP and Implications on the Partial Vandermonde Knapsack Problem
| hal.structure.identifier | Aarhus University [Aarhus] | |
| dc.contributor.author | BOUDGOUST, Katharina | |
| hal.structure.identifier | Université de Bordeaux [UB] | |
| dc.contributor.author | GACHON, Erell | |
| hal.structure.identifier | Centre National de la Recherche Scientifique [CNRS] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Lithe and fast algorithmic number theory [LFANT] | |
| dc.contributor.author | PELLET-MARY, Alice | |
| dc.date.accessioned | 2024-04-04T02:40:17Z | |
| dc.date.available | 2024-04-04T02:40:17Z | |
| dc.date.conference | 2022-08-13 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191053 | |
| dc.description.abstractEn | 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. | |
| dc.description.sponsorship | Sécurité cryptographique des réseaux modules - ANR-21-CE94-0003 | |
| dc.description.sponsorship | Calcul réparti sécurisé : Cryptographie, Combinatoire, Calcul Formel - ANR-21-CE39-0006 | |
| dc.language.iso | en | |
| dc.title.en | Some Easy Instances of Ideal-SVP and Implications on the Partial Vandermonde Knapsack Problem | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1007/978-3-031-15979-4_17 | |
| dc.subject.hal | Informatique [cs]/Cryptographie et sécurité [cs.CR] | |
| bordeaux.volume | 13508 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | CRYPTO 2022 | |
| bordeaux.country | US | |
| bordeaux.conference.city | Santa Barbara / Hybrid | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-03789519 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.organizer | International Association for Cryptologic Research (IACR) | |
| hal.conference.end | 2022-08-18 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-03789519v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.volume=13508&rft.au=BOUDGOUST,%20Katharina&GACHON,%20Erell&PELLET-MARY,%20Alice&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||