TR06-096 Authors: Iftach Haitner, Omer Reingold

Publication: 10th August 2006 15:11

Downloads: 3695

Keywords:

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).