2021/05/04 by Iftach Haitner, Jonathan J. Hoch, Haitner, Iftach +5
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Internet Traffic Analysis and Secure E-voting #cs.CR
paper · pdf · doi:10.48550/arxiv.2105.01417
The full version was published in the SIAM Journal on Computing 2015. Extended abstracts of this work appeared in the Annual Symposium on Foundations of Computer Science (FOCS) 2007 and in the Theory of Cryptography Conference (TCC) 2013
arxiv created 2021/05/04 · arxiv updated 2021/05/05
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).