Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Chethan Kamath:

TR23-077 | 25th May 2023
Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, Prashant Nalini Vasudevan

Batch Proofs are Statistically Hiding

Revisions: 2

Batch proofs are proof systems that convince a verifier that $x_1,\dots, x_t \in L$, for some $NP$ language $L$, with communication that is much shorter than sending the $t$ witnesses. In the case of statistical soundness (where the cheating prover is unbounded but honest prover is efficient), interactive batch proofs ... more >>>

TR19-074 | 22nd May 2019
Arka Rai Choudhuri, Pavel Hubá?ek, 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 >>>

ISSN 1433-8092 | Imprint