Regev's attack on hyperelliptic cryptosystems

Razvan Barbulescu; Gaetan Bisson

Paper 2024/2004

Regev's attack on hyperelliptic cryptosystems

Razvan Barbulescu

, Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest Research Centre

Gaetan Bisson, Laboratoire GAATI, University of French Polynesia

Abstract

Hyperelliptic curve cryptography (HECC) is a candidate to standardization which is a competitive alternative to elliptic curve cryptography (ECC). We extend Regev's algorithm to this setting. For genus-two curves relevant to cryptography, this yields a quantum attack up to nine times faster than the state-of-the-art. This implies that HECC is slightly weaker than ECC. In a more theoretical direction, we show that Regev's algorithm obtains its full speedup with respect to Shor's when the genus is high, a setting which is already known to be inadequate for cryptography.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: HECC quantum algorithms DLP
Contact author(s): razvan barbulescu @ u-bordeaux fr
bisson @ gaati org
History: 2024-12-13: revised; 2024-12-12: received; See all versions
Short URL: https://ia.cr/2024/2004
License: CC BY

BibTeX

@misc{cryptoeprint:2024/2004,
      author = {Razvan Barbulescu and Gaetan Bisson},
      title = {Regev's attack on hyperelliptic cryptosystems},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/2004},
      year = {2024},
      url = {https://eprint.iacr.org/2024/2004}
}