Identification protocols and signature schemes based on supersingular isogeny problems

Steven D. Galbraith; Christophe Petit; Javier  Silva

doi:10.1007/978-3-319-70694-8_1

Identification protocols and signature schemes based on supersingular isogeny problems

Steven D. Galbraith, Christophe Petit, Javier Silva

Computer Science

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

44 Citations (Scopus)

436 Downloads (Pure)

Abstract

We provide a new identification protocol and new signature schemes based on isogeny problems. Our identification protocol relies on the hardness of the endomorphism ring computation problem, arguably the hardest of all problems in this area, whereas the only previous scheme based on isogenies (due to De Feo, Jao and Plut) relied on potentially easier problems. The protocol makesnovel use of an algorithm of Kohel-Lauter-Petit-Tignol for the quaternion version of the l -isogeny problem, for which we provide a more complete description and analysis. Our new signature schemes are derived from the identification protocols using the Fiat-Shamir (respectively, Unruh) transforms for classical (respectively, post-quantum) security. We study their efficiency, highlighting very small key sizes and reasonably efficient signing and verification algorithms.

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2017
Subtitle of host publication	23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I
Editors	Tsuyoshi Takagi, Thomas Peyrin
Publisher	Springer
Pages	3-33
Number of pages	30
ISBN (Electronic)	9783319706948
ISBN (Print)	9783319706931
DOIs	https://doi.org/10.1007/978-3-319-70694-8_1
Publication status	Published - 30 Nov 2017
Event	23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2017) - Hong Kong Duration: 3 Dec 2017 → 7 Dec 2017

Publication series

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

Conference

Conference	23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2017)
City	Hong Kong
Period	3/12/17 → 7/12/17

Bibliographical note

Winner of the Best Paper Award of ASIACRYPT 2017 conference.

Access to Document

10.1007/978-3-319-70694-8_1Licence: None: All rights reserved

Galbraith2017IdentificationAccepted author manuscript, 433 KBLicence: None: All rights reserved

https://doi.org/10.1007/978-3-319-70694-8_1Licence: None: All rights reserved

Cite this

Galbraith, S. D., Petit, C., & Silva, J. (2017). Identification protocols and signature schemes based on supersingular isogeny problems. In T. Takagi, & T. Peyrin (Eds.), Advances in Cryptology – ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I (pp. 3-33). ( Lecture Notes in Computer Science (LNCS); Vol. 10624). Springer. https://doi.org/10.1007/978-3-319-70694-8_1

Galbraith, Steven D. ; Petit, Christophe ; Silva, Javier . / Identification protocols and signature schemes based on supersingular isogeny problems. Advances in Cryptology – ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I. editor / Tsuyoshi Takagi ; Thomas Peyrin. Springer, 2017. pp. 3-33 ( Lecture Notes in Computer Science (LNCS)).

@inproceedings{799511d56d524318aa0e6ba8668dbc90,

title = "Identification protocols and signature schemes based on supersingular isogeny problems",

abstract = "We provide a new identification protocol and new signature schemes based on isogeny problems. Our identification protocol relies on the hardness of the endomorphism ring computation problem, arguably the hardest of all problems in this area, whereas the only previous scheme based on isogenies (due to De Feo, Jao and Plut) relied on potentially easier problems. The protocol makesnovel use of an algorithm of Kohel-Lauter-Petit-Tignol for the quaternion version of the l -isogeny problem, for which we provide a more complete description and analysis. Our new signature schemes are derived from the identification protocols using the Fiat-Shamir (respectively, Unruh) transforms for classical (respectively, post-quantum) security. We study their efficiency, highlighting very small key sizes and reasonably efficient signing and verification algorithms.",

author = "Galbraith, {Steven D.} and Christophe Petit and Javier Silva",

note = "Winner of the Best Paper Award of ASIACRYPT 2017 conference.; 23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2017) ; Conference date: 03-12-2017 Through 07-12-2017",

year = "2017",

month = nov,

day = "30",

doi = "10.1007/978-3-319-70694-8_1",

language = "English",

isbn = "9783319706931",

series = " Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "3--33",

editor = "Tsuyoshi Takagi and Thomas Peyrin",

booktitle = "Advances in Cryptology – ASIACRYPT 2017",

}

Galbraith, SD, Petit, C & Silva, J 2017, Identification protocols and signature schemes based on supersingular isogeny problems. in T Takagi & T Peyrin (eds), Advances in Cryptology – ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I. Lecture Notes in Computer Science (LNCS), vol. 10624, Springer, pp. 3-33, 23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2017), Hong Kong, 3/12/17. https://doi.org/10.1007/978-3-319-70694-8_1

Identification protocols and signature schemes based on supersingular isogeny problems. / Galbraith, Steven D.; Petit, Christophe; Silva, Javier .
Advances in Cryptology – ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I. ed. / Tsuyoshi Takagi; Thomas Peyrin. Springer, 2017. p. 3-33 ( Lecture Notes in Computer Science (LNCS); Vol. 10624).

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

TY - GEN

T1 - Identification protocols and signature schemes based on supersingular isogeny problems

AU - Galbraith, Steven D.

AU - Petit, Christophe

AU - Silva, Javier

N1 - Winner of the Best Paper Award of ASIACRYPT 2017 conference.

PY - 2017/11/30

Y1 - 2017/11/30

N2 - We provide a new identification protocol and new signature schemes based on isogeny problems. Our identification protocol relies on the hardness of the endomorphism ring computation problem, arguably the hardest of all problems in this area, whereas the only previous scheme based on isogenies (due to De Feo, Jao and Plut) relied on potentially easier problems. The protocol makesnovel use of an algorithm of Kohel-Lauter-Petit-Tignol for the quaternion version of the l -isogeny problem, for which we provide a more complete description and analysis. Our new signature schemes are derived from the identification protocols using the Fiat-Shamir (respectively, Unruh) transforms for classical (respectively, post-quantum) security. We study their efficiency, highlighting very small key sizes and reasonably efficient signing and verification algorithms.

AB - We provide a new identification protocol and new signature schemes based on isogeny problems. Our identification protocol relies on the hardness of the endomorphism ring computation problem, arguably the hardest of all problems in this area, whereas the only previous scheme based on isogenies (due to De Feo, Jao and Plut) relied on potentially easier problems. The protocol makesnovel use of an algorithm of Kohel-Lauter-Petit-Tignol for the quaternion version of the l -isogeny problem, for which we provide a more complete description and analysis. Our new signature schemes are derived from the identification protocols using the Fiat-Shamir (respectively, Unruh) transforms for classical (respectively, post-quantum) security. We study their efficiency, highlighting very small key sizes and reasonably efficient signing and verification algorithms.

U2 - 10.1007/978-3-319-70694-8_1

DO - 10.1007/978-3-319-70694-8_1

M3 - Conference contribution

SN - 9783319706931

T3 - Lecture Notes in Computer Science (LNCS)

SP - 3

EP - 33

BT - Advances in Cryptology – ASIACRYPT 2017

A2 - Takagi, Tsuyoshi

A2 - Peyrin, Thomas

PB - Springer

T2 - 23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2017)

Y2 - 3 December 2017 through 7 December 2017

ER -

Galbraith SD, Petit C, Silva J. Identification protocols and signature schemes based on supersingular isogeny problems. In Takagi T, Peyrin T, editors, Advances in Cryptology – ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I. Springer. 2017. p. 3-33. ( Lecture Notes in Computer Science (LNCS)). doi: 10.1007/978-3-319-70694-8_1

Identification protocols and signature schemes based on supersingular isogeny problems

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Fingerprint

Cite this