Quantum Equivalence of the DLP and CDHP for Group Actions

Steven Galbraith (1) , Lorenz Panny (2) , Benjamin Smith (3) , Frederik Vercauteren (4)

1 Department of Mathematics [Auckland]
2 TU/e - Technische Universiteit Eindhoven
3 GRACE - Geometry, arithmetic, algorithms, codes and encryption
4 ESAT - Department of Electrical Engineering [Leuven]

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 par-allelization to vectorization, we thus prove the quantum equivalence of both problems.

Mots clés: computational Diffie-Hellman problem; discrete logarithm problem; Quantum reduction; group action; hard homogeneous space

Domaines: Cryptographie et sécurité [cs.CR]

Steven Galbraith, Lorenz Panny, Benjamin Smith, Frederik Vercauteren. Quantum Equivalence of the DLP and CDHP for Group Actions. Mathematical Cryptology, 2021, 1 (1), pp.40-44. ⟨hal-01963660v2⟩