All reports by Author Guy Rothblum:

__
TR22-052
| 18th April 2022
__

Tal Herman, Guy Rothblum#### Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties

__
TR21-146
| 19th October 2021
__

Guy Goldberg, Guy Rothblum#### Sample-Based Proofs of Proximity

Revisions: 1

__
TR20-176
| 26th November 2020
__

Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona#### Outcome Indistinguishability

__
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

Revisions: 1

__
TR19-176
| 4th December 2019
__

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

Revisions: 4

__
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

Tal Herman, Guy Rothblum

Given i.i.d. samples from an unknown distribution over a large domain $[N]$, approximating several basic quantities, including the distribution's support size, its entropy, and its distance from the uniform distribution, requires $\Theta(N / \log N)$ samples [Valiant and Valiant, STOC 2011].

Suppose, however, that we can interact with a powerful ... more >>>

Guy Goldberg, Guy Rothblum

Suppose we have random sampling access to a huge object, such as a graph or a database.

Namely, we can observe the values of \emph{random} locations in the object, say random records in the database or random edges in the graph.

We cannot, however, query locations of our choice. Can ...
more >>>

Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona

Prediction algorithms assign numbers to individuals that are popularly understood as individual ``probabilities''---what is the probability of 5-year survival after cancer diagnosis?---and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are ... more >>>

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