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
  • Aix Marseille University
  • DGA
  • CNRS, Institut Polytechnique de Paris
  • INRIA, France
  • Université Libre de Bruxelles
  • INRIA, IMB, Talence, France
  • Universite de Bordeaux, CNRS, Bordeaux, France

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 postquantum 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.

Details

Original languageEnglish
Title of host publication26th Annual International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt 2020)
Publication statusAccepted/In press - 16 Aug 2020
Event26th Annual International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt 2020) - Virtual Event
Duration: 7 Dec 202011 Dec 2020

Conference

Conference26th Annual International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt 2020)
CityVirtual Event
Period7/12/2011/12/20

Keywords

  • Post-quantum, Signatures, Isogenies