SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies

Luca De Feo; David Kohel; Antonin Leroux; Christophe Petit; Benjamin Wesolowski

doi:10.1007/978-3-030-64837-4_3

SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies

Luca De Feo, David Kohel, Antonin Leroux^*, Christophe Petit, Benjamin Wesolowski

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

27 Downloads (Pure)

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.

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2020
Subtitle of host publication	26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I
Editors	Shiho Moriai, Huaxiong Wang
Publisher	Springer
Pages	64-93
Number of pages	30
Edition	1
ISBN (Electronic)	9783030648374
ISBN (Print)	9783030648367
DOIs	https://doi.org/10.1007/978-3-030-64837-4_3
Publication status	Published - 6 Dec 2020
Event	26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020 - Daejeon, Korea, Republic of Duration: 7 Dec 2020 → 11 Dec 2020

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12491
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020
Country/Territory	Korea, Republic of
City	Daejeon
Period	7/12/20 → 11/12/20

Bibliographical note

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

Keywords

Post-quantum
Signatures
Isogenies

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-64837-4_3

FeoL2020SQISign
This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/978-3-030-64837-4_3. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms.
Accepted author manuscript, 520 KBLicence: Other (please specify with Rights Statement)

Cite this

De Feo, L., Kohel, D., Leroux, A., Petit, C., & Wesolowski, B. (2020). SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies. In S. Moriai, & H. Wang (Eds.), Advances in Cryptology – ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I (1 ed., pp. 64-93). (Lecture Notes in Computer Science; Vol. 12491). Springer. https://doi.org/10.1007/978-3-030-64837-4_3

De Feo, Luca ; Kohel, David ; Leroux, Antonin et al. / SQISign : Compact Post-quantum Signatures from Quaternions and Isogenies. Advances in Cryptology – ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I. editor / Shiho Moriai ; Huaxiong Wang. 1. ed. Springer, 2020. pp. 64-93 (Lecture Notes in Computer Science).

@inproceedings{028759ae05454d3fb1760757494868cf,

title = "SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies",

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 {\textquoteleft}special{\textquoteright} 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.",

keywords = "Post-quantum, Signatures, Isogenies",

author = "{De Feo}, Luca and David Kohel and Antonin Leroux and Christophe Petit and Benjamin Wesolowski",

note = "Publisher Copyright: {\textcopyright} 2020, International Association for Cryptologic Research.; 26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020 ; Conference date: 07-12-2020 Through 11-12-2020",

year = "2020",

month = dec,

day = "6",

doi = "10.1007/978-3-030-64837-4_3",

language = "English",

isbn = "9783030648367",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "64--93",

editor = "Shiho Moriai and Huaxiong Wang",

booktitle = "Advances in Cryptology – ASIACRYPT 2020",

edition = "1",

}

De Feo, L, Kohel, D, Leroux, A, Petit, C & Wesolowski, B 2020, SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies. in S Moriai & H Wang (eds), Advances in Cryptology – ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I. 1 edn, Lecture Notes in Computer Science, vol. 12491, Springer, pp. 64-93, 26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020, Daejeon, Korea, Republic of, 7/12/20. https://doi.org/10.1007/978-3-030-64837-4_3

SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies. / De Feo, Luca; Kohel, David; Leroux, Antonin et al.
Advances in Cryptology – ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I. ed. / Shiho Moriai; Huaxiong Wang. 1. ed. Springer, 2020. p. 64-93 (Lecture Notes in Computer Science; Vol. 12491).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - SQISign

T2 - 26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020

AU - De Feo, Luca

AU - Kohel, David

AU - Leroux, Antonin

AU - Petit, Christophe

AU - Wesolowski, Benjamin

PY - 2020/12/6

Y1 - 2020/12/6

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

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

KW - Post-quantum

KW - Signatures

KW - Isogenies

UR - http://www.scopus.com/inward/record.url?scp=85097850800&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-64837-4_3

DO - 10.1007/978-3-030-64837-4_3

M3 - Conference contribution

AN - SCOPUS:85097850800

SN - 9783030648367

T3 - Lecture Notes in Computer Science

SP - 64

EP - 93

BT - Advances in Cryptology – ASIACRYPT 2020

A2 - Moriai, Shiho

A2 - Wang, Huaxiong

PB - Springer

Y2 - 7 December 2020 through 11 December 2020

ER -

De Feo L, Kohel D, Leroux A, Petit C, Wesolowski B. SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies. In Moriai S, Wang H, editors, Advances in Cryptology – ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I. 1 ed. Springer. 2020. p. 64-93. (Lecture Notes in Computer Science). Epub 2020 Dec 5. doi: 10.1007/978-3-030-64837-4_3

SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this