Session A3 - Computational Number Theory
July 11, 18:20 ~ 19:00 - Room B6
Kummer arithmetic and compact signature schemes
Inria and École polytechnique, France - firstname.lastname@example.org
The Kummer surfaces of certain genus 2 curves offer fast scalar multiplication algorithms with a measure of built-in resistance to basic side-channel attacks. The corresponding algorithms for the Jacobians of these curves are far slower, more complicated, and are ultimately not competitive with elliptic curve-based cryptographic implementations. When implementing discrete logarithm-based signature schemes such as Schnorr signatures (and generalizations of ECDSA), the group structure on the Jacobian appears essential.
In recent work with Chung and Costello, we proposed algorithms to compute Jacobian-based signatures while exploiting the speed and safety of Kummer arithmetic. Moving from theory to practice, these algorithms were subsequently implemented for microcontroller platforms (with very limited computing resources) in joint work with Renes, Schwabe, and Batina; the results provided easily the most efficient secure signatures for microcontrollers to date. However, the increase in speed comes at the cost of heavy memory usage, largely due to the complicated formulae relating fast Kummer surfaces with their Jacobians.
In this talk we explain how to remove Jacobians from the picture entirely, presenting the first signature schemes requiring only Kummer arithmetic. The result is faster, simpler signatures with a much smaller memory footprint, suitable for use in constrained environments.
Joint work with Joost Renes (Radboud University Nijmegen, The Netherlands).