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.
In this paper we give an alternative proof for the [NOVY98] interactive hashing protocol, 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].
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. Indeed, we use our new theorem to construct statistical commitment schemes based on substantially weaker assumptions than the current constructions. 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).
Joint work with Omer Reingold
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.