Interactive hashing, introduced by Naor et al. [NOVY98], plays
an important role in many cryptographic protocols. In particular, it
is a major component in all known constructions of
statistically-hiding commitment schemes and of zero-knowledge
arguments based on general one-way permutations and on one-way
functions. Interactive hashing with respect to a one-way
permutations f is a two-party protocol that enables a sender that
knows y=f(x) to transfer a random hash z=h(y) to a receiver. The
receiver is guaranteed that the sender is committed to y (in the
sense that it cannot come up with x and x' such that f(x)\neq
f(x') but h(f(x))=h(f(x'))=z). The sender is guaranteed that the
receiver does not learn any additional information on y. In
particular, when h is a two-to-one hash function, the receiver
does not learn which of the two preimages {y,y'}=f^{-1}(z) is
the one the sender can invert with respect to f.

This paper reexamines the notion of interactive hashing. We give an
alternative proof for the NOVY-protocol [NOVY98], which seems
to us significantly simpler and more intuitive than the original
one. Moreover, the new proof achieves much better parameters (in
terms of how security preserving the reduction is). Finally, our
proof implies a more versatile interactive hashing theorem for a
more general setting than that of [NOVY98]. One generalization
relates to the selection of hash function h (allowing much more
flexibility). More importantly, the theorem applies to the case
where the underlying function f is hard-to-invert only on some
given (possibly sparse) subset of the output strings. In other
words, the theorem is tuned towards hashing of a value y that may
be distributed over a sparse subset of the domain (rather than
uniform on the entire domain as a random output of a one-way
permutation is).

Our interest in interactive hashing is in part as a very appealing object (i.e., independent of any
particular application). Furthermore, a major motivation for looking into interactive hashing is
towards achieving a construction of statistical commitment schemes based on any one-way functions.
Given the history of the problem, it seems that extending our understanding of interactive hashing
is a natural approach towards relaxing the general assumptions needed for constructing statistical
commitments. Indeed, our new theorem is already useful in easily and more directly implying
constructions of statistical commitments based on the same assumptions as in [HaitnerEtAl05].
In a subsequent work, we also show how to use the new theorem for constructions based
on substantially weaker assumptions. That construction goes beyond the natural barrier of relying
on ``almost regular" one-way functions (and in particular imply a construction based on any
exponentially-hard one-way function).