Paper 2015/983

Fast, uniform, and compact scalar multiplication for elliptic curves and genus 2 Jacobians with applications to signature schemes

Ping Ngai Chung, Craig Costello, and Benjamin Smith

Abstract

We give a general framework for uniform, constant-time one- and two-dimensional scalar multiplication algorithms for elliptic curves and Jacobians of genus~2 curves that operate by projecting to the \(x\)-line or Kummer surface, where we can exploit faster and more uniform pseudomultiplication, before recovering the proper ``signed'' output back on the curve or Jacobian. This extends the work of López and Dahab, Okeya and Sakurai, and Brier and Joye to genus~2, and also to two-dimensional scalar multiplication. Our results show that many existing fast pseudomultiplication implementations (hitherto limited to applications in Diffie--Hellman key exchange) can be wrapped with simple and efficient pre- and post-computations to yield competitive full scalar multiplication algorithms, ready for use in more general discrete logarithm-based cryptosystems, including signature schemes. This is especially interesting for genus~2, where Kummer surfaces can outperform comparable elliptic curve systems. As an example, we construct an instance of the Schnorr signature scheme driven by Kummer surface arithmetic.

Note: Added further bibliography.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
elliptic curve cryptographyhyperelliptic curve cryptographyscalar multiplicationsignatures
Contact author(s)
smith @ lix polytechnique fr
History
2015-10-19: revised
2015-10-12: received
See all versions
Short URL
https://ia.cr/2015/983
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/983,
      author = {Ping Ngai Chung and Craig Costello and Benjamin Smith},
      title = {Fast, uniform, and compact scalar multiplication for elliptic curves and genus 2 Jacobians with applications to signature schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2015/983},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/983}},
      url = {https://eprint.iacr.org/2015/983}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.