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