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

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 with unique encoding 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.

https://hal.sorbonne-universite.fr/hal-02350271
Contributor : Antoine Joux <>
Submitted on : Wednesday, November 6, 2019 - 5:06:06 AM
Last modification on : Friday, March 27, 2020 - 3:02:28 AM

Identifiers

• HAL Id : hal-02350271, version 1
• ARXIV : 1911.01662

Citation

Gabor Ivanyos, Antoine Joux, Miklos Santha. Discrete logarithm and Diffie-Hellman problems in identity black-box groups. 2019. ⟨hal-02350271⟩

Record views