Following Gay, Kerenidis, and Wee (Crypto 2015), we study the communication complexity of CDS protocols and derive the following positive and negative results.
1. *Closure* A CDS for $f$ can be turned into a CDS for its complement $\bar{f}$ with only a minor blow-up in complexity. More generally, for a (possibly non-monotone) predicate $h$, we obtain a CDS for $h(f_1,\ldots,f_m)$ whose cost is essentially linear in the formula size of $h$ and polynomial in the CDS complexity of $f_i$.
2. *Amplification* It is possible to reduce the privacy and correctness error of a CDS from constant to $2^{-k}$ with a multiplicative overhead of $O(k)$. Moreover, this overhead can be amortized over $k$-bit secrets.
3. *Amortization* Every predicate $f$ over $n$-bit inputs admits a CDS for multi-bit secrets whose amortized communication complexity per secret bit grows linearly with the input length $n$ for sufficiently long secrets. In contrast, the best known upper-bound for single-bit secrets is exponential in $n$.
4. *Lower-bounds* There exists a (non-explicit) predicate $f$ over $n$-bit inputs for which any perfect (single-bit) CDS requires communication of at least $\Omega(n)$. This is an exponential improvement over the previously known $\Omega(\log n)$ lower-bound.
5. *Separations* There exists an (explicit) predicate whose CDS complexity is exponentially smaller than its randomized communication complexity. This matches a lower-bound of Gay et. al., and, combined with another result of theirs, yields an exponential separation between the communication complexity of linear CDS and non-linear CDS. This is the first provable gap between the communication complexity of linear CDS (which captures most known protocols) and non-linear CDS.
Category / Keywords: foundations / Communication Complexity, Conditional Disclosure of Secrets, Amplification, Closure, Amortization, Lower-bounds, Separations Date: received 20 Feb 2017, last revised 1 May 2017 Contact author: raykov pavel at gmail com Available format(s): PDF | BibTeX Citation Note: Removed the application to "dense forbidden graph access structures" due to a flaw in the argument Version: 20170501:183731 (All versions of this report) Short URL: ia.cr/2017/164 Discussion forum: Show discussion | Start new discussion