Paper 2024/948

Return of the Kummer: a toolbox for genus 2 cryptography

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, as Kummer surfaces allow a much higher degree of parallelization, Kummer-based protocols over $\mathbb{F}_p$ could potentially outperform elliptic curve analogues over $\mathbb{F}_{p^2}$ in terms of clock cycles and actual performance.