Paper 2024/948

Return of the Kummer: a Toolbox for Genus-2 Cryptography

Maria Corte-Real Santos, University College London
Krijn Reijnders, Radboud University Nijmegen
Abstract

This work expands the machinery we have for isogeny-based cryptography in genus 2 by developing a toolbox of several essential algorithms for Kummer surfaces, the dimension-2 analogue of $x$-only arithmetic on elliptic curves. Kummer surfaces have been suggested in hyper-elliptic curve cryptography since at least the 1980s and recently these surfaces have reappeared to efficiently compute $(2,2)$-isogenies. We construct several essential analogues of techniques used in one-dimensional isogeny-based cryptography, such as pairings, deterministic point sampling and point compression and give an overview of $(2,2)$-isogenies on Kummer surfaces. We furthermore show how Scholten's construction can be used to transform isogeny-based cryptography over elliptic curves over $\mathbb{F}_{p^2}$ into protocols over Kummer surfaces over $\mathbb{F}_{p}$ As an example of this approach, we demonstrate that SQIsign verification can be performed completely on Kummer surfaces, and, therefore, that one-dimensional SQIsign verification can be viewed as a two-dimensional isogeny between products of elliptic curves. Curiously, the isogeny is then defined over $\mathbb{F}_{p}$ rather than $\mathbb{F}_{p^2}$. Contrary to expectation, the cost of SQIsign verification using Kummer surfaces does not explode: verification costs only 1.5$\times$ more in terms of finite field operations than the SQIsign variant AprèsSQI, optimised for fast verification. Furthermore, it is plausible that arithmetic on Kummer surfaces can be efficiently vectorised, giving Kummer-based protocols over $\mathbb{F}_{p}$ a potential performance boost on modern architectures, possibly surpassing the performance of elliptic-curve analogues over $\mathbb{F}_{p^2}$

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
post-quantum cryptographyisogeniesKummer surfaceSQIsigngenus 2
Contact author(s)
maria santos 20 @ ucl ac uk
krijn @ cs ru nl
History
2024-08-14: last of 2 revisions
2024-06-13: received
See all versions
Short URL
https://ia.cr/2024/948
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2024/948,
      author = {Maria Corte-Real Santos and Krijn Reijnders},
      title = {Return of the Kummer: a Toolbox for Genus-2 Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/948},
      year = {2024},
      url = {https://eprint.iacr.org/2024/948}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.