Arrow Research search

Author name cluster

Iftach Haitner

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

14 papers
2 author rows

Possible papers

14

STOC Conference 2022 Conference Paper

On the complexity of two-party differential privacy

  • Iftach Haitner
  • Noam Mazor
  • Jad Silbak
  • Eliad Tsfadia

In distributed differential privacy, the parties perform analysis over their joint data while preserving the privacy for both datasets. Interestingly, for a few fundamental two-party functions such as inner product and Hamming distance, the accuracy of the distributed solution lags way behind what is achievable in the client-server setting. McGregor, Mironov, Pitassi, Reingold, Talwar, and Vadhan [FOCS ’10] proved that this gap is inherent, showing upper bounds on the accuracy of (any) distributed solution for these functions. These limitations can be bypassed when settling for computational differential privacy, where the data is differentially private only in the eyes of a computationally bounded observer, using oblivious transfer. We prove that the use of public-key cryptography is necessary for bypassing the limitation of McGregor et al., showing that a non-trivial solution for the inner product, or the Hamming distance, implies the existence of a key-agreement protocol. Our bound implies a combinatorial proof for the fact that non-Boolean inner product of independent (strong) Santha-Vazirani sources is a good condenser. We obtain our main result by showing that the inner-product of a (single, strong) SV source with a uniformly random seed is a good condenser, even when the seed and source are dependent.

Details

FOCS Conference 2020 Conference Paper

A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip

  • Iftach Haitner
  • Yonatan Karidi-Heller

In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems '83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS '85], the parties communicate over a broadcast channel and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the n-party majority protocol is resilient to O(√n) corruptions (ignoring poly-logarithmic factors), and conjectured this is a tight upper bound for any n-party protocol (of any round complexity). Their conjecture was proved to be correct for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein, Linial, and Saks [Combinatorica '89], symmetric protocols Goldwasser, Tauman Kalai, and Park [ICALP '15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai, Komargodski, and Raz [DISC '18]. Yet, the question for many-turn protocols was left completely open. In this work we close the above gap, proving that no n-party protocol (of any round complexity) is resilient to ω(√n) (adaptive) corruptions.

Details

FOCS Conference 2018 Conference Paper

Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols

  • Iftach Haitner
  • Kobbi Nissim
  • Eran Omri
  • Ronen Shaltiel
  • Jad Silbak

Let π be an efficient two-party protocol that given security parameter k, both parties output single bits X k and Y k, respectively. We are interested in how (X k, Y k ) "appears" to an efficient adversary that only views the transcript T k. We make the following contributions: · We develop new tools to argue about this loose notion, and show (modulo some caveats) that for every such protocol π, there exists an efficient simulator such that the following holds: on input T k, the simulator outputs a pair (X' k, Y' k ) such that (X' k, Y' k, T k ) is (somewhat) computationally indistinguishable from (X k, Y k, T k ). · We use these tools to prove the following dichotomy theorem: every such protocol π is: - either uncorrelated - it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce T k, but then choose their outputs independently from some product distribution (that is determined in poly-time from T k ), - or, the protocol implies a key-agreement protocol (for infinitely many k's). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. ·We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. · A subsequent work of Haitner et al. uses the above dichotomy to makes progress on a long-standing open question regarding the complexity of fair two-party coin-flipping protocols. We highlight the following ideas regarding our technique: · The simulator algorithm is obtained by a carefully designed "competition" between efficient algorithms attempting to forecast ((X k, Y k )|T k = t). The winner is used to simulate the outputs of the protocol. · Our key-agreement protocol uses the simulation to reduce to an information theoretic setup, and is in some sense non-black box.

Details

FOCS Conference 2018 Conference Paper

Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling

  • Amos Beimel
  • Iftach Haitner
  • Nikolaos Makriyannis
  • Eran Omri

In his seminal work, Cleve [STOC '86] proved that the bias of any coin-flipping protocol is inversely proportional to the number of rounds. This lower bound was met for the two-party case by Moran et al. [Journal of Cryptology '16], and the three-party case (up to a polylogarithmic factor) by Haitner and Tsfadia [SICOMP '17], and was approached for multi-party protocols by Haitner et al. [SODA '17] when the number of rounds is at least doubly exponential in the number of parties. For the complement case, however, the best bias for multi-party coin-flipping protocols is proportional to the number of parties and inversely proportional to the square root of the number of rounds. The latter bias is achieved by the majority protocol of Awerbuch et al. [Manuscript '85]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, if the number of rounds is bounded by some polynomial in the number of parties, then the bias is lower-bounded by a quantity that is inversely proportional to the square root of the number of rounds (up to a polylogarithmic factor). As far as we know, this is the first improvement of Cleve's bound, and is far from the aforementioned upper bound of Awerbuch et al. only by a factor of the number of parties. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of ("augmented") weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [Manuscript '93], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of Cleve and Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.

Details

SODA Conference 2017 Conference Paper

Fair Coin Flipping: Tighter Analysis and the Many-Party Case

  • Niv Buchbinder
  • Iftach Haitner
  • Nissan Levi
  • Eliad Tsfadia

In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. In this work we focus on the case of dishonest majority, ie at least half of the parties can be corrupted. [19] [STOC 1986] has shown that in any m -round coin-flipping protocol the corrupted parties can bias the honest parties’ common output bit by Θ(1/m). For more than two decades the best known coin-flipping protocols against majority was the protocol of [9] [Manuscript 1985], who presented a t -party, m -round protocol with bias This was changed by the breakthrough result of [42] [TCC 2009], who constructed an m -round, two-party coin-flipping protocol with optimal bias Θ(1/m). Recently, [32] [STOC 14] constructed an m -round, three -party coin-flipping protocol with bias O (log 3 m/m). Still for the case of more than three parties, against arbitrary number of corruptions, the best known protocol remained the protocol of [9]. We make a step towards eliminating the above gap, presenting a t -party, m -round coin-flipping protocol, with bias This improves upon the protocol of [9] for any t ≤ 1/2 · log log m, and in particular for t ∊ O (1), this yields an protocol. For the three-party case, this yields an protocol, improving over the the O (log 3 m/m)-bias protocol of [32]. Our protocol generalizes that of [32], by presenting an appropriate “defense protocols” for the remaining parties to interact in, in the case that some parties abort or caught cheating ([32] only presented a two-party defense protocol, which limits their final protocol to handle three parties). We analyze our new protocols by presenting a new paradigm for analyzing fairness of coin-flipping protocols. We map the set of adversarial strategies that try to bias the honest parties outcome in the protocol to the set of the feasible solutions of a linear program. The gain each strategy achieves is the value of the corresponding solution. We then bound the the optimal value of the linear program by constructing a feasible solution to its dual.

Details

FOCS Conference 2011 Conference Paper

Coin Flipping with Constant Bias Implies One-Way Functions

  • Iftach Haitner
  • Eran Omri

It is well known (cf. , Impagliazzo and Luby [FOCS '89]) that the existence of almost all "interesting" cryptographic applications, i. e. , ones that cannot hold information theoretically, implies one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much. Impagliazzo and Luby proved that coin-flipping protocols that are safe against negligible bias do imply one-way functions, and, very recently, Maji, Prabhakaran, and Sahai [FOCS '10] proved the same for constant-round protocols (with any non-trivial bias). For the general case, however, no such implication was known. We make progress towards answering the above fundamental question, showing that (strong) coin-flipping protocols safe against a constant bias (concretely, (√2 -1)/2 - o(1)) imply one-way functions.

Details

STOC Conference 2010 Conference Paper

Efficiency improvements in constructing pseudorandom generators from one-way functions

  • Iftach Haitner
  • Omer Reingold
  • Salil P. Vadhan

We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Hastad, Impagliazzo, Levin, and Luby [SICOMP '99]. The key to our construction is a new notion of "next-block pseudoentropy", which is inspired by the notion of "inaccessible entropy" recently introduced in [Haitner, Reingold, Vadhan, Wee, STOC '09]. An additional advantage over previous constructions is that our pseudorandom generators are parallelizable and invoke the one-way function in a non-adaptive manner. Using [Applebaum, Ishai, Kushilevitz, SICOMP '06], this implies the existence of pseudorandom generators in NC^0 based on the existence of one-way functions in NC^1.

Details

FOCS Conference 2009 Conference Paper

A Parallel Repetition Theorem for Any Interactive Argument

  • Iftach Haitner

The question of whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e. g. , 3-message protocols-Bellare, Impagliazzo and Naor [FOCS '97], and public-coin protocols-Haastad, Pass, Pietrzak and Wikstrom [Manuscript '08]), Bellare et. al gave an example of interactive arguments for which parallel repetition does not reduce the soundness error at all. We show that by slightly modifying any interactive argument, in a way that preserves its completeness and only slightly deteriorates its soundness, we get a protocol for which parallel repetition does reduce the error at a weak exponential rate. In this modified version, the verifier flips at the beginning of each round an (1 - 1/4 m), 1/4 m) biased coin (i. e. , 1 is tossed with probability 1/4 m), where m is the round complexity of the (original) protocol. If the coin is one, the verifier halts the interaction and accepts, otherwise it sends the same message that the original verifier would. At the end of the protocol (if reached), the verifier accepts if and only if the original verifier would.

Details

STOC Conference 2009 Conference Paper

Inaccessible entropy

  • Iftach Haitner
  • Omer Reingold
  • Salil P. Vadhan
  • Hoeteck Wee

We put forth a new computational notion of entropy, which measures the (in)feasibility of sampling high entropy strings that are consistent with a given protocol. Specifically, we say that the i'th round of a protocol (A,B) has *accessible entropy* at most k, if no polynomial-time strategy A* can generate messages for A such that the entropy of its message in the i'th round has entropy greater than k when conditioned both on prior messages of the protocol and on prior coin tosses of A*. We say that the protocol has *inaccessible entropy* if the total accessible entropy (summed over the rounds) is noticeably smaller than the real entropy of A's messages, conditioned only on prior messages (but not the coin tosses of A). As applications of this notion, we -- Give a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions. -- Prove that constant-round statistically hiding commitments are necessary for constructing constant-round zero-knowledge proof systems for NP that remain secure under parallel composition (assuming the existence of one-way functions).

Details

FOCS Conference 2007 Conference Paper

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

  • Iftach Haitner
  • Jonathan J. Hoch
  • Omer Reingold
  • Gil Segev 0001

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.

Details