Communication Complexity vs Randomness Complexity in Interactive Proofs

Benny Applebaum; Kaartik Bhushan; Manoj Prabhakaran

Paper 2024/952

Communication Complexity vs Randomness Complexity in Interactive Proofs

Benny Applebaum

, Tel Aviv University

Kaartik Bhushan, IIT Bombay

Manoj Prabhakaran

, IIT Bombay

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