The special case of cyclotomic fields in quantum algorithms for unit groups

Razvan Barbulescu; Adrien Poulalion

Paper 2023/317

The special case of cyclotomic fields in quantum algorithms for unit groups

Razvan Barbulescu

, Centre National de la Recherche Scientifique

Adrien Poulalion, Alice and Bob, Corps des Mines

Abstract

Unit group computations are a cryptographic primitive for which one has a fast quantum algorithm, but the required number of qubits is $\tilde{O} (m^{5})$ . In this work we propose a modification of the algorithm for which the number of qubits is $\tilde{O} (m^{2})$ in the case of cyclotomic fields. Moreover, under a recent conjecture on the size of the class group of $Q (ζ_{m} + ζ_{m}^{- 1})$ , the quantum algorithms is much simpler because it is a hidden subgroup problem (HSP) algorithm rather than its error estimation counterpart: continuous hidden subgroup problem (CHSP). We also discuss the (minor) speed-up obtained when exploiting Galois automorphisms thnaks to the Buchmann-Pohst algorithm over -lattices.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: unit groups quantum algorithms lattices cyclotomic fields cyclotomic units
Contact author(s): adrien poulalion @ mines org
History: 2023-03-03: approved; 2023-03-03: received; See all versions
Short URL: https://ia.cr/2023/317
License: CC BY

BibTeX

@misc{cryptoeprint:2023/317,
      author = {Razvan Barbulescu and Adrien Poulalion},
      title = {The special case of cyclotomic fields in quantum algorithms for unit groups},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/317},
      year = {2023},
      url = {https://eprint.iacr.org/2023/317}
}