Cryptology ePrint Archive: Report 2021/1301

An Isogeny-Based ID Protocol Using Structured Public Keys

Karim Baghery and Daniele Cozzo and Robi Pedersen

Abstract: 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.

Category / Keywords: public-key cryptography / Isogeny-based Cryptography, Identification Protocols, Digital Signatures, Quantum Random Oracle Model

Original Publication (in the same form): IMACC 2021 - 18th IMA Conference on Cryptography and Coding Theory

Date: received 27 Sep 2021, last revised 28 Sep 2021

Contact author: karim baghery at kuleuven be, daniele cozzo at kuleuven be, robi pedersen at kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20210928:222608 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]