Cryptography Reference
In-Depth Information
Definition 4.10.2 (Non-Interactive Zero-Knowledge):
A non-interactive proof
system
(
P
,
V
)
for a language L is
zero-knowledge
if there exists a polynomial
p and a probabilistic polynomial-time algorithm M such that the ensembles
{
}
x
∈
L
are computationally indistinguish-
able, where U
m
is a random variable uniformly distributed over
(
x
,
U
p
(
|
x
|
)
,
P
(
x
,
U
p
(
|
x
|
)
))
}
x
∈
L
and
{
M
(
x
)
{
0
,
1
}
m
.
This definition, too, is “non-adaptive” (i.e., the common input cannot depend on the
common reference string). An adaptive formulation of zero-knowledge is presented
and discussed in Section 4.10.3.2.
Non-Interactive Zero-Knowledge versus Constant-Round Zero-Knowledge.
We
stress that the non-interactive zero-knowledge model postulates the existence of a uni-
formly selected reference string available to both prover and verifier. A natural sugges-
tion is to replace this postulate with a two-party protocol for generating a uniformly
distributed string of specified length. Such a protocol should be resilient to adversarial
behavior by each of the two parties: The output should be uniformly distributed even if
one of the parties deviates from the protocol (using any probabilistic polynomial-time
strategy). Furthermore, it seems that such a protocol should have a strong simulatabil-
ity feature, allowing the generation of a random-execution transcript for every given
outcome. Specifically, in order to obtain a constant-round zero-knowledge proof sys-
tem from a non-interactive zero-knowledge proof, one seems to need a constant-round
(strongly simulatable) protocol for generating uniformly distributed strings. Such a
protocol can be constructed using perfectly hiding commitment schemes. In combi-
nation with the results that follow, one can derive an alternative construction of a
round-efficient zero-knowledge proof for
NP
.
4.10.2. Constructions
A fictitious abstraction that nevertheless is very helpful for the design of non-
interactive zero-knowledge proof systems is the
hidden-bits model
. In this model
the common reference string is uniformly selected as before, but only the prover
can see all of it. The “proof” that the prover sends to the verifier consists of two
parts; a “certificate” and the specification of some bit positions in the common
reference string. The verifier can inspect only the bits of the common reference
string residing in the locations that have been specified by the prover. Certainly,
in addition, the verifier inspects the common input and the “certificate.”
Definition 4.10.3 (Proof Systems in the Hidden-Bits Model):
A pair of prob-
abilistic machines
(
P
,
V
)
is called a
hidden-bits proof system for
LifVis
polynomial-time and the following two conditions hold:
Completeness:
For every x
∈
L,
2
3
Pr
[
V
(
x
,
R
I
,
I
,π
)
=
1]
≥
