Paper 2018/1169

Placing Conditional Disclosure of Secrets in the Communication Complexity Universe

Benny Applebaum and Prashant Nalini Vasudevan

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 $\text{AM}\cap \text{co-AM}$ -- 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.

Note: Draft of the full version.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.Innovation in Theoretical Computer Science (ITCS) 2019
Keywords
information theoretic cryptographycommunication complexity
Contact author(s)
benny applebaum @ gmail com
History
2018-12-03: received
Short URL
https://ia.cr/2018/1169
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1169,
      author = {Benny Applebaum and Prashant Nalini Vasudevan},
      title = {Placing Conditional Disclosure of Secrets in the Communication Complexity Universe},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1169},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1169}},
      url = {https://eprint.iacr.org/2018/1169}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.