Quantum Equivalence of the DLP and CDHP for Group Actions
PDF

Keywords

quantum reduction
hard homogeneous space
discrete-logarithm problem
computational Diffie–Hellman problem

How to Cite

Galbraith, S., Panny, L., Smith, B., & Vercauteren, F. (2021). Quantum Equivalence of the DLP and CDHP for Group Actions. Mathematical Cryptology, 1(1), 40-44. Retrieved from https://journals.flvc.org/mathcryptology/article/view/122741

Abstract

In this short note we give a polynomial-time quantum reduction from the vectorization problem (DLP) to the parallelization problem (CDHP) for group actions. Combined with the trivial reduction from parallelization to vectorization, we thus prove the quantum equivalence of both 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 conclude with a discussion of the implications of this reduction for isogeny-based cryptosystems including CSIDH.

PDF
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.