Paper 2015/1046

From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back

Benny Applebaum and Pavel Raykov

Abstract

Göös, Pitassi and Watson (ITCS, 2015) have recently introduced the notion of \emph{Zero-Information Arthur-Merlin Protocols} (ZAM). In this model, which can be viewed as a private version of the standard Arthur-Merlin communication complexity game, Alice and Bob are holding a pair of inputs $x$ and $y$ respectively, and Merlin, the prover, attempts to convince them that some public function $f$ evaluates to 1 on $(x,y)$. In addition to standard completeness and soundness, Göös et al., require an additional ``zero-knowledge'' property which asserts that on each yes-input, the distribution of Merlin's proof leaks no information about the inputs $(x,y)$ to an external observer. In this paper, we relate this new notion to the well-studied model of \emph{Private Simultaneous Messages} (PSM) that was originally suggested by Feige, Naor and Kilian (STOC, 1994). Roughly speaking, we show that the randomness complexity of ZAM essentially corresponds to the communication complexity of PSM, and that the communication complexity of ZAM essentially corresponds to the randomness complexity of PSM. This relation works in both directions where different variants of PSM are being used. Consequently, we derive better upper-bounds on the communication-complexity of ZAM for arbitrary functions. As a secondary contribution, we reveal new connections between different variants of PSM protocols which we believe to be of independent interest.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in TCC 2016
Keywords
information-theoretic securityPrivate Simultaneous MessagesZero-Information Arthur-MerlinSecure Computation
Contact author(s)
raykov pavel @ gmail com
History
2016-07-13: last of 3 revisions
2015-10-29: received
See all versions
Short URL
https://ia.cr/2015/1046
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1046,
      author = {Benny Applebaum and Pavel Raykov},
      title = {From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1046},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1046}},
      url = {https://eprint.iacr.org/2015/1046}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.