2026-07-21T19:38:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20510 2024-08-06T05:20:07Z ddc:004 open_access

Communication Complexity vs Randomness Complexity in Interactive Proofs Applebaum, Benny Bhushan, Kaartik Prabhakaran, Manoj Interactive Proof Systems Communication Complexity Hash Functions Pseudo-Random Generators Compression In this work, 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 ρ random bits into another one for the same problem with the additional property that the verifier’s communication is bounded by O(I⋅ ρ). 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benny Applebaum and Kaartik Bhushan and Manoj Prabhakaran 2024 Is Part Of LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2024.2 urn:nbn:de:0030-drops-205103 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.2 eng https://creativecommons.org/licenses/by/4.0/legalcode