Cryptography Reference
In-Depth Information
4.10.1. Basic Definitions
NP
The model of non-interactive proofs seems closer in spirit to the model of
-proofs
NP
than to general interactive proofs. In a sense, the
-proof model is extended by
allowing the prover and verifier to refer to a common random string, as well as toss
coins by themselves. Otherwise, as in the case of
NP
-proofs, the interaction is minimal
(i.e., unidirectional: from the prover to the verifier). Thus, in the definition that follows,
both the prover and verifier are ordinary probabilistic machines that, in addition to the
common input, also get a uniformly distributed (common)
reference string
. We stress
that, in addition to the common input and common reference string, both the prover
and verifier can toss coins and get auxiliary inputs. However, for the sake of simplicity,
we present a definition for the case in which none of these machines gets an auxiliary
input (yet they both can toss additional coins). The verifier also gets as input the output
produced by the prover.
Definition 4.10.1 (Non-Interactive Proof System):
A pair of probabilistic
machines
(
P
V
)
is called a
non-interactive proof system for a language
L
if V is polynomial-time and the following two conditions hold:
,
Completeness:
For every x
∈
L
,
2
3
Pr
[
V
(
x
,
R
,
P
(
x
,
R
))
=
1]
≥
poly(
|
x
|
)
.
where R is a random variable uniformly distributed in
{
0
,
1
}
Soundness:
For every x
∈
L and every algorithm B,
1
3
Pr
[
V
(
x
,
R
,
B
(
x
,
R
))
=
1]
≤
poly(
|
x
|
)
.
The uniformly chosen string R is called the
common reference string
.
where R is a random variable uniformly distributed in
{
0
,
1
}
1
As usual, the error probability in both conditions can be reduced (from
3
)downto
2
−
poly(
|
x
|
)
by repeating the process sufficiently many times (using a sequence of many
independently chosen reference strings). In stating the soundness condition, we have de-
viated from the standard formulation that allows
x
∈
L
to be adversarially selected after
R
is fixed; the latter “adaptive” formulation of soundness is used in Section 4.10.3.2,
and it is easy to transform a system satisfying the foregoing (“non-adaptive”) soundness
condition into one satisfying the adaptive soundness condition (see Section 4.10.3.2).
Every language in
NP
has a non-interactive proof system (in which no randomness is
NP
used). However, this
-proof system is unlikely to be zero-knowledge (see Definition
4.10.2).
The definition of zero-knowledge for the non-interactive model is simplified by the
fact that because the verifier cannot affect the prover's actions it suffices to consider the
simulatability of the view of a single verifier (i.e., the prescribed one). Actually, we can
avoid considering the verifier at all (since its view can be generated from the common
reference string and the message sent by the prover).
