License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.51
URN: urn:nbn:de:0030-drops-133959
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13395/
Go to the corresponding LIPIcs Volume Portal

Montealegre, Pedro ; Ramírez-Romero, Diego ; Rapaport, Ivan

Shared vs Private Randomness in Distributed Interactive Proofs

pdf-format:
LIPIcs-ISAAC-2020-51.pdf (0.6 MB)

Abstract

In distributed interactive proofs, the nodes of a graph G interact with a powerful but untrustable prover who tries to convince them, in a small number of rounds and through short messages, that G satisfies some property. This series of interactions is followed by a phase of distributed verification, which may be either deterministic or randomized, where nodes exchange messages with their neighbors.
The nature of this last verification round defines the two types of interactive protocols. We say that the protocol is of Arthur-Merlin type if the verification round is deterministic. We say that the protocol is of Merlin-Arthur type if, in the verification round, the nodes are allowed to use a fresh set of random bits.
In the original model introduced by Kol, Oshman, and Saxena [PODC 2018], the randomness was private in the sense that each node had only access to an individual source of random coins. Crescenzi, Fraigniaud, and Paz [DISC 2019] initiated the study of the impact of shared randomness (the situation where the coin tosses are visible to all nodes) in the distributed interactive model.
In this work, we continue that research line by showing that the impact of the two forms of randomness is very different depending on whether we are considering Arthur-Merlin protocols or Merlin-Arthur protocols. While private randomness gives more power to the first type of protocols, shared randomness provides more power to the second. Our results also connect shared randomness in distributed interactive proofs with distributed verification, and new lower bounds are obtained.

BibTeX - Entry

@InProceedings{montealegre_et_al:LIPIcs:2020:13395,
  author =	{Pedro Montealegre and Diego Ram{\'\i}rez-Romero and Ivan Rapaport},
  title =	{{Shared vs Private Randomness in Distributed Interactive Proofs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{51:1--51:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13395},
  URN =		{urn:nbn:de:0030-drops-133959},
  doi =		{10.4230/LIPIcs.ISAAC.2020.51},
  annote =	{Keywords: Distributed interactive proofs, Distributed verification, Shared randomness, Private randomness}
}

Keywords: Distributed interactive proofs, Distributed verification, Shared randomness, Private randomness
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI