Paper 2024/952
Communication Complexity vs Randomness Complexity in Interactive Proofs
Abstract
In this note, we study the interplay between the communication from a verifier in a general private-coin interactive protocol and the number of random bits it uses in the protocol. Under worst-case derandomization assumptions, we show that it is possible to transform any $I$-round interactive protocol that uses $\rho$ random bits into another one for the same problem with the additional property that the verifier's communication is bounded by $O(I\cdot \rho)$. Importantly, this is done with a minor, logarithmic, increase in the communication from the prover to the verifier and while preserving the randomness complexity. Along the way, we introduce a new compression game between computationally-bounded compressor and computationally-unbounded decompressor and a new notion of conditioned efficient distributions that may be of independent interest. Our solutions are based on a combination of perfect hashing and pseudorandom generators.
Note: Preliminary version appears in ITC'24.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Minor revision. ITC 2024.
- Keywords
- interactive proofs
- Contact author(s)
-
benny applebaum @ gmail com
kbhushan @ cse iitb ac in
mp @ cse iitb ac in - History
- 2024-06-14: approved
- 2024-06-13: received
- See all versions
- Short URL
- https://ia.cr/2024/952
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/952,
author = {Benny Applebaum and Kaartik Bhushan and Manoj Prabhakaran},
title = {Communication Complexity vs Randomness Complexity in Interactive Proofs},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/952},
year = {2024},
url = {https://eprint.iacr.org/2024/952}
}