Cryptology ePrint Archive: Report 2020/244

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

Andrea Basso and Péter Kutas and Simon-Philipp Merz and 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.

Category / Keywords: public-key cryptography / cryptanalysis, elliptic curves, isogenies, k-SIDH

Original Publication (in the same form): AFRICACRYPT 2020

Date: received 23 Feb 2020, last revised 30 Apr 2020

Contact author: a basso at cs bham ac uk, kutasp at gmail com, simon-philipp merz 2018 at rhul ac uk, christophe f petit at gmail com, c weitkaemper at pgr bham ac uk

Available format(s): PDF | BibTeX Citation

Version: 20200430:233238 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]