Paper 2018/1199

Quantum Equivalence of the DLP and CDHP for Group Actions

Steven Galbraith, Lorenz Panny, Benjamin Smith, and Frederik Vercauteren

Abstract

In this short note we give a polynomial-time quantum reduction from the vectorization problem (DLP) to the parallelization problem (CDHP) for efficiently computable group actions. Combined with the trivial reduction from parallelization to vectorization, we thus prove the quantum equivalence of these problems, which is the post-quantum counterpart to classic results of den Boer and Maurer in the classical Diffie-Hellman setting. In contrast to the classical setting, our reduction holds unconditionally and does not assume knowledge of suitable auxiliary algebraic groups. We discuss the implications of this reduction for isogeny-based cryptosystems including CSIDH.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. to appear in Mathematical Cryptology
Keywords
quantum reductiongroup actiondiscrete-logarithm problemDLPcomputational Diffie-Hellman problemCDH
Contact author(s)
l s panny @ tue nl
History
2021-06-10: revised
2018-12-18: received
See all versions
Short URL
https://ia.cr/2018/1199
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1199,
      author = {Steven Galbraith and Lorenz Panny and Benjamin Smith and Frederik Vercauteren},
      title = {Quantum Equivalence of the DLP and CDHP for Group Actions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1199},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1199}},
      url = {https://eprint.iacr.org/2018/1199}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.