Mostrar el registro sencillo del ítem

New algorithms for the Deuring correspondence Towards practical and secure SQISign signatures

hal.structure.identifierIBM Research [Zurich]
dc.contributor.authorDE FEO, Luca
hal.structure.identifierInstitut de Recherche Mathématique de Rennes [IRMAR]
hal.structure.identifierDGA
dc.contributor.authorLEROUX, Antonin
hal.structure.identifierMicrosoft Research
dc.contributor.authorLONGA, Patrick
hal.structure.identifierCentre National de la Recherche Scientifique [CNRS]
hal.structure.identifierUnité de Mathématiques Pures et Appliquées [UMPA-ENSL]
hal.structure.identifierLithe and fast algorithmic number theory [LFANT]
hal.structure.identifierAnalyse cryptographique et arithmétique [CANARI]
dc.contributor.authorWESOLOWSKI, Benjamin
dc.date.accessioned2024-04-04T02:34:42Z
dc.date.available2024-04-04T02:34:42Z
dc.date.conference2023-04-23
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190572
dc.description.abstractEnThe Deuring correspondence defines a bijection between isogenies of supersingular elliptic curves and ideals of maximal orders in a quaternion algebra. We present a new algorithm to translate ideals of prime-power norm to their corresponding isogenies — a central task of the effective Deuring correspondence. The new method improves upon the algorithm introduced in 2021 by De Feo, Kohel, Leroux, Petit and Wesolowski as a building-block of the SQISign signature scheme. SQISign is the most compact post-quantum signature scheme currently known, but is several orders of magnitude slower than competitors, the main bottleneck of the computation being the ideal-to-isogeny translation. We implement the new algorithm and apply it to SQISign, achieving a more than two-fold speedup in key generation and signing with a new choice of parameter. Moreover, after adapting the state-of-the-art Fp2 multiplication algorithms by Longa to implement SQISign’s underlying extension field arithmetic and adding various improvements, we push the total speedups to over three times for signing and four times for verification. In a second part of the article, we advance cryptanalysis by showing a very simple distinguisher against one of the assumptions used in SQISign. We present a way to impede the distinguisher through a few changes to the generic KLPT algorithm. We formulate a new assumption capturing these changes, and provide an analysis together with experimental evidence for its validity.
dc.description.sponsorshipMéthodes pour les variétés abéliennes de petite dimension - ANR-20-CE40-0013
dc.description.sponsorshipPost-quantum padlock for web browser - ANR-22-PETQ-0008
dc.description.sponsorshipCentre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation - ANR-11-LABX-0020
dc.language.isoen
dc.rights.urihttp://creativecommons.org/licenses/by/
dc.subject.enPost-quantum cryptography
dc.subject.enIsogenies
dc.subject.enGroup actions
dc.title.enNew algorithms for the Deuring correspondence Towards practical and secure SQISign signatures
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Cryptographie et sécurité [cs.CR]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleEurocrypt 2023
bordeaux.countryFR
bordeaux.conference.cityLyon
bordeaux.peerReviewedoui
hal.identifierhal-04052502
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2023-04-27
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-04052502v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=DE%20FEO,%20Luca&LEROUX,%20Antonin&LONGA,%20Patrick&WESOLOWSKI,%20Benjamin&rft.genre=unknown


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem