All reports by Author Itay Berman:

__
TR19-049
| 2nd April 2019
__

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

Revisions: 2

__
TR19-038
| 7th March 2019
__

Itay Berman, Akshay Degwekar, Ron D. Rothblum, Prashant Vasudevan#### Statistical Difference Beyond the Polarizing Regime

Revisions: 1

__
TR17-172
| 3rd November 2017
__

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan#### From Laconic Zero-Knowledge to Public-Key Cryptography

__
TR17-097
| 31st May 2017
__

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan#### Multi Collision Resistant Hash Functions and their Applications

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

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

Itay Berman, Akshay Degwekar, Ron D. Rothblum, Prashant Vasudevan

The polarization lemma for statistical distance ($\mathrm{SD}$), due to Sahai and Vadhan (JACM, 2003), is an efficient transformation taking as input a pair of circuits $(C_0,C_1)$ and an integer $k$ and outputting a new pair of circuits $(D_0,D_1)$ such that if $\mathrm{SD}(C_0,C_1)\geq\alpha$ then $\mathrm{SD}(D_0,D_1) \geq 1-2^{-k}$ and if $\mathrm{SD}(C_0,C_1) \leq ... more >>>

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

Since its inception, public-key encryption (PKE) has been one of the main cornerstones of cryptography. A central goal in cryptographic research is to understand the foundations of public-key encryption and in particular, base its existence on a natural and generic complexity-theoretic assumption. An intriguing candidate for such an assumption is ... more >>>

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

Collision resistant hash functions are functions that shrink their input, but for which it is computationally infeasible to find a collision, namely two strings that hash to the same value (although collisions are abundant).

In this work we study multi-collision resistant hash functions (MCRH) a natural relaxation of collision resistant ... 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 >>>