Paper 2016/1045

On Fast Calculation of Addition Chains for Isogeny-Based Cryptography

Brian Koziel, Reza Azarderakhsh, David Jao, and Mehran Mozaffari-Kermani

Abstract

Addition chain calculations play a critical role in determining the efficiency of cryptosystems based on isogenies on elliptic curves. However, finding a minimal length addition chain is not easy; a generalized version of the problem, in which one must find a chain that simultaneously forms each of a sequence of values, is NP-complete. For the special primes used in such cryptosystems, finding fast addition chains for finite field arithmetic such as inversion and square root is also not easy. In this paper, we investigate the shape of smooth isogeny primes and propose new methods to calculate fast addition chains. Further, we also provide techniques to reduce the temporary register consumption of these large exponentials, applicable to both software and hardware implementations utilizing addition chains. Lastly, we utilize our procedures to compare multiple isogeny primes by the complexity of the addition chains.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. INSCRYPT2016
Keywords
Addition chainspost-quantum cryptographyisogeny-based cryptosystemsfinite field
Contact author(s)
azarderakhsh @ gmail com
kozielbrian @ gmail com
djao @ math uwaterloo ca
History
2016-11-07: received
Short URL
https://ia.cr/2016/1045
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1045,
      author = {Brian Koziel and Reza Azarderakhsh and David Jao and Mehran Mozaffari-Kermani},
      title = {On Fast Calculation of Addition Chains for Isogeny-Based Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1045},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1045}},
      url = {https://eprint.iacr.org/2016/1045}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.