All reports by Author Ron Rothblum:

__
TR20-157
| 21st October 2020
__

Guy Rothblum, Ron Rothblum#### Batch Verification and Proofs of Proximity with Polylog Overhead

__
TR20-147
| 24th September 2020
__

Inbar Kaslasi, Prashant Nalini Vasudevan, Guy Rothblum, Ron Rothblum, Adam Sealfon#### Batch Verification for Statistical Zero Knowledge Proofs

Revisions: 1

__
TR19-169
| 21st November 2019
__

Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev#### On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds

Revisions: 1

__
TR19-127
| 19th September 2019
__

Noga Ron-Zewi, Ron Rothblum#### Local Proofs Approaching the Witness Length

__
TR18-161
| 13th September 2018
__

Justin Holmgren, Ron Rothblum#### Delegating Computations with (almost) Minimal Time and Space Overhead

__
TR18-022
| 1st February 2018
__

Omer Reingold, Guy Rothblum, Ron Rothblum#### Efficient Batch Verification for UP

__
TR17-172
| 3rd November 2017
__

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

__
TR17-143
| 26th September 2017
__

Tom Gur, Govind Ramnarayan, Ron Rothblum#### Relaxed Locally Correctable Codes

Revisions: 1

__
TR17-097
| 31st May 2017
__

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

Revisions: 1

__
TR16-061
| 17th April 2016
__

Omer Reingold, Ron Rothblum, Guy Rothblum#### Constant-Round Interactive Proofs for Delegating Computation

Revisions: 2

Guy Rothblum, Ron Rothblum

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication (without making cryptographic assumptions or bounding the computational power of a malicious Alice)? ... more >>>

Inbar Kaslasi, Prashant Nalini Vasudevan, Guy Rothblum, Ron Rothblum, Adam Sealfon

A statistical zero-knowledge proof (SZK) for a problem $\Pi$ enables a computationally unbounded prover to convince a polynomial-time verifier that $x \in \Pi$ without revealing any additional information about $x$ to the verifier, in a strong information-theoretic sense.

Suppose, however, that the prover wishes to convince the verifier that $k$ ... more >>>

Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev

The Exponential-Time Hypothesis ($ETH$) is a strengthening of the $\mathcal{P} \neq \mathcal{NP}$ conjecture, stating that $3\text{-}SAT$ on $n$ variables cannot be solved in time $2^{\epsilon\cdot n}$, for some $\epsilon>0$. In recent years, analogous hypotheses that are ``exponentially-strong'' forms of other classical complexity conjectures (such as $\mathcal{NP}\not\subseteq\mathcal{BPP}$ or $co\text{-}\mathcal{NP}\not\subseteq \mathcal{NP}$) have ... more >>>

Noga Ron-Zewi, Ron Rothblum

Interactive oracle proofs (IOPs) are a hybrid between interactive proofs and PCPs. In an IOP the prover is allowed to interact with a verifier (like in an interactive proof) by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits ... more >>>

Justin Holmgren, Ron Rothblum

The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as ... more >>>

Omer Reingold, Guy Rothblum, Ron Rothblum

Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by ... 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 >>>

Tom Gur, Govind Ramnarayan, Ron Rothblum

Locally decodable codes (LDCs) and locally correctable codes (LCCs) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only few bits from a noisy codeword. These codes have found numerous applications both in theory and in practice.

A natural relaxation of ... 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 >>>

Omer Reingold, Ron Rothblum, Guy Rothblum

The celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an ... more >>>