Paper 2022/1103

Speeding-Up Parallel Computation of Large Smooth-Degree Isogeny using Precedence-Constrained Scheduling

Kittiphon Phalakarn, University of Waterloo
Vorapong Suppakitpaisarn, University of Tokyo
M. Anwar Hasan, University of Waterloo
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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2022/1103}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.