Paper 2023/1054
Quantum Complexity for Discrete Logarithms and Related Problems
Abstract
This paper studies the quantum computational complexity of the discrete logarithm (DL) and related group-theoretic problems in the context of ``generic algorithms''---that is, algorithms that do not exploit any properties of the group encoding.
We establish the quantum generic group model and hybrid classical-quantum generic group model as quantum and hybrid analogs of their classical counterpart. This model counts the number of group operations of the underlying cyclic group
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in CRYPTO 2024
- Keywords
- Quantum lower boundsShor's algorithmGeneric group model
- Contact author(s)
-
minkihhan @ kias re kr
takashi yamakawa @ ntt com
aaramyun @ g ewha ac kr - History
- 2024-07-05: last of 2 revisions
- 2023-07-05: received
- See all versions
- Short URL
- https://ia.cr/2023/1054
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1054, author = {Minki Hhan and Takashi Yamakawa and Aaram Yun}, title = {Quantum Complexity for Discrete Logarithms and Related Problems}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1054}, year = {2023}, url = {https://eprint.iacr.org/2023/1054} }