DE FEO, Luca; KOHEL, David; LEROUX, Antonin; PETIT, Christophe; WESOLOWSKI, Benjamin

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

DE FEO, Luca
IBM Research [Zurich]
Geometry, arithmetic, algorithms, codes and encryption [GRACE]

KOHEL, David
Aix Marseille Université [AMU]

LEROUX, Antonin
Geometry, arithmetic, algorithms, codes and encryption [GRACE]
Délégation générale de l'armement [DGA]

Langue

Communication dans un congrès

Ce document a été publié dans

Journal of the ACM (JACM), ASIACRYPT 2020 - 26th Annual International Conference on the Theory and Application of Cryptology and Information Security, 2020-12-07, Daejeon (virtual). 2020-12-07

Association for Computing Machinery

Résumé en anglais

We 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.< Réduire

URI

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

Project ANR

Cryptographie, isogenies et variété abéliennes surpuissantes - ANR-19-CE48-0008

Origine

Importé de hal

Unités de recherche

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