On Adaptive Attacks against Jao-Urbanik’s Isogeny-Based Protocol

Andrea Basso; Péter Kutas; Simon-Philipp Merz; Christophe Petit; Charlotte Weitkämper

Paper 2020/244

On Adaptive Attacks against Jao-Urbanik’s Isogeny-Based Protocol

Andrea Basso, Péter Kutas, Simon-Philipp Merz, Christophe Petit, and Charlotte Weitkämper

Abstract

The k-SIDH protocol is a static-static isogeny-based key agreement protocol. At Mathcrypt 2018, Jao and Urbanik introduced a variant of this protocol which uses non-scalar automorphisms of special elliptic curves to improve its efficiency. In this paper, we provide a new adaptive attack on Jao-Urbanik's protocol. The attack is a non-trivial adaptation of Galbraith-Petit-Shani-Ti's attack on SIDH (Asiacrypt 2016) and its extension to k-SIDH by Dobson-Galbraith-LeGrow-Ti-Zobernig (IACR eprint 2019). Our attack provides a speedup compared to a naïve application of Dobson et al.'s attack to Jao-Urbanik's scheme, exploiting its inherent structure. Estimating the security of k-SIDH and Jao-Urbanik's variant with respect to these attacks, k-SIDH provides better efficiency.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. AFRICACRYPT 2020
Keywords: cryptanalysis elliptic curves isogenies k-SIDH
Contact author(s): a basso @ cs bham ac uk
kutasp @ gmail com
simon-philipp merz 2018 @ rhul ac uk
christophe f petit @ gmail com
c weitkaemper @ pgr bham ac uk
History: 2020-04-30: revised; 2020-02-25: received; See all versions
Short URL: https://ia.cr/2020/244
License: CC BY

BibTeX

@misc{cryptoeprint:2020/244,
      author = {Andrea Basso and Péter Kutas and Simon-Philipp Merz and Christophe Petit and Charlotte Weitkämper},
      title = {On Adaptive Attacks against Jao-Urbanik’s Isogeny-Based Protocol},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/244},
      year = {2020},
      url = {https://eprint.iacr.org/2020/244}
}