Characterizations: We obtain an almost-characterization of access structures for which there are secret-sharing schemes with an efficient sharing algorithm (but not necessarily efficient reconstruction). In particular, we show that for every language $L \in \SZKL$ (the class of languages that have statistical zero knowledge proofs with log-space verifiers and simulators), a (monotonized) access structure associated with $L$ has such a secret-sharing scheme. Conversely, we show that such secret-sharing schemes can only exist for languages in $\SZK$.
Constructions: We show new constructions of secret-sharing schemes with efficient sharing and reconstruction for access structures that are in $\P$, but are not known to be in $\NC$, namely Bounded-Degree Graph Isomorphism and constant-dimensional lattice problems. In particular, this gives us the first combinatorial access structure that is conjectured to be outside $\NC$ but has an efficient secret-sharing scheme. Previous such constructions (Beimel and Ishai; CCC 2001) were algebraic and number-theoretic in nature.
Limitations: We show that universally-efficient secret-sharing schemes, where the complexity of computing the shares is a polynomial independent of the complexity of deciding the access structure, cannot exist for all (monotone languages in) $\P$, unless there is a polynomial $q$ such that $\P \subseteq \DSPACE(q(n))$.Category / Keywords: foundations / zero knowledge, secret sharing Original Publication (with minor differences): IACR-ASIACRYPT-2015 Date: received 24 Mar 2015, last revised 7 Sep 2015 Contact author: prashvas at mit edu Available format(s): PDF | BibTeX Citation Version: 20150907:173008 (All versions of this report) Short URL: ia.cr/2015/281 Discussion forum: Show discussion | Start new discussion