Welcome to the resource topic for 2017/359
Title:
Conditional Disclosure of Secrets via Non-Linear Reconstruction
Authors: Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee
Abstract: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.
ePrint: https://eprint.iacr.org/2017/359
Talk: https://www.youtube.com/watch?v=ObTbv-LrHnQ
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 .