Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / information theoretic cryptography, communication complexity

Original Publication (with major differences): Innovation in Theoretical Computer Science (ITCS) 2019

Date: received 29 Nov 2018

Contact author: benny applebaum at gmail com

Available format(s): PDF | BibTeX Citation

Note: Draft of the full version.

Version: 20181203:032039 (All versions of this report)

Short URL: ia.cr/2018/1169


[ Cryptology ePrint archive ]