From Statistical Zero Knowledge to Secret Sharing.
Vinod Vaikuntanathan, Prashant Nalini Vasudevan · IACR Cryptology ePrint Archive · 2015
We show a general connection between various types of statistical zero-knowledge (SZK) proof systems and (unconditionally secure) secret sharing schemes. Viewed through the SZK lens, we obtain several new results on secret-sharing: Characterizations: We obtain an almost-characterization of access structures for which there are secret-sharing schemes with an ecient sharing algorithm (but not necessarily ecient reconstruction). In particular, we show that for every language L2 SZKL (the class of languages that have statistical zero knowledge proofs with log-space veriers and simulators), a (monotonized) access structure associated with L has such a secretsharing 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 ecient 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 rst combinatorial access structure that is conjectured to be outside NC but has an ecient secret-sharing scheme. Previous such constructions (Beimel and Ishai; CCC 2001) were algebraic and number-theoretic in nature. Limitations: We show that universally-ecie nt 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 DSPACE(q(n)).