All reports by Author Iftach Haitner:

__
TR20-089
| 8th June 2020
__

Dror Chawin, Iftach Haitner, Noam Mazor#### Lower Bounds on the Time/Memory Tradeoff of Function Inversion

Revisions: 1

__
TR20-071
| 4th May 2020
__

Iftach Haitner, Yonatan Karidi-Heller#### A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip

Revisions: 1

__
TR19-081
| 31st May 2019
__

Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak#### Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation

Revisions: 1

__
TR19-049
| 2nd April 2019
__

Itay Berman, Iftach Haitner, Eliad Tsfadia#### A Tight Parallel-Repetition Theorem for Random-Terminating Interactive Arguments

Revisions: 2

__
TR18-084
| 24th April 2018
__

Iftach Haitner, Nikolaos Makriyannis, Eran Omri#### On the Complexity of Fair Coin Flipping

__
TR18-071
| 15th April 2018
__

Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak#### Computational Two-Party Correlation

Revisions: 1

__
TR18-031
| 15th February 2018
__

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff#### On the Communication Complexity of Key-Agreement Protocols

Revisions: 2

__
TR17-168
| 5th November 2017
__

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri#### Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Dierentially Private Sampling

Revisions: 6

__
TR17-084
| 2nd May 2017
__

Iftach Haitner, Salil Vadhan#### The Many Entropies in One-Way Functions

Revisions: 1

__
TR15-106
| 22nd June 2015
__

Itay Berman, Iftach Haitner, Aris Tentes#### Coin Flipping of Any Constant Bias Implies One-Way Functions

Revisions: 1

__
TR12-182
| 24th December 2012
__

Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor#### Hardness Preserving Reductions via Cuckoo Hashing

Revisions: 2

__
TR12-129
| 9th October 2012
__

Iftach Haitner, Eran Omri, Hila Zarosim#### On the Power of Random Oracles

Revisions: 3

__
TR10-089
| 26th May 2010
__

Iftach Haitner, Omer Reingold, Salil Vadhan#### Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions

__
TR10-001
| 30th December 2009
__

Iftach Haitner, Mohammad Mahmoody, David Xiao#### A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of $NP$

__
TR09-045
| 20th May 2009
__

Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee#### Inaccessible Entropy

__
TR09-027
| 2nd April 2009
__

Iftach Haitner#### A Parallel Repetition Theorem for Any Interactive Argument

Revisions: 1

__
TR07-038
| 23rd April 2007
__

Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev#### Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

__
TR06-096
| 10th August 2006
__

Iftach Haitner, Omer Reingold#### A New Interactive Hashing Theorem

__
TR05-135
| 19th November 2005
__

Iftach Haitner, Danny Harnik, Omer Reingold#### On the Power of the Randomized Iterate

__
TR04-115
| 1st December 2004
__

Iftach Haitner, Ronen Shaltiel#### Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions

Dror Chawin, Iftach Haitner, Noam Mazor

We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an $s$-bit advice for a randomly chosen function $f\colon [n] \mapsto [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$ (i.e., to find $x$ such that $f(x)=y$). ... more >>>

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

Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak

Consider a PPT two-party protocol ?=(A,B) in which the parties get no private inputs and obtain outputs O^A,O^B?{0,1}, and let V^A and V^B denote the partiesâ€™ individual views. Protocol ? has ?-agreement if Pr[O^A=O^B]=1/2+?. The leakage of ? is the amount of information a party obtains about the event {O^A=O^B}; ... more >>>

Itay Berman, Iftach Haitner, Eliad Tsfadia

Parallel repetition is known to reduce the soundness error of some special cases of interactive arguments: three-message protocols and public-coin protocols. However, it does not do so in the general case.

Haitner [FOCS '09, SiCOMP '13] presented a simple method for transforming any interactive argument $\pi$ into a slightly modified ... more >>>

Iftach Haitner, Nikolaos Makriyannis, Eran Omri

A two-party coin-flipping protocol is $\varepsilon$-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $\varepsilon$. Cleve [STOC '86] showed that $r$-round $o(1/r)$-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript '85] ... more >>>

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

Let $\pi$ be an efficient two-party protocol that given security parameter $\kappa$, both parties output single bits $X_\kappa$ and $Y_\kappa$, respectively. We are interested in how $(X_\kappa,Y_\kappa)$ ``appears'' to an efficient adversary that only views the transcript $T_\kappa$. We make the following contributions:

\begin{itemize}

\item We develop new tools to ...
more >>>

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to the more common public-key based key-agreement protocols. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but they are limited in the number of ... more >>>

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri

In his seminal work, Cleve [STOC 1986] has proved that any r-round coin-flipping protocol can be efficiently biassed by ?(1/r). The above lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner ... more >>>

Iftach Haitner, Salil Vadhan

Computational analogues of information-theoretic notions have given rise to some of the most interesting phenomena in the theory of computation. For example, computational indistinguishability, Goldwasser and Micali '84, which is the computational analogue of statistical distance, enabled the bypassing of Shanon's impossibility results on perfectly secure encryption, and provided the ... more >>>

Itay Berman, Iftach Haitner, Aris Tentes

We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., $.499$) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias $\frac{\sqrt2 -1}2 - o(1) \approx .207$. Unlike ... more >>>

Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor

A common method for increasing the usability and uplifting the security of pseudorandom function families (PRFs) is to ``hash" the inputs into a smaller domain before applying the PRF. This approach, known as ``Levin's trick", is used to achieve ``PRF domain extension" (using a short, e.g., fixed, input length PRF ... more >>>

Iftach Haitner, Eran Omri, Hila Zarosim

In the random oracle model, the parties are given oracle access to a random member of

a (typically huge) function family, and are assumed to have unbounded computational power

(though they can only make a bounded number of oracle queries). This model provides powerful

properties that allow proving the security ...
more >>>

Iftach Haitner, Omer Reingold, Salil 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 Haastad, Impagliazzo, Levin and Luby [SICOMP '99]. The key to our construction is a new notion of next-block pseudoentropy, which is inspired ... more >>>

Iftach Haitner, Mohammad Mahmoody, David Xiao

We investigate the question of what languages can be decided efficiently with the help of a recursive collision-finding oracle. Such an oracle can be used to break collision-resistant hash functions or, more generally, statistically hiding commitments. The oracle we consider, $Sam_d$ where $d$ is the recursion depth, is based on ... more >>>

Iftach Haitner, Omer Reingold, Salil 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 ...
more >>>

Iftach Haitner

The question 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, ... more >>>

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

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 one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme ... more >>>

Iftach Haitner, Omer Reingold

Interactive hashing, introduced by Naor et al. [NOVY98], plays

an important role in many cryptographic protocols. In particular, it

is a major component in all known constructions of

statistically-hiding commitment schemes and of zero-knowledge

arguments based on general one-way permutations and on one-way

functions. Interactive hashing with respect to a ...
more >>>

Iftach Haitner, Danny Harnik, Omer Reingold

We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad et. al. [HILL99], is that pseudorandom generators can be constructed from any one-way function. The second due to Yao [Yao82] states that the existence of weak one-way functions (i.e. functions on which every efficient algorithm ... more >>>

Iftach Haitner, Ronen Shaltiel

A statistical zero knowledge argument for NP is a cryptographic primitive that allows a polynomial-time prover to convince another

polynomial-time verifier of the validity of an NP statement. It is guaranteed that even an infinitely powerful verifier does not learn any

additional information but the validity of the claim.

Naor ... more >>>