Regev’s Attack on Hyperelliptic Cryptosystems

An algorithm of Ekerå and Gärtner, inspired by Regev’s factoring algorithm, computes discrete logarithms in multiplicative groups of prime fields. Asymptotically, it has the same qubit and gate complexity as Shor’s algorithm but splits the computation into d independent, parallel runs. The optimal value of this parameter is d∼n where n is the bit size of the cryptographic group. We propose an extension of this algorithm to hyperelliptic curves. For curves of genus g∼n, which are not used in cryptography, we prove unconditionally that the optimal number of parallel runs d∼n can still be achieved. For genus-two curves, we propose a heuristic algorithm. While its runtime speedup is difficult to quantify in general, we show that it can be expected to use up to d=8 parallel runs for specific curves relevant to cryptography, including GLV-friendly and pairing-friendly curves.