Paper 2021/1301

An Isogeny-Based ID Protocol Using Structured Public Keys

Karim Baghery, Daniele Cozzo, and Robi Pedersen


Isogeny-based cryptography is known as one of the promising approaches to the emerging post-quantum public key cryptography. In cryptography, an IDentification (ID) protocol is a primitive that allows someone's identity to be confirmed. We present an efficient variation of the isogeny-based interactive ID scheme used in the base form of the CSI-FiSh signature [BKV19], which was initially proposed by Couveignes-Rostovtsev-Stolbunov [Cou06, RS06], to support a larger challenge space, and consequently achieve a better soundness error rate in each execution. To this end, we prolong the public key of the basic ID protocol with some $\it{well-formed}$ elements that are generated by particular factors of the secret key. Due to the need for a well-formed (or structured) public key, the (secret and public) keys are generated by a trusted authority. Our analysis shows that, for a particular security parameter, by extending a public key of size 64 B to 2.1 MB, the prover and verifier of our ID protocol can be more than 14$\times$ faster than the basic ID protocol which has a binary challenge space, and moreover, the proof in our case will be about 13.5$\times$ shorter. Using standard techniques, we also turn the presented ID protocol into a signature scheme that is as efficient as the state-of-the-art CSI-FiSh signature, and is existentially unforgeable under chosen message attacks in the (quantum) random oracle model. However, in our signature scheme, a verifier should get the public key of a signer from a trusted authority, which is standard in a wide range of current uses of signatures. Finally, we show how to eliminate the need for a trusted authority in our proposed ID protocol.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision.IMACC 2021 - 18th IMA Conference on Cryptography and Coding Theory
Isogeny-based CryptographyIdentification ProtocolsDigital SignaturesQuantum Random Oracle Model
Contact author(s)
karim baghery @ kuleuven be
daniele cozzo @ kuleuven be
robi pedersen @ kuleuven be
2021-12-13: last of 2 revisions
2021-09-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Karim Baghery and Daniele Cozzo and Robi Pedersen},
      title = {An Isogeny-Based ID Protocol Using Structured Public Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1301},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.