Welcome to the resource topic for 2017/164
Title:
Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations
Authors: Benny Applebaum, Barak Arkis, Pavel Raykov, 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 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.
ePrint: https://eprint.iacr.org/2017/164
Talk: https://www.youtube.com/watch?v=g3bJX0AN9OE
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .