Cryptography Reference
In-Depth Information
be implemented by a probabilistic polynomial-time machine that gets an
NP
-
witness as auxiliary input.
4.10.3. Extensions
We present the two extensions mentioned at the beginning of this section: First we
consider proof systems that preserve zero-knowledge when applied polynomially many
times (with the same common reference string), and later we consider proof systems that
preserve security when the assertions (i.e., common inputs) are adversarially selected
after the common reference string has been fixed.
4.10.3.1. Proving Many Assertions of Varying Lengths
The definitions presented in Section 4.10.1 are restricted in two ways. First, they con-
sider the proving of only one assertion relative to the common reference string, and
furthermore the common reference string is allowed to be longer than the assertion
(though polynomial in length of the assertion). A stronger definition, provided next, al-
lows the proving of poly(
n
) assertions, each of poly(
n
) length, using the same
n
-bit-long
common reference string.
We first note that it suffices to treat the case in which the number of assertions is
unbounded but the length of each assertion is a priori bounded. Specifically, for any
ε>
0, it suffices to consider the case where poly(
n
) assertions, each of length
n
ε
, need
to be proved relative to the same
n
-bit-long common reference string. The reason for
this is that we can reduce, in a “zero-knowledge manner,” any
NP
-assertion of length
-assertions, each of length
n
ε
: For example,
first we reduce the original (poly(
n
)-bit-long)
NP
poly(
n
) into a sequence of poly(
n
)
NP
-assertion to an assertion regarding
the 3-colorability of a poly(
n
)-vertex graph. Next, we use a commitment scheme with
commitments of length
n
ε
/
2 in order to commit to the coloring of each vertex. Finally,
for each edge, we (invoke the proof system to) prove that the corresponding two com-
mitments are to two different values in
{
1
,
2
,
3
}
. Note that each such assertion is of an
NP
type and refers to a pair of
n
ε
/
2-bit-long strings.
We now turn to the actual definitions. First we note that nothing needs to be changed
regarding the definition of non-interactive proof systems (Definition 4.10.1). We still
require the ability to be convinced by valid assertions, as well as “protection” from
false assertions. Alas, a minor technical difference is that whereas in Definition 4.10.1
we denoted by
n
the length of the assertion and considered a common reference string
of length poly(
n
), here we let
n
denote the length of the common reference string used
for assertions of length
n
ε
. We call
the
fundamental constant
of the proof system. In
contrast, the definition of zero-knowledge has to be extended to handle an (a priori)
unbounded sequence of proofs. (Recall that
U
n
denotes a random variable, uniformly
distributed over
ε
n
.)
{
0
,
1
}
Definition 4.10.11 (Non-Interactive Zero-Knowledge, Unbounded Version):
A non-interactive proof system
(
P
,
V
)
, with fundamental constant
ε
, for a
