The Curious Case of
Non-Interactive Commitments
Mohammad
Mahmoody (
Abstract:
It is well-known that one-way permutations (and even one-to-one one-way
functions) imply the existence of non-interactive commitments. Furthermore
the construction is black-box
(i.e., the underlying one-way function is used as an oracle to implement the
commitment scheme, and an adversary attacking the commitment scheme is used
as an oracle in the proof of security).
We rule out the possibility of black-box constructions of non-interactive
commitments from general (possibly not one-to-one) one-way functions. As far
as we know, this is the first result showing a natural cryptographic task
that can be achieved in a black-box way from one-way permutations but not
from one-way functions.
We next extend our black-box separation to constructions of non-interactive
commitments from a stronger notion of one-way functions, which we refer to as
hitting one-way functions. Perhaps
surprisingly, Barak, Ong, and Vadhan
(Siam JoC '07) showed that there does exist a non-black-box construction of non-interactive commitments
from hitting one-way functions. As far as we know, this is the first result
to establish a “separation” between the power of black-box and
non-black-box use of a primitive to implement a natural cryptographic task.
We finally show that unless the complexity class $\NP$ has program checkers,
the above separations extend also to non-interactive instance-based
commitments, and 3-message public-coin honest-verifier zero-knowledge
protocols with O(log n)-bit verifier messages. The
well-known classical zero-knowledge proof for NP fall
into this category.