Paper 2018/376

Arithmetic Considerations for Isogeny Based Cryptography

Joppe W. Bos and Simon Friedberger

Abstract

In this paper we investigate various arithmetic techniques which can be used to potentially enhance the performance in the supersingular isogeny Diffie-Hellman (SIDH) key-exchange protocol which is one of the more recent contenders in the post-quantum public-key arena. Firstly, we give a systematic overview of techniques to compute efficient arithmetic modulo $2^xp^y\pm 1$. Our overview shows that in the SIDH setting, where arithmetic over a quadratic extension field is required, the approaches based on Montgomery reduction for such primes of a special shape are to be preferred. Moreover, the outcome of our investigation reveals that there exist moduli which allow even faster implementations. Secondly, we investigate if it is beneficial to use other curve models to speed-up the elliptic curve scalar multiplication. The use of twisted Edwards curves allows one to search for efficient addition-subtraction chains for fixed scalars while this is not possible with the differential addition law when using Montgomery curves. Our preliminary results show that despite the fact that we found such efficient chains, using twisted Edwards curves does not result in faster scalar multiplication arithmetic in the setting of SIDH.

Note: This is an extended version of https://eprint.iacr.org/2016/986.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
joppe bos @ nxp com
History
2018-05-01: revised
2018-04-30: received
See all versions
Short URL
https://ia.cr/2018/376
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/376,
      author = {Joppe W.  Bos and Simon Friedberger},
      title = {Arithmetic Considerations for Isogeny Based Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2018/376},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/376}},
      url = {https://eprint.iacr.org/2018/376}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.