Paper 2023/317
The special case of cyclotomic fields in quantum algorithms for unit groups
, Centre National de la Recherche ScientifiqueAbstract
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 $\mathbb{Q}(\zeta_m+\zeta_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 $\mathcal{O}_K$-lattices.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- unit groupsquantum algorithmslatticescyclotomic fieldscyclotomic 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}
}
