Paper 2017/359

Conditional Disclosure of Secrets via Non-Linear Reconstruction

Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee


We present new protocols for conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. - For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$, we present two protocols that achieve $o(N^{1/2})$ communication: the first achieves $O(N^{1/3})$ communication and the second achieves sub-polynomial $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$ communication. - As a corollary, we obtain improved share complexity for forbidden graph access structures. Namely, for every graph on $N$ vertices, there is a secret-sharing scheme for $N$ parties in which each pair of parties can reconstruct the secret if and only if the corresponding vertices in $G$ are connected, and where each party gets a share of size $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$. Prior to this work, the best protocols for both primitives required communication complexity $\tilde{O}(N^{1/2})$. Indeed, this is essentially the best that all prior techniques could hope to achieve as they were limited to so-called ``linear reconstruction''. This is the first work to break this $O(N^{1/2})$ ``linear reconstruction'' barrier in settings related to secret sharing. To obtain these results, we draw upon techniques for non-linear reconstruction developed in the context of information-theoretic private information retrieval. We further extend our results to the setting of private simultaneous messages (PSM), and provide applications such as an improved attribute-based encryption (ABE) for quadratic polynomials.

Note: Minor revisions.

Available format(s)
Publication info
Published by the IACR in CRYPTO 2017
secret sharinginformation theoretic
Contact author(s)
liutr @ mit edu
vinodv @ csail mit edu
wee @ di ens fr
2017-06-12: revised
2017-04-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tianren Liu and Vinod Vaikuntanathan and Hoeteck Wee},
      title = {Conditional Disclosure of Secrets via Non-Linear Reconstruction},
      howpublished = {Cryptology ePrint Archive, Paper 2017/359},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.