[Resource Topic] 2018/1199: Quantum Equivalence of the DLP and CDHP for Group Actions

Welcome to the resource topic for 2018/1199

Quantum Equivalence of the DLP and CDHP for Group Actions

Authors: Steven Galbraith, Lorenz Panny, Benjamin Smith, Frederik Vercauteren


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.

ePrint: https://eprint.iacr.org/2018/1199

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .