All reports by Author Ron D. Rothblum:

__
TR24-116
| 6th July 2024
__

Lijie Chen, Ron D. Rothblum, Roei Tell#### Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)

__
TR24-114
| 12th July 2024
__

Nir Bitansky, Ron D. Rothblum, Prahladh Harsha, Yuval Ishai, David Wu#### Dot-Product Proofs and Their Applications

__
TR23-097
| 2nd July 2023
__

Joshua Cook, Ron D. Rothblum#### Efficient Interactive Proofs for Non-Deterministic Bounded Space

Revisions: 1

__
TR22-097
| 3rd July 2022
__

Lijie Chen, Ron D. Rothblum, Roei Tell#### Unstructured Hardness to Average-Case Randomness

__
TR22-017
| 15th February 2022
__

Ron D. Rothblum, Prashant Nalini Vasudevan#### Collision-Resistance from Multi-Collision-Resistance

Revisions: 2

__
TR21-127
| 30th August 2021
__

Ron D. Rothblum, Michael Ezra#### Small Circuits Imply Efficient Arthur-Merlin Protocols

Revisions: 1

__
TR19-038
| 7th March 2019
__

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

Revisions: 1

Lijie Chen, Ron D. Rothblum, Roei Tell

A classical challenge in complexity theory and cryptography is to simulate interactive proof systems by non-interactive proof systems. In this work we leverage approaches from recent works in derandomization to address this challenge, focusing on non-interactive simulations that are sound against uniform adversarial algorithms.

Our results concern fundamental questions in ... more >>>

Nir Bitansky, Ron D. Rothblum, Prahladh Harsha, Yuval Ishai, David Wu

A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement $x$ and the proof ${\pi}$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a single dot-product query $\langle {q},({x} \| {\pi})\rangle$ jointly to ${x}$ and ${\pi}$. A DPP can ... more >>>

Joshua Cook, Ron D. Rothblum

The celebrated $\mathbf{IP}=\mathbf{PSPACE}$ Theorem gives an efficient interactive proof for any bounded-space algorithm. In this work we study interactive proofs for non-deterministic bounded space computations. While Savitch's Theorem shows that nondeterministic bounded-space algorithms can be simulated by deterministic bounded-space algorithms, this simulation has a quadratic overhead. We give interactive protocols ... more >>>

Lijie Chen, Ron D. Rothblum, Roei Tell

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

Ron D. Rothblum, Prashant Nalini Vasudevan

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

Ron D. Rothblum, Michael Ezra

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

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