Cryptology ePrint Archive: Report 2020/1178

An Efficient Authenticated Key Exchange from Random Self-Reducibility on CSIDH

Tomoki Kawashima and Katsuyuki Takashima and Yusuke Aikawa and Tsuyoshi Takagi

Abstract: SIDH and CSIDH are key exchange protocols based on isogenies and conjectured to be quantum-resistant. Since their protocols are similar to the classical Diffie–Hellman, they are vulnerable to the man-in-the-middle attack. A key exchange which is resistant to such an attack is called an authenticated key exchange (AKE), and many isogeny-based AKEs have been proposed. However, none of them are efficient in that they all have relatively large security losses. This is partially because the random self-reducibility of isogeny-based decisional problems has not been proved yet. In this paper, we show that the computational problem and the gap problem of CSIDH are random self-reducible. A gap problem is a computational problem given access to the corresponding decision oracle. Moreover, we propose a CSIDH-based AKE with small security loss, following the construction of Cohn-Gordon et al. at CRYPTO 2019, as an application of the random self-reducibility of the gap problem of CSIDH. Our AKE is proved to be the fastest CSIDH-based AKE when we aim at 110-bit security level.

Category / Keywords: post-quantum · tight security · authenticated key exchange · isogeny-based cryptography · CSIDH

Date: received 26 Sep 2020, last revised 30 Sep 2020

Contact author: tomoki_kawashima at mist i u-tokyo ac jp

Available format(s): PDF | BibTeX Citation

Version: 20200930:080934 (All versions of this report)

Short URL: ia.cr/2020/1178