Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > GUY ROTHBLUM:
All reports by Author Guy Rothblum:

TR19-176 | 4th December 2019
Gal Arnon, Guy Rothblum

On Prover-Efficient Public-Coin Emulation of Interactive Proofs

Revisions: 1

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


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

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


TR19-060 | 18th April 2019
Scott Aaronson, Guy Rothblum

Gentle Measurement of Quantum States and Differential Privacy

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




ISSN 1433-8092 | Imprint