An Algorithm for Efficient Detection of (N, N)-Splittings and Its Application to the Isogeny Problem in Dimension 2

Maria  Corte-Real Santos; Craig Costello; Sam Frengley

doi:10.1007/978-3-031-57725-3_6

An Algorithm for Efficient Detection of (N, N)-Splittings and Its Application to the Isogeny Problem in Dimension 2

Maria Corte-Real Santos^*, Craig Costello, Sam Frengley

^*Corresponding author for this work

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

1 Citation (Scopus)

26 Downloads (Pure)

Abstract

We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally (N, N)-split for each integer N ≤ 11. Incorporating this algorithm into the best-known attack against the superspecial isogeny problem in dimension 2 (due to Costello and Smith) gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime p is 100 bits, the attack is sped up by a factor of 25; when the underlying prime is 200 bits, the attack is sped up by a factor of 42; and, when the underlying prime is 1000 bits, the attack is sped up by a factor of 160.

Original language	English
Title of host publication	Public-Key Cryptography - PKC 2024
Subtitle of host publication	27th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
Editors	Qiang Tang, Vanessa Teague
Publisher	Springer, Cham
Pages	157-189
Number of pages	33
Volume	14603
ISBN (Electronic)	9783031577253
ISBN (Print)	9783031577246
DOIs	https://doi.org/10.1007/978-3-031-57725-3_6
Publication status	Published - 14 Apr 2024
Event	27th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2024 - Sydney, Australia Duration: 15 Apr 2024 → 17 Apr 2024 https://pkc.iacr.org/2024/

Publication series

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

Conference

Conference	27th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2024
Abbreviated title	PKC 2024
Country/Territory	Australia
City	Sydney
Period	15/04/24 → 17/04/24
Internet address	https://pkc.iacr.org/2024/

Bibliographical note

Publisher Copyright:
© 2024 International Association for Cryptologic Research.

Access to Document

10.1007/978-3-031-57725-3_6Licence: Unspecified

Full-text PDF (accepted manuscript)
This is the accepted author manuscript (AAM) of the article which has been made Open Access under the University of Bristol's Scholarly Works Policy. The final published version (Version of Record) can be found on the publisher's website. The copyright of any third-party content, such as images, remains with the copyright holder.
Accepted author manuscript, 678 KBLicence: CC BY

https://eprint.iacr.org/2022/1736Licence: CC BY

Handle.net

Persistent link

Cite this

Corte-Real Santos, M., Costello, C., & Frengley, S. (2024). An Algorithm for Efficient Detection of (N, N)-Splittings and Its Application to the Isogeny Problem in Dimension 2. In Q. Tang, & V. Teague (Eds.), Public-Key Cryptography - PKC 2024: 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings (Vol. 14603, pp. 157-189). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14603 LNCS). Springer, Cham. https://doi.org/10.1007/978-3-031-57725-3_6

Corte-Real Santos, Maria ; Costello, Craig ; Frengley, Sam. / An Algorithm for Efficient Detection of (N, N)-Splittings and Its Application to the Isogeny Problem in Dimension 2. Public-Key Cryptography - PKC 2024: 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. editor / Qiang Tang ; Vanessa Teague. Vol. 14603 Springer, Cham, 2024. pp. 157-189 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{56def8af772d4af4a1217810cd598566,

title = "An Algorithm for Efficient Detection of (N, N)-Splittings and Its Application to the Isogeny Problem in Dimension 2",

abstract = "We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally (N, N)-split for each integer N ≤ 11. Incorporating this algorithm into the best-known attack against the superspecial isogeny problem in dimension 2 (due to Costello and Smith) gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime p is 100 bits, the attack is sped up by a factor of 25; when the underlying prime is 200 bits, the attack is sped up by a factor of 42; and, when the underlying prime is 1000 bits, the attack is sped up by a factor of 160.",

author = "\{Corte-Real Santos\}, Maria and Craig Costello and Sam Frengley",

note = "Publisher Copyright: {\textcopyright} 2024 International Association for Cryptologic Research.; 27th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2024, PKC 2024 ; Conference date: 15-04-2024 Through 17-04-2024",

year = "2024",

month = apr,

day = "14",

doi = "10.1007/978-3-031-57725-3\_6",

language = "English",

isbn = "9783031577246",

volume = "14603",

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

publisher = "Springer, Cham",

pages = "157--189",

editor = "Qiang Tang and Vanessa Teague",

booktitle = "Public-Key Cryptography - PKC 2024",

address = "Switzerland",

url = "https://pkc.iacr.org/2024/",

}

Corte-Real Santos, M, Costello, C & Frengley, S 2024, An Algorithm for Efficient Detection of (N, N)-Splittings and Its Application to the Isogeny Problem in Dimension 2. in Q Tang & V Teague (eds), Public-Key Cryptography - PKC 2024: 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. vol. 14603, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14603 LNCS, Springer, Cham, pp. 157-189, 27th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2024, Sydney, New South Wales, Australia, 15/04/24. https://doi.org/10.1007/978-3-031-57725-3_6

An Algorithm for Efficient Detection of (N, N)-Splittings and Its Application to the Isogeny Problem in Dimension 2. / Corte-Real Santos, Maria ; Costello, Craig; Frengley, Sam.
Public-Key Cryptography - PKC 2024: 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. ed. / Qiang Tang; Vanessa Teague. Vol. 14603 Springer, Cham, 2024. p. 157-189 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14603 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - An Algorithm for Efficient Detection of (N, N)-Splittings and Its Application to the Isogeny Problem in Dimension 2

AU - Corte-Real Santos, Maria

AU - Costello, Craig

AU - Frengley, Sam

PY - 2024/4/14

Y1 - 2024/4/14

N2 - We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally (N, N)-split for each integer N ≤ 11. Incorporating this algorithm into the best-known attack against the superspecial isogeny problem in dimension 2 (due to Costello and Smith) gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime p is 100 bits, the attack is sped up by a factor of 25; when the underlying prime is 200 bits, the attack is sped up by a factor of 42; and, when the underlying prime is 1000 bits, the attack is sped up by a factor of 160.

AB - We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally (N, N)-split for each integer N ≤ 11. Incorporating this algorithm into the best-known attack against the superspecial isogeny problem in dimension 2 (due to Costello and Smith) gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime p is 100 bits, the attack is sped up by a factor of 25; when the underlying prime is 200 bits, the attack is sped up by a factor of 42; and, when the underlying prime is 1000 bits, the attack is sped up by a factor of 160.

U2 - 10.1007/978-3-031-57725-3_6

DO - 10.1007/978-3-031-57725-3_6

M3 - Conference Contribution (Conference Proceeding)

SN - 9783031577246

VL - 14603

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

SP - 157

EP - 189

BT - Public-Key Cryptography - PKC 2024

A2 - Tang, Qiang

A2 - Teague, Vanessa

PB - Springer, Cham

T2 - 27th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2024

Y2 - 15 April 2024 through 17 April 2024

ER -

Corte-Real Santos M, Costello C, Frengley S. An Algorithm for Efficient Detection of (N, N)-Splittings and Its Application to the Isogeny Problem in Dimension 2. In Tang Q, Teague V, editors, Public-Key Cryptography - PKC 2024: 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. Vol. 14603. Springer, Cham. 2024. p. 157-189. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-57725-3_6