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.ITCS.2019.4
URN: urn:nbn:de:0030-drops-100976
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10097/
Go to the corresponding LIPIcs Volume Portal

Applebaum, Benny ; Vasudevan, Prashant Nalini

Placing Conditional Disclosure of Secrets in the Communication Complexity Universe

pdf-format:
LIPIcs-ITCS-2019-4.pdf (0.5 MB)

Abstract

In the conditional disclosure of secrets (CDS) problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold n-bit inputs x and y respectively, wish to release a common secret z to Carol (who knows both x and y) if and only if the input (x,y) satisfies some predefined predicate f. Alice and Bob are allowed to send a single message to Carol which may depend on their inputs and some shared randomness, and the goal is to minimize the communication complexity while providing information-theoretic security.
Despite the growing interest in this model, very few lower-bounds are known. In this paper, we relate the CDS complexity of a predicate f to its communication complexity under various communication games. For several basic predicates our results yield tight, or almost tight, lower-bounds of Omega(n) or Omega(n^{1-epsilon}), providing an exponential improvement over previous logarithmic lower-bounds.
We also define new communication complexity classes that correspond to different variants of the CDS model and study the relations between them and their complements. Notably, we show that allowing for imperfect correctness can significantly reduce communication - a seemingly new phenomenon in the context of information-theoretic cryptography. Finally, our results show that proving explicit super-logarithmic lower-bounds for imperfect CDS protocols is a necessary step towards proving explicit lower-bounds against the class AM, or even AM cap coAM - a well known open problem in the theory of communication complexity. Thus imperfect CDS forms a new minimal class which is placed just beyond the boundaries of the "civilized" part of the communication complexity world for which explicit lower-bounds are known.

BibTeX - Entry

@InProceedings{applebaum_et_al:LIPIcs:2018:10097,
  author =	{Benny Applebaum and Prashant Nalini Vasudevan},
  title =	{{Placing Conditional Disclosure of Secrets in the Communication Complexity Universe}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10097},
  URN =		{urn:nbn:de:0030-drops-100976},
  doi =		{10.4230/LIPIcs.ITCS.2019.4},
  annote =	{Keywords: Conditional Disclosure of Secrets, Information-Theoretic Security}
}

Keywords: Conditional Disclosure of Secrets, Information-Theoretic Security
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

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