Cryptology ePrint Archive: Report 2017/164

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

Benny Applebaum and Barak Arkis and 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. \begin​{itemize} \item (\textbf{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$.

\item (\textbf{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. \item (\textbf{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$.

\item (\textbf{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.

\item (\textbf{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. \end{itemize} Our results solve several open problems posed by Gay et al., and have applications to secret-sharing schemes for forbidden-graph access structures.

Category / Keywords: foundations / Communication Complexity, Conditional Disclosure of Secrets, Amplification, Closure, Amortization, Lower-bounds, Separations

Date: received 20 Feb 2017, last revised 8 Mar 2017

Contact author: raykov pavel at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20170308:114537 (All versions of this report)

Short URL: ia.cr/2017/164

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]