Cryptography Reference
In-Depth Information
property. Hence, we confine ourselves to describing the ideas involved in construct-
ing such arguments and do not address the issue of making them zero-knowledge.
(We stress that the argument system presented next is
not
zero-knowledge, unless
NP
⊆
BPP
.)
By the so-called PCP theorem, every
language
L
can be reduced to 3
SAT
,
so that non-members of
L
are mapped into 3CNF formulae for which every truth
assignment satisfies at most a 1
NP
−
ε
fraction of the clauses, where
ε>
0 is a universal
constant. Let us denote this reduction by
L
,it
suffices to prove that the formula
f
(
x
) is satisfiable. This can be done by supplying a
satisfying assignment for
f
(
x
). The interesting point is that the verifier need not check
that all clauses of
f
(
x
) are satisfied by the given assignment. Instead, it can uniformly
select only poly-logarithmically many clauses and check that the assignment satisfies
all of them. If
x
∈
L
(and the prover supplies a satisfying assignment to
f
(
x
)), then
the verifier will always accept. But if
x
∈
L
, then no assignment will satisfy more than
a1
f
. Now, in order to prove that
x
∈
fraction of the clauses, and consequently a uniformly chosen clause will not
be satisfied with probability at least
−
ε
ε
. Hence, checking super-logarithmically many
clauses will do.
The preceding paragraph shows that the randomness complexity can be made poly-
logarithmic and that the verifier need only inspect a poly-logarithmic number of ran-
domly selected values. Specifically, the prover commits to each of the values of the
variables in the formula
f
(
x
) but is asked to reveal only a few of them. To obtain (total)
poly-logarithmic communication complexity, we use a special commitment scheme
that allows us to commit to a string of length
n
such that the commitment phase takes
poly-logarithmic communication and individual bits of this string can be revealed (and
verified as correct) at poly-logarithmic communication cost. For constructing such
a commitment scheme, we use a
collision-free
hashing function. The function maps
strings of some length to strings of half that length, so that it is “hard” to find two
strings that are mapped by the function to the same image. (The following descrip-
tion is slightly inaccurate. What we need is a family of hashing functions such that no
small non-uniform circuit, given the description of a function in the family, can form
collisions with respect to it.)
Let
n
denote the length of the input string to which the sender wishes to commit
itself, and let
k
be a parameter (which is later set to be poly-logarithmic in
n
). Denote by
H
a collision-free hashing function mapping strings of length 2
k
into strings of length
k
. The sender partitions its input string into
m
def
=
n
k
consecutive blocks, each of length
k
. Next, the sender constructs a binary tree of depth log
2
m
, placing the
m
blocks in the
corresponding leaves of the tree. In each internal node, the sender places the hashing
value obtained by applying the function
H
to the content of the children of this node.
The only message sent in the commit phase is the content of the root (sent by the sender
to the receiver). By doing so,
unless the sender can form collisions under H
, the sender
has “committed” itself to some
n
-bit-long string. When the receiver wishes to get the
value of a specific bit in the string, the sender reveals to the receiver the contents of
both children
of each node along the path from the root to the corresponding leaf. The
receiver checks that the values supplied for each node (along the path) match the value
obtained by applying
H
to the values supplied for its two children.
