2021/05/04 by Iftach Haitner, Jonathan J. Hoch, Haitner, Iftach +5
Computer Science · #Cryptography and Data Security #Internet Traffic Analysis and Secure E-voting #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2105.01417
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).