Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Prashant Nalini Vasudevan:

TR24-024 | 14th February 2024
Changrui Mu, Shafik Nassar, Ron Rothblum, Prashant Nalini Vasudevan

Strong Batching for Non-Interactive Statistical Zero-Knowledge

A zero-knowledge proof enables a prover to convince a verifier that $x \in S$, without revealing anything beyond this fact. By running a zero-knowledge proof $k$ times, it is possible to prove (still in zero-knowledge) that $k$ separate instances $x_1,\dots,x_k$ are all in $S$. However, this increases the communication by ... more >>>

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

Batch Proofs are Statistically Hiding

Revisions: 4

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

TR23-060 | 17th April 2023
Sagnik Saha, Nikolaj Schwartzbach, Prashant Nalini Vasudevan

The Planted $k$-SUM Problem: Algorithms, Lower Bounds, Hardness Amplification, and Cryptography

Revisions: 1

In the average-case $k$-SUM problem, given $r$ integers chosen uniformly at random from $\{0,\ldots,M-1\}$, the objective is to find a set of $k$ numbers that sum to $0$ modulo $M$ (this set is called a ``solution''). In the related $k$-XOR problem, given $k$ uniformly random Boolean vectors of length $\log{M}$, ... more >>>

TR22-017 | 15th February 2022
Ron D. Rothblum, Prashant Nalini Vasudevan

Collision-Resistance from Multi-Collision-Resistance

Revisions: 2

Collision-resistant hash functions (CRH) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of CRH called t-way multi-collision-resistant hash functions (t-MCRH). These are families of functions for which it is computationally hard to find a t-way collision, even though such collisions are abundant (and even ... more >>>

ISSN 1433-8092 | Imprint