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

摘要

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 f can be turned into a CDS for its complement 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 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 ( n ) . This is an exponential improvement over the previously known ( 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.