Paper 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.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Contact author(s)
- tomoki_kawashima @ mist i u-tokyo ac jp
- History
- 2020-11-20: last of 2 revisions
- 2020-09-30: received
- See all versions
- Short URL
- https://ia.cr/2020/1178
- License
-
CC BY