Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations

In the conditional disclosure of secrets (CDS) problem [Gertner et al., J. Comput. System Sci., 60 (2000), pp. 592--629] Alice and Bob, who hold inputs $x$ and $y$, respectively, wish to release a common secret $s$ 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 joint randomness and the goal is to minimize the communication complexity while providing information-theoretic security. In this work, we initiate the study of CDS manipulation techniques and derive the following positive and negative results: (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 nonmonotone) 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$. (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. (Amortization) Every predicate $f$ over $n$-bit inputs admits a CDS for multibit 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$. (Lower-bounds) There exists a (nonexplicit) 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. (Separations) There exists an (explicit) predicate whose CDS complexity is exponentially smaller than its randomized communication complexity. This matches a lower-bound of Gay, Kerenidis, and Wee [Advances in Cryptology, Lecture Notes in Comput. Sci. 9216, Springer, New York, 2015, pp. 485--502] 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 nonlinear CDS.