Afficher la notice abrégée

On Module Unique-SVP and NTRU

hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
hal.structure.identifierArithmétiques des ordinateurs, méthodes formelles, génération de code [ARIC]
dc.contributor.authorFELDERHOFF, Joël
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierLithe and fast algorithmic number theory [LFANT]
dc.contributor.authorPELLET-MARY, Alice
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
hal.structure.identifierArithmétiques des ordinateurs, méthodes formelles, génération de code [ARIC]
dc.contributor.authorSTEHLÉ, Damien
dc.date.accessioned2024-04-04T02:40:22Z
dc.date.available2024-04-04T02:40:22Z
dc.date.conference2022-12-05
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191059
dc.description.abstractEnThe 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.
dc.description.sponsorshipSécurité cryptographique des réseaux modules - ANR-21-CE94-0003
dc.description.sponsorshipPost-quantum padlock for web browser - ANR-22-PETQ-0008
dc.language.isoen
dc.title.enOn Module Unique-SVP and NTRU
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Cryptographie et sécurité [cs.CR]
dc.description.sponsorshipEuropePRivacy preserving pOst-quantuM systEms from advanced crypTograpHic mEchanisms Using latticeS
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleAsiacrypt 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security
bordeaux.countryTW
bordeaux.conference.cityTaipei
bordeaux.peerReviewedoui
hal.identifierhal-03789544
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2022-12-09
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-03789544v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=FELDERHOFF,%20Jo%C3%ABl&PELLET-MARY,%20Alice&STEHL%C3%89,%20Damien&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée