Identification protocols and signature schemes based on supersingular isogeny problems

Steven D. Galbraith, Christophe Petit, Javier Silva

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
248 Downloads (Pure)


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 and Tignol for the quaternion version of the ℓ-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 independently published by Yoo, Azarderakhsh, Jalali, Jao and Soukharev. This is the full version of a paper published at ASIACRYPT 2017.

Original languageEnglish
Pages (from-to)130-175
JournalJournal of Cryptology
Issue number1
Early online date27 Mar 2019
Publication statusPublished - Jan 2020


  • isogenies
  • Public Key Signatures
  • Post-quantum Cryptography


Dive into the research topics of 'Identification protocols and signature schemes based on supersingular isogeny problems'. Together they form a unique fingerprint.

Cite this