Statistically Hiding Commitment from Any One-Way Function

Iftach Haitner

A commitment scheme defines a two-stage interactive protocol between a sender and a receiver; informally, after the commit stage, the sender is bound to (at most) one value, which is not yet revealed to the receiver, and in the reveal stage the receiver finally learns this value. In a statistically-hiding computationally-binding commitment scheme (for short, statistical commitment) even an all-powerful receiver does not learn the value to which the sender commits before the reveal stage, while a polynomial-bounded sender is bound to at most one value after the commit stage.

Statistical commitment is a fundamental primitive in cryptography, it can be used as a building block in constructions of statistical zero-knowledge arguments and certain coin-tossing protocols. In particular, it implies, via standard reduction, a way to transform protocols that are secure assuming an all powerful honest-but-curious party, into one that is secure even when this party maliciously deviates from the protocol.

We give the first construction of statistically-hiding commitment schemes based on the minimal cryptographic assumption that one-way functions exist (previous constructions assume some structure on the functions, e.g. regularity). Our construction employs two-phase commitment schemes, recently constructed by Nguyen, Ong and Vadhan (FOCS '06), and universal one-way hash functions introduced and constructed by Naor and Yung (STOC '89) and Rompel (STOC '90).

Joint work with Omer Reingold

10 Sept (Monday) at 1630 hrs

Gates 4B (opposite 490)