Paper 2018/792
Faster Modular Arithmetic For Isogeny Based Crypto on Embedded Devices
Joppe W. Bos and Simon J. Friedberger
Abstract
We show how to implement the Montgomery reduction algorithm for isogeny based cryptography such that it can utilize the "unsigned multiply accumulate accumulate long" instruction present on modern ARM architectures. This results in a practical speed-up of a factor 1.34 compared to the approach used by SIKE: the supersingular isogeny based submission to the ongoing post-quantum standardization effort. Moreover, motivated by the recent work of Costello and Hisil (ASIACRYPT 2017), which shows that there is only a moderate degradation in performance when evaluating large odd degree isogenies, we search for more general supersingular isogeny friendly moduli. Using graphics processing units to accelerate this search we find many such moduli which allow for faster implementations on embedded devices. By combining these two approaches we manage to make the modular reduction 1.5 times as fast on a 32-bit ARM platform.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Contact author(s)
- joppe bos @ nxp com
- History
- 2018-09-01: received
- Short URL
- https://ia.cr/2018/792
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/792,
author = {Joppe W. Bos and Simon J. Friedberger},
title = {Faster Modular Arithmetic For Isogeny Based Crypto on Embedded Devices},
howpublished = {Cryptology ePrint Archive, Paper 2018/792},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/792}},
url = {https://eprint.iacr.org/2018/792}
}
