SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

External organisations

  • IBM Research - Zurich
  • Institut Polytechnique de Paris
  • INRIA Rocquencourt
  • Aix Marseille University
  • DGA
  • Université Libre de Bruxelles
  • LOMA, Univ. Bordeaux, UMR 5798
  • UMR 5251

Abstract

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.6 s for key generation, 2.5 s for signing, and 50 ms 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.

Bibliographic note

Publisher Copyright: © 2020, International Association for Cryptologic Research.

Details

Original languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, 2020, Proceedings
EditorsShiho Moriai, Huaxiong Wang
Publication statusPublished - 2020
Event26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020 - Daejeon, Korea, Republic of
Duration: 7 Dec 202011 Dec 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12491 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020
CountryKorea, Republic of
CityDaejeon
Period7/12/2011/12/20

Keywords

  • Isogenies, Post-quantum, Signatures