The system will be going down for regular maintenance. Please save your work and logout.
The special case of cyclotomic fields in quantum algorithms for unit groups
BARBULESCU, Razvan
Lithe and fast algorithmic number theory [LFANT]
Analyse cryptographique et arithmétique [CANARI]
Lithe and fast algorithmic number theory [LFANT]
Analyse cryptographique et arithmétique [CANARI]
BARBULESCU, Razvan
Lithe and fast algorithmic number theory [LFANT]
Analyse cryptographique et arithmétique [CANARI]
< Reduce
Lithe and fast algorithmic number theory [LFANT]
Analyse cryptographique et arithmétique [CANARI]
Language
en
Communication dans un congrès
This item was published in
Progress in cryptology -- AFRICACRYPT 2023Lecture notes in computer science (LNCS), Progress in cryptology -- AFRICACRYPT 2023Lecture notes in computer science (LNCS), AFRICACRYPT 2023, 2023-07-18, Soussa. 2023-07-21, vol. 14064, p. 229
Springer
English Abstract
Unit group computations are a cryptographic primitive for which one has a fast quantum algorithm, but the required number of qubits is Õ(m 5). In this work we propose a modification of the algorithm for which the number ...Read more >
Unit group computations are a cryptographic primitive for which one has a fast quantum algorithm, but the required number of qubits is Õ(m 5). In this work we propose a modification of the algorithm for which the number of qubits is Õ(m 2) in the case of cyclotomic fields. Moreover, under a recent conjecture on the size of the class group of $ \mathbb{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 thanks to the Buchmann-Pohst algorithm over OK-lattices.Read less <
English Keywords
Quantum algorithms
unit groups
Cyclotomic fields
lattices
Origin
Hal imported
