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

Tomoki Moriya, Hiroshi Onuki, and Tsuyoshi Takagi

##### Abstract

We propose two new supersingular isogeny-based public key encryptions: SiGamal and C-SiGamal. They were developed by giving an additional point of the order $2^r$ to CSIDH. SiGamal is similar to ElGamal encryption, while C-SiGamal is a compressed version of SiGamal. We prove that SiGamal and C-SiGamal are IND-CPA secure 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 (PRF) 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 that the computational costs of group actions to compute our proposed PRF are about $\sqrt{\frac{8T}{3\pi}}$ times that of the group actions in CSIDH, where $T$ is the Hamming weight of the input of the PRF. Finally, we experimented with group actions in SiGamal and C-SiGamal. The computational costs of group actions in SiGamal-512 with a $256$-bit plaintext message space were about $2.62$ times that of a group action in CSIDH-512.

Available format(s)
Category
Public-key cryptography
Publication info
Keywords
isogeny-based cryptographyisogeniesCSIDHpublic key encryption
Contact author(s)
tomoki_moriya @ mist i u-tokyo ac jp
onuki @ mist i u-tokyo ac jp
takagi @ mist i u-tokyo ac jp
History
2020-10-06: revised
See all versions
Short URL
https://ia.cr/2020/613

CC BY

BibTeX

@misc{cryptoeprint:2020/613,
author = {Tomoki Moriya and Hiroshi Onuki and Tsuyoshi Takagi},
title = {SiGamal: A supersingular isogeny-based PKE and its application to a PRF},
howpublished = {Cryptology ePrint Archive, Paper 2020/613},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/613}},
url = {https://eprint.iacr.org/2020/613}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.