Finding Collisions in Interactive Protocols -- Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments
This work addresses foundational challenges in cryptography by providing rigorous complexity bounds, which is crucial for protocol designers and security analysts, though it is incremental in building on prior techniques.
The paper tackles the problem of establishing tight lower bounds on round and communication complexities for statistically hiding commitment schemes derived from one-way or trapdoor permutations, achieving results that extend to protocols like private information retrieval and oblivious transfer with statistical security.
We study the round and communication complexities of various cryptographic protocols. We give tight lower bounds on the round and communication complexities of any fully black-box reduction of a statistically hiding commitment scheme from one-way permutations, and from trapdoor permutations. 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 and the reconstruction paradigm of Gennaro and Trevisan (FOCS '00).