|
|
On search complexity of discrete logarithm
Václavek, Jan ; Hubáček, Pavel (advisor) ; Koucký, Michal (referee)
In this thesis, we study the discrete logarithm problem in the context of TFNP - the complexity class of search problems with a syntactically guaranteed existence of a solution for all instances. Our main results show that suitable variants of the discrete logarithm problem, which we call Index and DLog, are complete for the classes PPP and PWPP, respectively. Additionally, our reductions provide new structural insights into PWPP by establishing two new PWPP-complete problems. First, the problem Dove, a relaxation of the PPP-complete problem Pigeon. Dove is the first PWPP-complete problem not defined in terms of an explicitly shrinking function. Second, the problem Claw, a total search problem capturing the computational complexity of breaking claw-free permuta- tions. In the context of TFNP, the PWPP-completeness of Claw matches the known intrinsic relationship between collision-resistant hash functions and claw-free permuta- tions established in the cryptographic literature. 1
|
guest ::
