Paper 2022/1103
Speeding-Up Parallel Computation of Large Smooth-Degree Isogeny using Precedence-Constrained Scheduling
Abstract
Although the supersingular isogeny Diffie-Hellman (SIDH) protocol is one of the most promising post-quantum cryptosystems, it is significantly slower than its main counterparts due to the underlying large smooth-degree isogeny computation. In this work, we address the problem of evaluating and constructing a strategy for computing the large smooth-degree isogeny in the multi-processor setting by formulating them as scheduling problems with dependencies. The contribution of this work is two-fold. For the strategy evaluation, we transform strategies into task dependency graphs and apply precedence-constrained scheduling algorithms to them in order to find their costs. For the strategy construction, we construct strategies from smaller parts that are optimal solutions of integer programming representing the problem. We show via experiments that the proposed two techniques together offer more than 13% reduction in the strategy costs compared to the best current results by Hutchinson and Karabina presented at Indocrypt 2018.
Note: This paper is accepted and will appear in the 27th Australasian Conference on Information Security and Privacy (ACISP 2022).
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- SIDH Isogeny-based cryptography Parallel computing Precedence-constrained scheduling
- Contact author(s)
-
kphalakarn @ uwaterloo ca
vorapong @ is s u-tokyo ac jp
ahasan @ uwaterloo ca - History
- 2022-08-29: revised
- 2022-08-26: received
- See all versions
- Short URL
- https://ia.cr/2022/1103
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1103,
author = {Kittiphon Phalakarn and Vorapong Suppakitpaisarn and M. Anwar Hasan},
title = {Speeding-Up Parallel Computation of Large Smooth-Degree Isogeny using Precedence-Constrained Scheduling},
howpublished = {Cryptology ePrint Archive, Paper 2022/1103},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1103}},
url = {https://eprint.iacr.org/2022/1103}
}
