On Constant-Round Precise Zero-Knowledge

Precise zero-knowledge, introduced by Micali and Pass [STOC’06], captures the idea that a view of any verifier can be

indifferently

reconstructed. Though there are some constructions of precise zero-knowledge, constant-round constructions are unknown to exist. This paper is towards constant-round constructions of precise zero-knowledge. The results of this paper are as follows.

We propose a relaxation of precise zero-knowledge that captures the idea that with a probability

arbitrarily polynomially

close to 1 a view of any verifier can be

indifferently

reconstructed, i.e., there exists a simulator (without having

q

(

n

),

p

(

n

,

t

) as input) such that for

any

polynomial

q

(

n

), there is a polynomial

p

(

n

,

t

) satisfying with probability at least

$1-\frac{1}{q(n)}$

, the view of any verifier in every interaction can be reconstructed in

p

(

n

,

T

) time by the simulator whenever the verifier’s running-time on this view is

T

. Then we show the impossibility of constructing constant-round protocols satisfying our relaxed definition with all the known techniques.

We present a constant-round precise zero-knowledge argument for any language in

NP

with respect to our definition, assuming the existence of collision-resistant hash function families (against all

n

O

(loglog

n

)

-size circuits).