Afficher la notice abrégée

SQISign: compact post-quantum signatures from quaternions and isogenies

hal.structure.identifierIBM Research [Zurich]
hal.structure.identifierGeometry, arithmetic, algorithms, codes and encryption [GRACE]
dc.contributor.authorDE FEO, Luca
hal.structure.identifierAix Marseille Université [AMU]
dc.contributor.authorKOHEL, David
hal.structure.identifierGeometry, arithmetic, algorithms, codes and encryption [GRACE]
hal.structure.identifierDélégation générale de l'armement [DGA]
dc.contributor.authorLEROUX, Antonin
hal.structure.identifierUniversity of Birmingham [Birmingham]
dc.contributor.authorPETIT, Christophe
hal.structure.identifierLithe and fast algorithmic number theory [LFANT]
hal.structure.identifierCentre National de la Recherche Scientifique [CNRS]
dc.contributor.authorWESOLOWSKI, Benjamin
dc.date.accessioned2024-04-04T02:48:38Z
dc.date.available2024-04-04T02:48:38Z
dc.date.issued2020-12-07
dc.date.conference2020-12-07
dc.identifier.issn0004-5411
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191757
dc.description.abstractEnWe introduce a new signature scheme, SQISign, (for Short Quaternion and Isogeny Signature) from isogeny graphs of supersingular elliptic curves. The signature scheme is derived from a new one-round, high soundness, interactive identification protocol. Targeting the post-quantum NIST-1 level of security, our implementation results in signatures of 204 bytes, secret keys of 16 bytes and public keys of 64 bytes. In particular, the signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. On a modern workstation, our implementation in C takes 0.6s for key generation, 2.5s for signing, and 50ms for verification.While the soundness of the identification protocol follows from classical assumptions, the zero-knowledge property relies on the second main contribution of this paper. We introduce a new algorithm to find an isogeny path connecting two given supersingular elliptic curves of known endomorphism rings. A previous algorithm to solve this problem, due to Kohel, Lauter, Petit and Tignol, systematically reveals paths from the input curves to a `special' curve. This leakage would break the zero-knowledge property of the protocol. Our algorithm does not directly reveal such a path, and subject to a new computational assumption, we prove that the resulting identification protocol is zero-knowledge.
dc.description.sponsorshipCryptographie, isogenies et variété abéliennes surpuissantes - ANR-19-CE48-0008
dc.language.isoen
dc.publisherAssociation for Computing Machinery
dc.title.enSQISign: compact post-quantum signatures from quaternions and isogenies
dc.typeCommunication dans un congrès
dc.subject.halMathématiques [math]/Théorie des nombres [math.NT]
dc.subject.halInformatique [cs]/Cryptographie et sécurité [cs.CR]
bordeaux.journalJournal of the ACM (JACM)
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleASIACRYPT 2020 - 26th Annual International Conference on the Theory and Application of Cryptology and Information Security
bordeaux.countryKR
bordeaux.conference.cityDaejeon (virtual)
bordeaux.peerReviewedoui
hal.identifierhal-03038004
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2020-12-11
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-03038004v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Journal%20of%20the%20ACM%20(JACM)&rft.date=2020-12-07&rft.eissn=0004-5411&rft.issn=0004-5411&rft.au=DE%20FEO,%20Luca&KOHEL,%20David&LEROUX,%20Antonin&PETIT,%20Christophe&WESOLOWSKI,%20Benjamin&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