Cryptography Reference
In-Depth Information
Theorem 4.7.15:
Assuming the existence of (non-uniformly) one-way functions,
every
NP
-relation has a zero-knowledge system for
strong
proofs of knowledge.
4.8.
∗
Computationally Sound Proofs (Arguments)
In this section we consider a relaxation of the notion of an interactive proof system.
Specifically, we relax the soundness condition of interactive proof systems. Instead of
requiring that it be
impossible
to fool the verifier into accepting false statements (with
probability greater than some bound), we require only that it be
infeasible
to do so. We
call such protocols
computationally sound proof systems
(or
arguments
). The advantage
of computationally sound proof systems is that
perfect
zero-knowledge
computation-
ally sound
proof systems can be constructed, under some reasonable complexity-
assumptions, for all languages in
NP
. Recall that
perfect
zero-knowledge proof sys-
tems are unlikely to exist for all languages in
NP
(see Section 4.5). Also recall
that
computational
zero-knowledge proof systems do exist for all languages in
NP
,
provided that one-way functions exist. Hence, the previously quoted positive results
exhibit some kind of a trade-off between the soundness and zero-knowledge proper-
ties of the zero-knowledge protocols of
. (We remark, however, that the perfect
zero-knowledge computationally sound proofs for
NP
are constructed under stronger
complexity-theoretic assumptions than are the ones used for the computational zero-
knowledge proofs. It is indeed an interesting research project to try to construct perfect
zero-knowledge computationally sound proofs for
NP
under weaker assumptions, in
particular, assuming only the existence of one-way functions.)
We mention that it seems that computationally sound proof systems can be much
more efficient than ordinary proof systems. Specifically, under some plausible com-
plexity assumptions, extremely efficient computationally sound proof systems (i.e.,
requiring only poly-logarithmic communication and randomness) exist for any lan-
guage in
NP
NP
NP
. An analogous result cannot hold for ordinary proof systems unless
NP
⊆
Dtime(2
polylog
)).
is contained in deterministic quasi-polynomial time (i.e.,
4.8.1. Definition
The definition of computationally sound proof systems follows naturally from the
foregoing discussion. The only issue to consider is that
merely
replacing the soundness
condition of Definition 4.2.4 with a
computational-soundness
condition leads to an
unnatural definition, since the computational power of the prover in the completeness
condition (in Definition 4.2.4) is not restricted. Hence, it is natural to restrict the prover
in
both
(the completeness and soundness) conditions to be an efficient one. It is crucial
to interpret “efficient” as being probabilistic polynomial-time
given auxiliary input
(otherwise, only languages in
will have such proof systems). Hence, our starting
point is Definition 4.2.10 (rather than Definition 4.2.4).
BPP
Definition 4.8.1 (Computationally Sound Proof System (Arguments)):
A pair
of interactive machines
(
P
,
V
)
is called a
computationally sound proof system
