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