Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ron D. Rothblum:

TR22-097 | 3rd July 2022
Lijie Chen, Ron D. Rothblum, Roei Tell

Unstructured Hardness to Average-Case Randomness

The leading technical approach in uniform hardness-to-randomness in the last two decades faced several well-known barriers that caused results to rely on overly strong hardness assumptions, and yet still yield suboptimal conclusions.

In this work we show uniform hardness-to-randomness results that *simultaneously break through all of the known barriers*. Specifically, ... more >>>

TR22-017 | 15th February 2022
Ron D. Rothblum, Prashant Nalini Vasudevan

Collision-Resistance from Multi-Collision-Resistance

Revisions: 2

Collision-resistant hash functions (CRH) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of CRH called t-way multi-collision-resistant hash functions (t-MCRH). These are families of functions for which it is computationally hard to find a t-way collision, even though such collisions are abundant (and even ... more >>>

TR21-127 | 30th August 2021
Ron D. Rothblum, Michael Ezra

Small Circuits Imply Efficient Arthur-Merlin Protocols

Revisions: 1

The inner product function $\langle x,y \rangle = \sum_i x_i y_i \bmod 2$ can be easily computed by a (linear-size) ${AC}^0(\oplus)$ circuit: that is, a constant depth circuit with AND, OR and parity (XOR) gates. But what if we impose the restriction that the parity gates can only be on ... 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 >>>

ISSN 1433-8092 | Imprint