Paper 2015/281

Secret Sharing and Statistical Zero Knowledge

Vinod Vaikuntanathan and Prashant Nalini Vasudevan

Abstract

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 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))$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in ASIACRYPT 2015
Keywords
zero knowledgesecret sharing
Contact author(s)
prashvas @ mit edu
History
2015-09-07: revised
2015-03-25: received
See all versions
Short URL
https://ia.cr/2015/281
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/281,
      author = {Vinod Vaikuntanathan and Prashant Nalini Vasudevan},
      title = {Secret Sharing and Statistical Zero Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2015/281},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/281}},
      url = {https://eprint.iacr.org/2015/281}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.