Finding Collisions in Interactive Protocols - Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments
Finding Collisions in Interactive Protocols - Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments
复制标题
发现交互协议中的冲突 - 统计隐藏承诺的轮次和通信复杂性的严格下限
DOI：
10.1137/130938438
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
G. Segev
中科院分区：
文献类型：
--
作者：
Iftach Haitner;Jonathan J. Hoch;Omer Reingold;G. Segev
我们研究各种密码协议的轮数和通信复杂性。我们对单向排列和陷门排列的统计隐藏承诺方案的任何完全黑盒还原的轮次和通信复杂性给出了严格的下限。作为推论，我们为其他几种加密协议得出了类似的严格下限，例如单服务器私有信息检索、交互式散列和保证一方统计安全的不经意传输。我们的技术扩展了 Simon [密码学进展---EUROCRYPT'98，计算讲座笔记] 的碰撞发现预言。科学。 1403，施普林格，柏林，1998，第 334--345 页] 交互协议的设置以及 Gennaro 和 Trevisan 的重建范式 [第 41 届计算机科学基础年度研讨会 (FOCS) 论文集，IEEE Press，皮斯卡塔韦，新泽西州，2000 年，第 305--313 页]。
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 [Advances in Cryptology---EUROCRYPT'98, Lecture Notes in Comput. Sci. 1403, Springer, Berlin, 1998, pp. 334--345] to the setting of interactive protocols and the reconstruction paradigm of Gennaro and Trevisan [Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2000, pp. 305--313].