arXiv:2105.01417 · SIAM Journal on Computing

Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments

Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev

Published Jan 1, 2015• 34 citations

Abstract

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

DOI: 10.1137/130938438

Related papers

Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

Iftach Haitner, Jonathan J. Hoch, Omer Reingold +1 more

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from oneway permutations, and even front trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme due to Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). As a corollary, we derive similar tight lower bounds for several other ctyptographicprotocols, 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 (our extension also implies an alternative proof for the main property of the original oracle). In addition, we substantially extend the reconstruction paradigm of Gennaro and Trevisan (FOCS '00). In both cases, our extensions are quite delicate and may be found useful in proving additional black-box separation results.

Annual Symposium on Foundations of Computer ScienceOct 1, 200796 citations

Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

Iftach Haitner, Jonathan J. Hoch, Omer Reingold +1 more

Annual Symposium on Foundations of Computer ScienceOct 1, 20073 citations

Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments.

Iftach Haitner, Jonathan J. Hoch, Omer Reingold +1 more

Abstract We study the round complexity of various cryptographic protocols. Our main result is a tightlower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. Thislower bound matches the round complexity of the statistically-hiding commitment scheme due to Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). As a corollary, we derive similar tightlower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for oneof the parties.

Jan 1, 20070 citations

A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval.

Iftach Haitner, Jonathan J. Hoch, Gil Segev

We study the communication complexity of single-server Private Information Retrieval (PIR) protocolsthat are based on fundamental cryptographic primitives in a black-box manner. In this setting, we establish a tight lower bound on the number of bits communicated by the server in any polynomially-preservingconstruction that relies on trapdoor permutations. More specifically, our main result states that in such constructions \\Omega (n) bits must be communicated by the server, where n is the size of the server's database,and this improves the \\Omega (n / log n) lower bound due to Haitner, Hoch, Reingold and Segev (FOCS '07).Therefore, in the setting under consideration, the naive solution in which the user downloads the entire database turns out to be optimal up to constant multiplicative factors. We note that the lower boundwe establish holds for the most generic form of trapdoor permutations, including in particular enhanced trapdoor permutations.Technically speaking, this paper consists of two main contributions from which our lower bound is obtained. First, we derive a tight lower bound on the number of bits communicated by the sender duringthe commit stage of any black-box construction of a statistically-hiding bit-commitment scheme from a family of trapdoor permutations. This lower bound asymptotically matches the upper bound provided bythe scheme of Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). Second, we improve the e fficiencyof the reduction of statistically-hiding commitment schemes to low-communication single-server PIR, due to Beimel, Ishai, Kushilevitz and Malkin (STOC '99). In particular, we present a reduction that essentiallypreserves the communication complexity of the underlying single-server PIR protocol.

Jan 1, 20070 citations

Black-Box Constructions of Protocols for Secure Computation.

Iftach Haitner, Yuval Ishai, Eyal Kushilevitz Z +2 more

In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor permutation) in a black-box way only. Until now, all known general constructions for this setting were inherently non-blackbox since they required the parties to prove zero-knowledge statements that are related to the computation of the underlying primitive. Our main technical result is a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semi-honest parties. As a corollary, we obtain the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which only make a black-box use of semi-honest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption. In order to construct this reduction we introduce a new notion of security called privacy in the presence of defensible adversaries. This notion states that if an adversary can produce (retroactively, after the protocol terminates) an input and random tape that make

Jan 1, 20102 citations

Constructing Non-malleable Commitments: A Black-Box Approach

Vipul Goyal, Chen-Kuei Lee, Rafail Ostrovsky +1 more

We propose the first black-box construction of non-malleable commitments according to the standard notion of non-malleability with respect to commitment. Our construction additionally only requires a constant number of rounds and is based only on (black-box use of) one-way functions. Prior to our work, no black-box construction of non-malleable commitments was known (except for relaxed notions of security) in any (polynomial) number of rounds based on any cryptographic assumption. This closes the wide gap existent between black-box and non-black-box constructions for the problem of non-malleable commitments. Our construction relies on (and can be seen as a generalization of) the recent non-malleable commitment scheme of Goyal (STOC 2011). We also show how to get black-box constructions for a host of other cryptographic primitives. We extend our construction to get constant-round concurrent non-malleable commitments, constant-round multi-party coin tossing, and non-malleable statistically hiding commitments (satisfying the notion of non-malleability with respect to opening). All of the mentioned results make only a black-box use of one-way functions. Our primary technical contribution is a novel way of implementing the proof of consistency typically required in the constructions of non-malleable commitments (and other related primitives). We do this by relying on ideas from the ``zero-knowledge from secure multi-party computation" paradigm of Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2007). We extend in a novel way this ``computation in the head" paradigm (which can be though of as bringing powerful error-correcting codes into purely computational setting). To construct a non-malleable commitment scheme, we apply our computation in the head techniques to the recent (constant-round) construction of Goyal. Along the way, we also present a simplification of the construction of Goyal where a part of the protocol is implemented in an information theoretic manner. Such a simplification is crucial for getting a black-box construction. This is done by making use of pair wise-independent hash functions and strong randomness extractors. We show that our techniques have multiple applications, as elaborated in the paper. Hence, we believe our techniques might be useful in other settings in future.

Annual Symposium on Foundations of Computer ScienceOct 1, 201287 citations