Cryptography Reference
In-Depth Information
The rationale for having the sender check to see if the index
i
indeed be
lo
ngs
to the legitimate index set
I
is that only permutation pairs (
f
i
,
f
i
) with
i
∈
I
are
guaranteed to have identical range distri
bu
tions. Thus, it actually is not necessary for
the sender to check whether or not
i
∈
I
; it suffices for it to check (or be otherwise
convinced) that the permutation pair (
f
i
,
f
i
) satisfies the requirement of identical range
distributions. Consider, for example, the factoring claw-free collection (presented in
Section 2.4.5). This collection
is not known
to have an efficiently recognizable index set.
Still, having sent an index
N
, the receiver can prove in zero-knowledge to the sender that
the permutation pair (
f
N
,
f
N
) satisfies the requirement of identical range distributions.
What is actually being proved is that half of the square roots of each quadratic residue
mod
N
have Jacobi symbol 1 (relative to
N
). A (perfect) zero-knowledge proof system
for this claim does exist (without assuming anything). In fact, it suffices to use a witness-
independent proof system, and such a system having a constant number of rounds does
exist (again, without assuming anything). Hence, the factoring claw-free collection can
be used to construct a constant-round perfectly hiding commitment scheme, and thus
such commitment schemes also exist under the assumption that the factoring of Blum
integers is intractable.
4.8.2.4. Non-Uniform Computational Unambiguity
Actually, for the applications to proof/argument systems, both the one following and
the one in Section 4.9.1, we need commitment schemes with perfect secrecy and
non-
uniform
computational unambiguity. (The reason for this need is analogous to one
discussed in the case of the zero-knowledge proof for
presented in Section 4.4.)
By non-uniform computational unambiguity we mean that the unambiguity condition
should also hold for (non-uniform) families of polynomial-size circuits. We stress that
the foregoing constructions of perfect commitment schemes possess the non-uniform
computational unambiguity, provided that the underlying intractability assumption also
holds with respect to non-uniform polynomial-size circuits (e.g., the one-way permu-
tation is hard to invert even by such circuits, and the claw-free collections also foil
non-uniform polynomial-size claw-forming circuits).
In order to prevent the terminology from becoming too cumbersome, we omit the
attribute “non-uniform” when referring to the perfectly hiding commitment schemes
in the description of the two applications mentioned earlier.
NP
4.8.2.5. Commitment Schemes with A Posteriori Secrecy
We conclude the discussion of perfectly hiding commitment schemes by introducing
a relaxation of the secrecy requirement. The resulting scheme cannot be used for the
purposes of the current section, yet it is useful in different settings discussed later.
The advantage of the relaxation is that it allows us to construct such (constant-round
perfectly hiding) commitment schemes using any claw-free collection, thus waiving
the additional requirement that the index set be efficiently recognizable.
Loosely speaking, we relax the secrecy requirement of perfectly hiding commitment
schemes by requiring that it hold only when the receiver follows its prescribed program
