Paper 2017/164
Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lowerbounds, 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 informationtheoretic 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 blowup 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$. 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 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 upperbound for singlebit secrets is exponential in $n$. 4. *Lowerbounds* There exists a (nonexplicit) predicate $f$ over $n$bit inputs for which any perfect (singlebit) CDS requires communication of at least $\Omega(n)$. This is an exponential improvement over the previously known $\Omega(\log n)$ lowerbound. 5. *Separations* There exists an (explicit) predicate whose CDS complexity is exponentially smaller than its randomized communication complexity. This matches a lowerbound of Gay et. al., and, combined with another result of theirs, yields an exponential separation between the communication complexity of linear CDS and nonlinear CDS. This is the first provable gap between the communication complexity of linear CDS (which captures most known protocols) and nonlinear CDS.
Note: Removed the application to "dense forbidden graph access structures" due to a flaw in the argument
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Communication ComplexityConditional Disclosure of SecretsAmplificationClosureAmortizationLowerboundsSeparations
 Contact author(s)
 raykov pavel @ gmail com
 History
 20170501: last of 2 revisions
 20170223: received
 See all versions
 Short URL
 https://ia.cr/2017/164
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/164, author = {Benny Applebaum and Barak Arkis and Pavel Raykov and Prashant Nalini Vasudevan}, title = {Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lowerbounds, and Separations}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/164}, year = {2017}, url = {https://eprint.iacr.org/2017/164} }