All reports by Author Guy 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

__
TR20-058
| 24th April 2020
__

Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff#### Interactive Proofs for Verifying Machine Learning

__
TR19-176
| 4th December 2019
__

Gal Arnon, Guy Rothblum#### On Prover-Efficient Public-Coin Emulation of Interactive Proofs

Revisions: 1

__
TR19-074
| 22nd May 2019
__

Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum#### Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir

__
TR19-060
| 18th April 2019
__

Scott Aaronson, Guy Rothblum#### Gentle Measurement of Quantum States and Differential Privacy

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

Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff

We consider the following question: using a source of labeled data and interaction with an untrusted prover, what is the complexity of verifying that a given hypothesis is "approximately correct"? We study interactive proof systems for PAC verification, where a verifier that interacts with a prover is required to accept ... more >>>

Gal Arnon, Guy Rothblum

A central question in the study of interactive proofs is the relationship between private-coin proofs, where the verifier is allowed to hide its randomness from the prover, and public-coin proofs, where the verifier's random coins are sent to the prover.

In this work, we study transformations ...
more >>>

Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum

The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocolâ€™s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.

We show that ... more >>>

Scott Aaronson, Guy Rothblum

In differential privacy (DP), we want to query a database about $n$ users, in a way that "leaks at most $\varepsilon$ about any individual user," even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure $n$ quantum states, in a way that "damages the ... more >>>