FELDERHOFF, Joël; PELLET-MARY, Alice; STEHLÉ, Damien

Métadonnées

Licence d’utilisation du document

FELDERHOFF, Joël
Laboratoire de l'Informatique du Parallélisme [LIP]
Arithmétiques des ordinateurs, méthodes formelles, génération de code [ARIC]

PELLET-MARY, Alice
Institut de Mathématiques de Bordeaux [IMB]
Lithe and fast algorithmic number theory [LFANT]

STEHLÉ, Damien
Laboratoire de l'Informatique du Parallélisme [LIP]
Arithmétiques des ordinateurs, méthodes formelles, génération de code [ARIC]

Langue

Communication dans un congrès

Ce document a été publié dans

Asiacrypt 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, 2022-12-05, Taipei.

Résumé en anglais

The NTRU problem can be viewed as an instance of finding a short non-zero vector in a lattice, under the promise that it contains an exceptionally short vector. Further, the lattice under scope has the structure of a rank-2 module over the ring of integers of a number field. Let us refer to this problem as the module unique Shortest Vector Problem,or mod-uSVP for short. We exhibit two reductions that together provide evidence the NTRU problem is not just a particular case of mod-uSVP, but representative of it from a computational perspective.First, we reduce worst-case mod-uSVP to worst-case NTRU. For this, we rely on an oracle for id-SVP, the problem of finding short non-zero vectors in ideal lattices. Using the worst-case id-SVP to worst-case NTRU reduction from Pellet-Mary and Stehlé [ASIACRYPT'21],this shows that worst-case NTRU is equivalent to worst-case mod-uSVP.Second, we give a random self-reduction for mod-uSVP. We put forward a distribution D over mod-uSVP instances such that solving mod-uSVP with a non-negligible probability for samples from D allows to solve mod-uSVP in the worst-case. With the first result, this gives a reduction from worst-case mod-uSVP to an average-case version of NTRU where the NTRU instance distribution is inherited from D. This worst-case to average-case reduction requires an oracle for id-SVP.< Réduire

URI

https://oskar-bordeaux.fr/handle/20.500.12278/191059

Projet Européen

PRivacy preserving pOst-quantuM systEms from advanced crypTograpHic mEchanisms Using latticeS

Project ANR

Sécurité cryptographique des réseaux modules - ANR-21-CE94-0003
Post-quantum padlock for web browser - ANR-22-PETQ-0008

Origine

Importé de hal

Unités de recherche

Institut de Mathématiques de Bordeaux (IMB) - UMR 5251