Nguyen, Giang Nam ; Bischof, Christian (2023)
Task-based Parallelization Approach for Attacking the Supersingular Isogeny Path Problem.
2023 Australasian Computer Science Week. Melbourne, Australia (30.01.-03.02.2023)
doi: 10.1145/3579375.3579381
Konferenzveröffentlichung, Bibliographie
Kurzbeschreibung (Abstract)
The hardness of the supersingular isogeny (SSI) path problem is a crucial underpinning of isogeny-based cryptography. While the isogeny graphs emanating from various isogeny-based schemes might look differently, they only differ by the isogeny degrees, which determine the number of edges from a vertex in the graph.
Two generic algorithms for attacking the SSI path problem are the Meet-in-the-Middle (MiTM) and the van Oorschot-Wiener (vOW) algorithms. This paper proposes parallelization techniques using OpenMP tasking to accelerate the compute-intensive isogeny tree generation, an important and time-consuming building block in the two algorithms mentioned above.
Previous work considers a wide variety of computing platforms and different levels of parallelism to run MiTM and vOW, e.g., with multithreading on CPUs [1, 8], FPGAs [14], and GPGPUs [4].
On CPUs, known parallelization techniques employ static scheduling to distribute each isogeny subtree to a core. This scheduling requires programmers to manually compute the depth of the subtree regarding the number of cores available. Furthermore, this approach suffers from a load-balancing issue. To the best of our knowledge, our work is the first one considering tasking as a mechanism to parallelize such workloads. We demonstrate the advantage of our task-based approach on finding 2e-degree isogenies corresponding to seven SSI instances.
For MiTM, our approach enables use of a concurrent container from the Intel oneAPI template library [12] and reduces runtime by a factor of 40 on a machine with 96 CPU cores. The precomputation in vOW, a special case of MiTM, takes a significant amount of time in the total runtime of the algorithm, especially for large SSI instances. Hence, our implementation is based on the vOW4SIKE software [9], a state-of-the-art classical vOW implementation with optimized field arithmetic. Overall, then, our approach reduces the runtime of vOW by about 40%. While considering the 2-isogeny graph, we stress that our approach is relevant for parallelizing the attacks on SSI path problems regarding CSIDH [6] or SQiSign [10] by simply adapting the degree of the isogenies.
| Typ des Eintrags: | Konferenzveröffentlichung |
|---|---|
| Erschienen: | 2023 |
| Autor(en): | Nguyen, Giang Nam ; Bischof, Christian |
| Art des Eintrags: | Bibliographie |
| Titel: | Task-based Parallelization Approach for Attacking the Supersingular Isogeny Path Problem |
| Sprache: | Englisch |
| Publikationsjahr: | 13 März 2023 |
| Verlag: | ACM |
| Buchtitel: | ACSW '23: Proceedings of the 2023 Australasian Computer Science Week |
| Veranstaltungstitel: | 2023 Australasian Computer Science Week |
| Veranstaltungsort: | Melbourne, Australia |
| Veranstaltungsdatum: | 30.01.-03.02.2023 |
| DOI: | 10.1145/3579375.3579381 |
| URL / URN: | https://dl.acm.org/doi/10.1145/3579375.3579381 |
| Kurzbeschreibung (Abstract): | The hardness of the supersingular isogeny (SSI) path problem is a crucial underpinning of isogeny-based cryptography. While the isogeny graphs emanating from various isogeny-based schemes might look differently, they only differ by the isogeny degrees, which determine the number of edges from a vertex in the graph. Two generic algorithms for attacking the SSI path problem are the Meet-in-the-Middle (MiTM) and the van Oorschot-Wiener (vOW) algorithms. This paper proposes parallelization techniques using OpenMP tasking to accelerate the compute-intensive isogeny tree generation, an important and time-consuming building block in the two algorithms mentioned above. Previous work considers a wide variety of computing platforms and different levels of parallelism to run MiTM and vOW, e.g., with multithreading on CPUs [1, 8], FPGAs [14], and GPGPUs [4]. On CPUs, known parallelization techniques employ static scheduling to distribute each isogeny subtree to a core. This scheduling requires programmers to manually compute the depth of the subtree regarding the number of cores available. Furthermore, this approach suffers from a load-balancing issue. To the best of our knowledge, our work is the first one considering tasking as a mechanism to parallelize such workloads. We demonstrate the advantage of our task-based approach on finding 2e-degree isogenies corresponding to seven SSI instances. For MiTM, our approach enables use of a concurrent container from the Intel oneAPI template library [12] and reduces runtime by a factor of 40 on a machine with 96 CPU cores. The precomputation in vOW, a special case of MiTM, takes a significant amount of time in the total runtime of the algorithm, especially for large SSI instances. Hence, our implementation is based on the vOW4SIKE software [9], a state-of-the-art classical vOW implementation with optimized field arithmetic. Overall, then, our approach reduces the runtime of vOW by about 40%. While considering the 2-isogeny graph, we stress that our approach is relevant for parallelizing the attacks on SSI path problems regarding CSIDH [6] or SQiSign [10] by simply adapting the degree of the isogenies. |
| Freie Schlagworte: | Primitives, P1 |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Scientific Computing DFG-Sonderforschungsbereiche (inkl. Transregio) DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1119: CROSSING – Kryptographiebasierte Sicherheitslösungen als Grundlage für Vertrauen in heutigen und zukünftigen IT-Systemen |
| Hinterlegungsdatum: | 21 Mär 2023 10:37 |
| Letzte Änderung: | 18 Jul 2023 10:43 |
| PPN: | 509771998 |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum