Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR19-038 | 7th March 2019
Itay Berman, Akshay Degwekar, Ron D. Rothblum, Prashant Vasudevan

Statistical Difference Beyond the Polarizing Regime

Revisions: 1

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

TR17-172 | 3rd November 2017
Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

From Laconic Zero-Knowledge to Public-Key Cryptography

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

TR17-097 | 31st May 2017
Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

Multi Collision Resistant Hash Functions and their Applications

Revisions: 1

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

TR15-106 | 22nd June 2015
Itay Berman, Iftach Haitner, Aris Tentes

Coin Flipping of Any Constant Bias Implies One-Way Functions

Revisions: 1

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

TR12-182 | 24th December 2012
Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor

Hardness Preserving Reductions via Cuckoo Hashing

Revisions: 2

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

ISSN 1433-8092 | Imprint