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

Abstract

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.

• The article: PDF (247 KB)
• Source material: ZIP (88 KB)
• BibTeX entry for this article (258 bytes)

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

© 2023 Gábor Iványos, Antoine Joux and Miklos Santha
Licensed under a Creative Commons Attribution License

Volume 2022, Article 2

Article 2

Volume 2023

Published articles