Paper 2021/218

InSIDH: a Simplification of SiGamal

Tako Boris Fouotsa and Christophe Petit

Abstract

At Asiacrypt 2020, Moriya et al. introduced two new IND-CPA secure supersingular isogeny based Public Key Encryption (PKE) protocols: SiGamal and C-SiGamal. Unlike the PKEs canonically derived from SIKE and CSIDH, the new protocols provide IND-CPA security without the use of random oracles. SiGamal and C-SiGamal are however not IND-CCA secure. Moriya et al. suggested a variant of SiGamal that could be IND-CCA secure, but left its study as an open problem. In this paper, we revisit the protocols introduced by Moriya et al. First, we show that the SiGamal variant suggested by Moriya et al. for IND-CCA security is, in fact, not IND-CCA secure. Secondly, we propose a new isogeny-based PKE protocol named InSIDH, obtained by simplifying SiGamal. InSIDH has smaller public keys and ciphertexts than (C-)SiGamal and it is more efficient. We prove that InSIDH is IND-CCA secure under CSIDH security assumptions and one Knowledge of Exponent-type assumption we introduce. Interestingly, InSIDH is also much closer to the CSIDH protocol, facilitating a comparison between SiGamal and CSIDH.