Paper 2017/164

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

Benny Applebaum, Barak Arkis, Pavel Raykov, and Prashant Nalini Vasudevan

Abstract

In the \emph{conditional disclosure of secrets} problem (Gertner et al., J. Comput. Syst. Sci., 2000) 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 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. 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 $$ can be turned into a CDS for its complement $$ with only a minor blow-up in complexity. More generally, for a (possibly non-monotone) predicate $$, we obtain a CDS for $$ whose cost is essentially linear in the formula size of $$ and polynomial in the CDS complexity of $$. 2. *Amplification* It is possible to reduce the privacy and correctness error of a CDS from constant to $$ with a multiplicative overhead of $$. Moreover, this overhead can be amortized over $$-bit secrets. 3. *Amortization* Every predicate $$ over $$-bit inputs admits a CDS for multi-bit secrets whose amortized communication complexity per secret bit grows linearly with the input length $$ for sufficiently long secrets. In contrast, the best known upper-bound for single-bit secrets is exponential in $$. 4. *Lower-bounds* There exists a (non-explicit) predicate $$ over $$-bit inputs for which any perfect (single-bit) CDS requires communication of at least $$. This is an exponential improvement over the previously known $$ 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.

Note: Removed the application to "dense forbidden graph access structures" due to a flaw in the argument