Vectorized and Parallel Computation of Large Smooth-Degree Isogenies using Precedence-Constrained Scheduling
Strategies and their evaluations play important roles in speeding up the computation of large smooth-degree isogenies. The concept of optimal strategies for such computation was introduced by De Feo et al., and virtually all implementations of isogeny-based protocols have adopted this approach, whi...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2023-06-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/10963 |
| _version_ | 1797807374935785472 |
|---|---|
| author | Kittiphon Phalakarn Vorapong Suppakitpaisarn Francisco Rodríguez-Henríquez M. Anwar Hasan |
| author_facet | Kittiphon Phalakarn Vorapong Suppakitpaisarn Francisco Rodríguez-Henríquez M. Anwar Hasan |
| author_sort | Kittiphon Phalakarn |
| collection | DOAJ |
| description |
Strategies and their evaluations play important roles in speeding up the computation of large smooth-degree isogenies. The concept of optimal strategies for such computation was introduced by De Feo et al., and virtually all implementations of isogeny-based protocols have adopted this approach, which is provably optimal for single-core platforms. In spite of its inherent sequential nature, several recent works have studied ways of speeding up this isogeny computation by exploiting the rich parallelism available in vectorized and multi-core platforms. One obstacle to taking full advantage of this parallelism, however, is that De Feo et al.’s strategies are not necessarily optimal in multi-core environments. To illustrate how the speed of vectorized and parallel isogeny computation can be improved at the strategylevel, we present two novel software implementations that utilize a state-of-the-art evaluation technique, called precedence-constrained scheduling (PCS), presented by Phalakarn et al., with our proposed strategies crafted for these environments. Our first implementation relies only on the parallelism provided by multi-core processors. The second implementation targets multi-core processors supporting the latest generation of the Intel’s Advanced Vector eXtensions (AVX) technology, commonly known as AVX-512IFMA instructions. To better handle the computational concurrency associated with PCS, we equip both implementations with extensive synchronization techniques. Our first implementation outperforms the implementation of Cervantes-Vázquez et al. by yielding up to 14.36% reduction in the execution time, when targeting platforms with two- to four-core processors. Our second implementation, equipped with four cores, achieves up to 34.05% reduction in the execution time compared to the single-core implementation of Cheng et al. of CHES 2022.
|
| first_indexed | 2024-03-13T06:21:32Z |
| format | Article |
| id | doaj.art-45f00fd79742494bb9182a839c972c7f |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-03-13T06:21:32Z |
| publishDate | 2023-06-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-45f00fd79742494bb9182a839c972c7f2023-06-09T15:49:38ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252023-06-012023310.46586/tches.v2023.i3.246-269Vectorized and Parallel Computation of Large Smooth-Degree Isogenies using Precedence-Constrained SchedulingKittiphon Phalakarn0Vorapong Suppakitpaisarn1Francisco Rodríguez-Henríquez2M. Anwar Hasan3University of Waterloo, Waterloo, CanadaThe University of Tokyo, Tokyo, JapanCINVESTAV-IPN, Mexico City, Mexico; Technology Innovation Institute, Abu Dhabi, UAEUniversity of Waterloo, Waterloo, Canada Strategies and their evaluations play important roles in speeding up the computation of large smooth-degree isogenies. The concept of optimal strategies for such computation was introduced by De Feo et al., and virtually all implementations of isogeny-based protocols have adopted this approach, which is provably optimal for single-core platforms. In spite of its inherent sequential nature, several recent works have studied ways of speeding up this isogeny computation by exploiting the rich parallelism available in vectorized and multi-core platforms. One obstacle to taking full advantage of this parallelism, however, is that De Feo et al.’s strategies are not necessarily optimal in multi-core environments. To illustrate how the speed of vectorized and parallel isogeny computation can be improved at the strategylevel, we present two novel software implementations that utilize a state-of-the-art evaluation technique, called precedence-constrained scheduling (PCS), presented by Phalakarn et al., with our proposed strategies crafted for these environments. Our first implementation relies only on the parallelism provided by multi-core processors. The second implementation targets multi-core processors supporting the latest generation of the Intel’s Advanced Vector eXtensions (AVX) technology, commonly known as AVX-512IFMA instructions. To better handle the computational concurrency associated with PCS, we equip both implementations with extensive synchronization techniques. Our first implementation outperforms the implementation of Cervantes-Vázquez et al. by yielding up to 14.36% reduction in the execution time, when targeting platforms with two- to four-core processors. Our second implementation, equipped with four cores, achieves up to 34.05% reduction in the execution time compared to the single-core implementation of Cheng et al. of CHES 2022. https://tches.iacr.org/index.php/TCHES/article/view/10963Isogeny-based cryptographyIsogeny computationSoftware optimizationVectorizationParallel computingPrecedence-constrained scheduling |
| spellingShingle | Kittiphon Phalakarn Vorapong Suppakitpaisarn Francisco Rodríguez-Henríquez M. Anwar Hasan Vectorized and Parallel Computation of Large Smooth-Degree Isogenies using Precedence-Constrained Scheduling Transactions on Cryptographic Hardware and Embedded Systems Isogeny-based cryptography Isogeny computation Software optimization Vectorization Parallel computing Precedence-constrained scheduling |
| title | Vectorized and Parallel Computation of Large Smooth-Degree Isogenies using Precedence-Constrained Scheduling |
| title_full | Vectorized and Parallel Computation of Large Smooth-Degree Isogenies using Precedence-Constrained Scheduling |
| title_fullStr | Vectorized and Parallel Computation of Large Smooth-Degree Isogenies using Precedence-Constrained Scheduling |
| title_full_unstemmed | Vectorized and Parallel Computation of Large Smooth-Degree Isogenies using Precedence-Constrained Scheduling |
| title_short | Vectorized and Parallel Computation of Large Smooth-Degree Isogenies using Precedence-Constrained Scheduling |
| title_sort | vectorized and parallel computation of large smooth degree isogenies using precedence constrained scheduling |
| topic | Isogeny-based cryptography Isogeny computation Software optimization Vectorization Parallel computing Precedence-constrained scheduling |
| url | https://tches.iacr.org/index.php/TCHES/article/view/10963 |
| work_keys_str_mv | AT kittiphonphalakarn vectorizedandparallelcomputationoflargesmoothdegreeisogeniesusingprecedenceconstrainedscheduling AT vorapongsuppakitpaisarn vectorizedandparallelcomputationoflargesmoothdegreeisogeniesusingprecedenceconstrainedscheduling AT franciscorodriguezhenriquez vectorizedandparallelcomputationoflargesmoothdegreeisogeniesusingprecedenceconstrainedscheduling AT manwarhasan vectorizedandparallelcomputationoflargesmoothdegreeisogeniesusingprecedenceconstrainedscheduling |