Paper Info
Title
Conditional Disclosure of Secrets via Non-linear Reconstruction.
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 P : [N] x [N] -> {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(root logN log logN)) = 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(root logN log logN)) = N-o(1). Prior to this work, the best protocols for both primitives required communication complexity (O) over tilde (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.
Year
DOI
Venue
2017
10.1007/978-3-319-63688-7_25
ADVANCES IN CRYPTOLOGY - CRYPTO 2017, PT I
Field
DocType
Volume
Nonlinear system,Computer science,Theoretical computer science,Third party,If and only if,Predicate (grammar)
Conference
10401
ISSN
Citations 
PageRank 
0302-9743
7
0.48
References 
Authors
30
3
Name
Order
Citations
PageRank
Tianren Liu1204.08
Vinod Vaikuntanathan25353200.79
Hoeteck Wee3161386.36