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 pred : [ N ] [ 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 ( 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 ( log N log log N ) = N o (1) .

Prior to this work, the best protocols for both primitives required communication complexity 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.