Paper 2018/1154
Leakage Resilient Secret Sharing and Applications
Akshayaram Srinivasan and Prashant Nalini Vasudevan
Abstract
A secret sharing scheme allows a dealer to share a secret among a set of $n$ parties such that any authorized subset of the parties can recover the secret, while any unauthorized subset of the parties learns no information about the secret. A local leakageresilient secret sharing scheme (introduced in independent works by (Goyal and Kumar, STOC 18) and (Benhamouda, Degwekar, Ishai and Rabin, Crypto 18)) additionally requires the secrecy to hold against every unauthorized set of parties even if they obtain some bounded local leakage from every other share. The leakage is said to be local if it is computed independently for each share. So far, the only known constructions of local leakage resilient secret sharing schemes are for threshold access structures for very low ($O(1)$) or very high ($n o(\log n)$) thresholds. In this work, we give a compiler that takes a secret sharing scheme for any monotone access structure and produces a local leakage resilient secret sharing scheme for the same access structure, with only a constantfactor blowup in the sizes of the shares. Furthermore, the resultant secret sharing scheme has optimal leakageresilience rate i.e., the ratio between the leakage tolerated and the size of each share can be made arbitrarily close to $1$. Using this secret sharing scheme as the main building block, we obtain the following results: 1. Rate Preserving NonMalleable Secret Sharing: We give a compiler that takes any secret sharing scheme for a 4monotone access structure with rate $R$ and converts it into a nonmalleable secret sharing scheme for the same access structure with rate $\Omega(R)$. The prior such nonzero rate construction (Badrinarayanan and Srinivasan, 18) only achieves a rate of $\Theta(R/{t_{\max}\log^2 n})$, where $t_{\max}$ is the maximum size of any minimal set in the access structure. As a special case, for any threshold $t \geq 4$ and an arbitrary $n \geq t$, we get the first constant rate construction of $t$outof$n$ nonmalleable secret sharing. 2. LeakageTolerant Multiparty Computation for General Interaction Pattern: For any function, we give a reduction from constructing leakagetolerant secure multiparty computation protocols obeying any interaction pattern to constructing a secure (and not necessarily leakagetolerant) protocol for a related function obeying the star interaction pattern. This improves upon the result of (Halevi et al., ITCS 2016), who constructed a protocol that is secure in a leakfree environment.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Contact author(s)
 akshayaram @ berkeley edu
 History
 20190819: last of 2 revisions
 20181203: received
 See all versions
 Short URL
 https://ia.cr/2018/1154
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/1154, author = {Akshayaram Srinivasan and Prashant Nalini Vasudevan}, title = {Leakage Resilient Secret Sharing and Applications}, howpublished = {Cryptology ePrint Archive, Paper 2018/1154}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/1154}}, url = {https://eprint.iacr.org/2018/1154} }