Cryptology ePrint Archive: Report 2020/361

How Not to Create an Isogeny-Based PAKE

Reza Azarderakhsh and David Jao and Brian Koziel and Jason T. LeGrow and Vladimir Soukharev and Oleg Taraskin

Abstract: Isogeny-based key establishment protocols are believed to be resistant to quantum cryptanalysis. Two such protocols---supersingular isogeny Diffie-Hellman (SIDH) and commutative supersingular isogeny Diffie-Hellman (CSIDH)---are of particular interest because of their extremely small public key sizes compared with other post-quantum candidates. Although SIDH and CSIDH allow us to achieve key establishment against passive adversaries and authenticated key establishment (using generic constructions), there has been little progress in the creation of provably-secure isogeny-based password-authenticated key establishment protocols (PAKEs). This is in stark contrast with the classical setting, where the Diffie-Hellman protocol can be tweaked in a number of straightforward ways to construct PAKEs, such as EKE, SPEKE, PAK (and variants), J-PAKE, and Dragonfly. Although SIDH and CSIDH superficially resemble Diffie-Hellman, it is often difficult or impossible to ``translate'' these Diffie-Hellman-based protocols to the SIDH or CSIDH setting; worse still, even when the construction can be ``translated,'' the resultant protocol may be insecure, even if the Diffie-Hellman based protocol is secure. In particular, a recent paper of Terada and Yoneyama and ProvSec 2019 purports to instantiate encrypted key exchange (EKE) over SIDH and CSIDH; however, there is a subtle problem which leads to an offline dictionary attack on the protocol, rendering it insecure. In this work we present man-in-the-middle and offline dictionary attacks on isogeny-based PAKEs from the literature, and explain why other classical constructions do not ``translate'' securely to the isogeny-based setting.

Category / Keywords: cryptographic protocols / Isogeny-based cryptography, password-authenticated key exchange

Date: received 27 Mar 2020

Contact author: razarderakhsh at fau edu,djao@math uwaterloo ca,bkoziel2017@fau edu,Vladimir Soukharev@infosecglobal com,tog postquant@gmail com,jason legrow@uwaterloo ca

Available format(s): PDF | BibTeX Citation

Version: 20200328:152306 (All versions of this report)

Short URL: ia.cr/2020/361


[ Cryptology ePrint archive ]