On adaptive attacks against Jao-Urbanik's isogeny-based protocol

Andrea Basso; Peter Kutas; Simon-Philipp Merz; Christophe Petit; Charlotte Weitkaemper

doi:10.1007/978-3-030-51938-4_10

On adaptive attacks against Jao-Urbanik's isogeny-based protocol

Andrea Basso, Peter Kutas, Simon-Philipp Merz, Christophe Petit, Charlotte Weitkaemper

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

25 Downloads (Pure)

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 naive 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.

Original language	English
Title of host publication	Progress in Cryptology - AFRICACRYPT 2020
Subtitle of host publication	12th International Conference on Cryptology in Africa, Cairo, Egypt, July 20 – 22, 2020, Proceedings
Editors	Abderrahmane Nitaj, Amr Youssef
Publisher	Springer
Pages	195-213
Number of pages	19
Edition	1
ISBN (Electronic)	9783030519384
ISBN (Print)	9783030519377
DOIs	https://doi.org/10.1007/978-3-030-51938-4_10
Publication status	Published - 5 Jul 2020
Event	12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020 - Cairo, Egypt Duration: 20 Jul 2020 → 22 Jul 2020

Publication series

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

Conference

Conference	12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020
Country/Territory	Egypt
City	Cairo
Period	20/07/20 → 22/07/20

Bibliographical 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.

Keywords

Elliptic curves
Isogenies
k-SIDH
Adaptive attack

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-030-51938-4_10

BassoA2020Adaptive
This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/978-3-030-51938-4_10. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms
Accepted author manuscript, 383 KBLicence: Other (please specify with Rights Statement)

Cite this

Basso, A., Kutas, P., Merz, S-P., Petit, C., & Weitkaemper, C. (2020). On adaptive attacks against Jao-Urbanik's isogeny-based protocol. In A. Nitaj, & A. Youssef (Eds.), Progress in Cryptology - AFRICACRYPT 2020: 12th International Conference on Cryptology in Africa, Cairo, Egypt, July 20 – 22, 2020, Proceedings (1 ed., pp. 195-213). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12174 LNCS). Springer. https://doi.org/10.1007/978-3-030-51938-4_10

Basso, Andrea ; Kutas, Peter ; Merz, Simon-Philipp et al. / On adaptive attacks against Jao-Urbanik's isogeny-based protocol. Progress in Cryptology - AFRICACRYPT 2020: 12th International Conference on Cryptology in Africa, Cairo, Egypt, July 20 – 22, 2020, Proceedings. editor / Abderrahmane Nitaj ; Amr Youssef. 1. ed. Springer, 2020. pp. 195-213 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f674f69bfb664d87a4c8bccd95846d49,

title = "On adaptive attacks against Jao-Urbanik's isogeny-based protocol",

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 naive 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.",

keywords = "Elliptic curves, Isogenies, k-SIDH, Adaptive attack",

author = "Andrea Basso and Peter Kutas and Simon-Philipp Merz and Christophe Petit and Charlotte Weitkaemper",

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: {\textcopyright} Springer Nature Switzerland AG 2020.; 12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020 ; Conference date: 20-07-2020 Through 22-07-2020",

year = "2020",

month = jul,

day = "5",

doi = "10.1007/978-3-030-51938-4_10",

language = "English",

isbn = "9783030519377",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "195--213",

editor = "Nitaj, {Abderrahmane } and Amr Youssef",

booktitle = "Progress in Cryptology - AFRICACRYPT 2020",

edition = "1",

}

Basso, A, Kutas, P, Merz, S-P, Petit, C & Weitkaemper, C 2020, On adaptive attacks against Jao-Urbanik's isogeny-based protocol. in A Nitaj & A Youssef (eds), Progress in Cryptology - AFRICACRYPT 2020: 12th International Conference on Cryptology in Africa, Cairo, Egypt, July 20 – 22, 2020, Proceedings. 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12174 LNCS, Springer, pp. 195-213, 12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020, Cairo, Egypt, 20/07/20. https://doi.org/10.1007/978-3-030-51938-4_10

On adaptive attacks against Jao-Urbanik's isogeny-based protocol. / Basso, Andrea; Kutas, Peter; Merz, Simon-Philipp et al.
Progress in Cryptology - AFRICACRYPT 2020: 12th International Conference on Cryptology in Africa, Cairo, Egypt, July 20 – 22, 2020, Proceedings. ed. / Abderrahmane Nitaj; Amr Youssef. 1. ed. Springer, 2020. p. 195-213 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12174 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On adaptive attacks against Jao-Urbanik's isogeny-based protocol

AU - Basso, Andrea

AU - Kutas, Peter

AU - Merz, Simon-Philipp

AU - Petit, Christophe

AU - Weitkaemper, Charlotte

N1 - 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.

PY - 2020/7/5

Y1 - 2020/7/5

N2 - 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 naive 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.

AB - 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 naive 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.

KW - Elliptic curves

KW - Isogenies

KW - k-SIDH

KW - Adaptive attack

UR - http://www.scopus.com/inward/record.url?scp=85088506386&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-51938-4_10

DO - 10.1007/978-3-030-51938-4_10

M3 - Conference contribution

AN - SCOPUS:85088506386

SN - 9783030519377

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 195

EP - 213

BT - Progress in Cryptology - AFRICACRYPT 2020

A2 - Nitaj, Abderrahmane

A2 - Youssef, Amr

PB - Springer

T2 - 12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020

Y2 - 20 July 2020 through 22 July 2020

ER -

Basso A, Kutas P, Merz S-P, Petit C, Weitkaemper C. On adaptive attacks against Jao-Urbanik's isogeny-based protocol. In Nitaj A, Youssef A, editors, Progress in Cryptology - AFRICACRYPT 2020: 12th International Conference on Cryptology in Africa, Cairo, Egypt, July 20 – 22, 2020, Proceedings. 1 ed. Springer. 2020. p. 195-213. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-51938-4_10

On adaptive attacks against Jao-Urbanik's isogeny-based protocol

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this