International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

Authors:
Iftach Haitner
Jonathan J. Hoch
Omer Reingold
Gil Segev
Download:
URL: http://eprint.iacr.org/2007/145
Search ePrint
Search Google
Abstract: We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme due to Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). As a corollary, we derive similar tight lower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon (EUROCRYPT '98) to the setting of interactive protocols (our extension also implies an alternative proof for the main property of the original oracle). In addition, we substantially extend the reconstruction paradigm of Gennaro and Trevisan (FOCS '00). In both cases, our extensions are quite delicate and may be found useful in proving additional black-box separation results.
BibTeX
@misc{eprint-2007-13427,
  title={Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments},
  booktitle={IACR Eprint archive},
  keywords={foundations / Black-box reductions, Lower bounds},
  url={http://eprint.iacr.org/2007/145},
  note={FOCS '07. This is the full version. gil.segev@weizmann.ac.il 13725 received 23 Apr 2007, last revised 30 Jul 2007},
  author={Iftach Haitner and Jonathan J. Hoch and Omer Reingold and Gil Segev},
  year=2007
}