Cryptology ePrint Archive: Report 2018/1199

Quantum Equivalence of the DLP and CDHP for Group Actions

Steven Galbraith and Lorenz Panny and 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.

Category / Keywords: foundations / quantum reduction, group action, discrete-logarithm problem, DLP, computational Diffie-Hellman problem, CDH

Original Publication (in the same form): to appear in Mathematical Cryptology

Date: received 12 Dec 2018, last revised 9 Jun 2021

Contact author: l s panny at tue nl

Available format(s): PDF | BibTeX Citation

Version: 20210610:023012 (All versions of this report)

Short URL: ia.cr/2018/1199


[ Cryptology ePrint archive ]