**SiGamal: A supersingular isogeny-based PKE and its application to a PRF**

*Tomoki Moriya and Hiroshi Onuki and Tsuyoshi Takagi*

**Abstract: **We propose two new supersingular isogeny-based public key encryptions: SiGamal and C-SiGamal. These public key encryptions are developed by giving an additional point of the order $2^r$ to CSIDH. SiGamal seems similar to ElGamal encryption, while C-SiGamal is a compressed version of SiGamal. We prove that SiGamal and C-SiGamal obtain IND-CPA security without using hash functions under a new assumption: the P-CSSDDH assumption. This assumption comes from the expectation that no efficient algorithm can distinguish between a random point and a point that is the image of a public point under a hidden isogeny.

Next, we propose a Naor-Reingold type pseudo random function based on SiGamal. If the P-CSSDDH assumption and the CSSDDH$^*$ assumption, which guarantees the security of CSIDH that uses a prime $p$ in the setting of SiGamal, hold, then our proposed function is a pseudo random function. Moreover, we estimate computational costs of group actions to compute our proposed PRF are about $\sqrt{\frac{8T}{3\pi}}$ times than that of the group action in CSIDH, where $T$ is the Hamming weight of input of the PRF.

Finally, we experimented group actions in SiGamal and C-SiGamal. In our experimentation, the computational costs of group actions in SiGamal-512 with a $256$-bit plaintext message space are about $2.62$ times that of a group action in CSIDH-512.

**Category / Keywords: **public-key cryptography / isogeny-based cryptography/isogenies/CSIDH/public key encryption

**Date: **received 25 May 2020

**Contact author: **tomoki_moriya at mist i u-tokyo ac jp,onuki@mist i u-tokyo ac jp,takagi@mist i u-tokyo ac jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20200525:160958 (All versions of this report)

**Short URL: **ia.cr/2020/613

[ Cryptology ePrint archive ]