Chicago Journal of Theoretical Computer Science

Volume 2023

Article 1

Published by the Department of Computer Science, The University of Chicago.

Discrete logarithm and Diffie-Hellman problems in identity black-box groups

Gábor Iványos
Institute for Computer Science and Control
Eötvös Loránd Research Network
Budapest, Hungary
Gabor DOT Ivanyos AT sztaki DOT hu

Antoine Joux
CISPA Helmhotz Center for Information Security
Saarbrücken, Germany
antoine DOT joux AT mdx DOT org


Miklos Santha
Centre for Quantum Technologies and MajuLab
National University of Singapore
miklos DOT santha AT gmail DOT com

June 15, 2023


We investigate the computational complexity of the discrete logarithm, the computational Diffie-Hellman and the decisional Diffie-Hellman problems in some identity black-box groups $G_{p,t}$, where $p$ is a prime number and $t$ is a positive integer. These are defined as quotient groups of vector space $Z_p^{t+1}$ by a hyperplane $H$ given through an identity oracle. While in general black-box groups that have unique encoding of their elements these computational problems are classically all hard and quantumly all easy, we find that in the groups $G_{p,t}$ the situation is more contrasted. We prove that while there is a polynomial time probabilistic algorithm to solve the decisional Diffie-Hellman problem in $G_{p,1}$, the probabilistic query complexity of all the other problems is $\Omega(p)$, and their quantum query complexity is $\Omega(\sqrt{p})$. Our results therefore provide a new example of a group where the computational and the decisional Diffie-Hellman problems have widely different complexity.

Submitted May 19 2021, revised January 5, 2023, published June 15, 2023.

DOI: 10.4086/cjtcs.2023.001

[] Volume 2022, Article 2 [] Article 2
[back] Volume 2023 [back] Published articles
[CJCTS home]