On adaptive attacks against jao-urbanik’s isogeny-based protocol

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

External organisations

  • Royal Holloway University of London
  • University of Birmingham

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.

Bibliographic note

Funding Information: We would like to thank David Jao and David Urbanik for their valuable comments and feedback on this work. Furthermore, we are grateful to Samuel Dobson, Steven D. Galbraith, Jason LeGrow, Yan Bo Ti, and Lukas Zobernig for their helpful clarifications regarding the DGLTZ attack. Work by the second and fourth authors was supported by an EPSRC New Investigator grant (EP/S01361X/1). Publisher Copyright: © Springer Nature Switzerland AG 2020.

Details

Original languageEnglish
Title of host publicationProgress in Cryptology - AFRICACRYPT 2020 - 12th International Conference on Cryptology in Africa, Proceedings
EditorsAbderrahmane Nitaj, Amr Youssef
Publication statusPublished - 2020
Event12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020 - Cairo, Egypt
Duration: 20 Jul 202022 Jul 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12174 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020
CountryEgypt
CityCairo
Period20/07/2022/07/20

Keywords

  • Adaptive attack, Elliptic curves, Isogenies, k-SIDH