Cryptography Reference
In-Depth Information
(or an argument)
for a language
L if both machines are polynomial-time
(with
auxiliary inputs)
and the following two conditions hold:
Completeness:
For every x
∈
L, there exists a string y such that for every string z,
2
3
Pr
,
=
≥
[
P
(
y
)
V
(
z
)
(
x
)
1]
Computational soundness:
For every polynomial-time interactive machine B, and
for all sufficiently long x
∈
L and every y and z,
1
3
Pr
[
B
(
y
)
,
V
(
z
)
(
x
)
=
1]
≤
As usual, the error probability (in both the completeness and soundness conditions)
can be reduced (from
3
) down to as much as 2
−
poly(
|
x
|
)
by sequentially repeating the
protocol sufficiently many times; see Exercise 31. We mention that
parallel
repetitions
may fail to reduce the (computational) soundness error in some cases.
1
4.8.2. Perfectly Hiding Commitment Schemes
The thrust of the current section is toward a method for constructing
perfect
zero-
knowledge
arguments
for every language in
. This method makes essential use of
the concept of a commitment scheme with a
perfect
(or “information-theoretic”) secrecy
property. Hence, we start with an exposition of such perfectly hiding commitment
schemes. We remark that such schemes may also be useful in other settings (e.g., other
settings in which the receiver of the commitment is computationally unbounded; see,
for example, Section 4.9.1).
The difference between commitment schemes (as defined in Section 4.4.1) and
perfectly hiding commitment schemes (defined later) consists in a switch in the
scope of the secrecy and unambiguity requirements: In commitment schemes (see
Definition 4.4.1), the secrecy requirement is computational (i.e., refers only to prob-
abilistic polynomial-time adversaries), whereas the unambiguity requirement is
information-theoretic (and makes no reference to the computational power of the
adversary). On the other hand, in perfectly hiding commitment schemes (as defined
later), the secrecy requirement is information-theoretic, whereas the unambiguity
requirement is computational (i.e., refers only to probabilistic polynomial-time
adversaries).
NP
Comments about Terminology.
From this point on, we explicitly mention the “per-
fect” feature of a commitment scheme to which we refer. That is, a commitment scheme
as in Definition 4.4.1 will be referred to as
perfectly binding
, whereas a commitment
scheme as in Definition 4.8.2 (presented later) will be referred to as
perfectly hiding
.
Consequently, when we talk of a commitment scheme without specifying any “perfect”
feature, it may be that the scheme is only computationally hiding and computationally
binding. We remark that it is impossible to have a commitment scheme that is both
perfectly hiding and perfectly binding (see Exercise 32).
