Towards Zero Knowledge Argument for Double Discrete Logarithm with Constant Cost

Abstract

It has been an open problem whether a constant round andconstant cost protocol exists for the Double Discrete Logarithm problem(DDLOG). In this paper, we show that such a protocol exists for bilineargroups under the restriction x = poly( λ ) where x and λ are the secretexponent and the security parameter, respectively. The protocol costsO (1) exponentiations and pairings on both the prover and verifier, andit exchanges 53 (67) group (field) elements, regardless of the desiredsoundness.