Paper 2016/1154

Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems

Steven D. Galbraith, Christophe Petit, and Javier Silva

Abstract

We present signature schemes whose security relies on computational assumptions relating to isogeny graphs of supersingular elliptic curves. We give two schemes, both of them based on interactive identification protocols. The first identification protocol is due to De Feo, Jao and Pl{û}t. The second one, and the main contribution of the paper, makes novel use of an algorithm of Kohel-Lauter-Petit-Tignol for the quaternion version of the $\ell$-isogeny problem, for which we provide a more complete description and analysis, and is based on a more standard and potentially stronger computational problem. Both identification protocols lead to signatures that are existentially unforgeable under chosen message attacks in the random oracle model using the well-known Fiat-Shamir transform, and in the quantum random oracle model using another transform due to Unruh. A version of the first signature scheme was indepdendently published by Yoo, Azarderakhsh, Jalali, Jao and Soukharev. This is the full version of a paper published at ASIACRYPT 2017.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in ASIACRYPT 2017
Keywords
elliptic curvesisogeniespost-quantum crypto
Contact author(s)
javiersilvavelon @ gmail com
History
2018-03-13: last of 5 revisions
2016-12-21: received
See all versions
Short URL
https://ia.cr/2016/1154
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1154,
      author = {Steven D.  Galbraith and Christophe Petit and Javier Silva},
      title = {Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1154},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1154}},
      url = {https://eprint.iacr.org/2016/1154}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.