Public-Coin Concurrent Zero-Knowledge in the Global Hash Model

Public-coin zero-knowledge

and

concurrent zero-knowledge (

cZK

)

are two classes of zero knowledge protocols that guarantee some additional desirable properties. Still, to this date no protocol is known that is both public-coin and

cZK

for a language outside BPP. Furthermore, it is known that no such protocol can be black-box

ZK

[Pass et.al, Crypto 09].

We present a public-coin concurrent

ZK

protocol for any NP language. The protocol assumes that all verifiers have access to a globally specified function, drawn from a collision resistant hash function family. (This model, which we call the Global Hash Function, or GHF model, can be seen as a restricted case of the non-programmable reference string model.) We also show that the impossibility of black-box public-coin

cZK

extends also to the GHF model.

Our protocol assumes CRH functions against quasi-polynomial adversaries and takes

O

(log

1 + 

ε

n

) rounds for any

ε

 > 0, where

n

is the security parameter. Our techniques combine those for (non-public-coin) black-box

cZK

with Barak’s non-black-box technique for public-coin constant-round

ZK

. As a corollary we obtain the first simultaneously resettable zero-knowledge protocol with

O

(log

1 + 

ε

n

) rounds, in the GHF model.