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

In the 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 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. Following Gay et al. (Crypto 2015), we study the communication complexity of CDS protocols and derive the following positive and negative results. - (Closure): A CDS for f can be turned into a CDS for its complement (f) over bar 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),..., 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 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. - (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. - (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.