3 papers
cs.CR2021
Hardness-Preserving Reductions via Cuckoo Hashing
Itay Berman, Iftach Haitner, Ilan Komargodski +1
The focus of this work is \emph{hardness-preserving} transformations of somewhat limited pseudorandom functions families (PRFs) into ones with more versatile characteristics. Consi…
cs.CR2021
Coin Flipping of \emph{Any} Constant Bias Implies One-Way Functions
Itay Berman, Iftach Haitner, Aris Tentes
We show that the existence of a coin-flipping protocol safe against \emph{any} non-trivial constant bias (\eg ) implies the existence of one-way functions. This improves upon…
cs.CR2021
A Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KL-Divergence
Itay Berman, Iftach Haitner, Eliad Tsfadia
Hardness amplification is a central problem in the study of interactive protocols. While ``natural'' parallel repetition transformation is known to reduce the soundness error of so…