Paper 2021/1301

An Isogeny-Based ID Protocol Using Structured Public Keys

Karim Baghery, 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 $\mathit{w}\mathit{e}\mathit{l}\mathit{l}\mathit{-}\mathit{f}\mathit{o}\mathit{r}\mathit{m}\mathit{e}\mathit{d}$ 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$$ faster than the basic ID protocol which has a binary challenge space, and moreover, the proof in our case will be about 13.5$$ 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.