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 the 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, the parameter sizes of the existing schemes should be large since they all have relatively large security losses in security proofs. 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. in 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 19 Nov 2020
Contact author: tomoki_kawashima at mist i u-tokyo ac jp
Available format(s): PDF | BibTeX Citation
Version: 20201120:052133 (All versions of this report)
Short URL: ia.cr/2020/1178
[ Cryptology ePrint archive ]