Cryptology ePrint Archive: Report 2015/983
Fast, uniform, and compact scalar multiplication for elliptic curves and genus 2 Jacobians with applications to signature schemes
Ping Ngai Chung and 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.
Category / Keywords: implementation / elliptic curve cryptography, hyperelliptic curve cryptography, scalar multiplication, signatures
Date: received 11 Oct 2015, last revised 19 Oct 2015
Contact author: smith at lix polytechnique fr
Available format(s): PDF | BibTeX Citation
Note: Added further bibliography.
Version: 20151019:153210 (All versions of this report)
Short URL: ia.cr/2015/983
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]