#

### 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`

and

Miklos Santha

Centre for Quantum Technologies and MajuLab

National University of Singapore

Singapore

`miklos DOT santha AT gmail DOT com`

*June 15, 2023*
#### 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.

Volume 2022, Article 2
Article 2

Volume 2023
Published articles