Paper 2018/1144
Revisiting NonMalleable Secret Sharing
Saikrishna Badrinarayanan and Akshayaram Srinivasan
Abstract
A threshold secret sharing scheme (with threshold $t$) allows a dealer to share a secret among a set of parties such that any group of $t$ or more parties can recover the secret and no group of at most $t1$ parties learn any information about the secret. A nonmalleable threshold secret sharing scheme, introduced in the recent work of Goyal and Kumar (STOC'18), additionally protects a threshold secret sharing scheme when its shares are subject to tampering attacks. Specifically, it guarantees that the reconstructed secret from the tampered shares is either the original secret or something that is unrelated to the original secret. In this work, we continue the study of threshold nonmalleable secret sharing against the class of tampering functions that tamper each share independently. We focus on achieving greater efficiency and guaranteeing a stronger security property. We obtain the following results:  Rate Improvement. We give the first construction of a threshold nonmalleable secret sharing scheme that has rate $> 0$. Specifically, for every $n,t \geq 4$, we give a construction of a $t$outof$n$ nonmalleable secret sharing scheme with rate $\Theta(\frac{1}{t\log ^2 n})$. In the prior constructions, the rate was $\Theta(\frac{1}{n\log m})$ where $m$ is the length of the secret and thus, the rate tends to 0 as $m \rightarrow \infty$. Furthermore, we also optimize the parameters of our construction and give a concretely efficient scheme.  Multiple Tampering. We give the first construction of a threshold nonmalleable secret sharing scheme secure in the stronger setting of bounded tampering wherein the shares are tampered by multiple (but bounded in number) possibly different tampering functions. The rate of such a scheme is $\Theta(\frac{1}{k^3t\log^2 n})$ where $k$ is an apriori bound on the number of tamperings. We complement this positive result by proving that it is impossible to have a threshold nonmalleable secret sharing scheme that is secure in the presence of an apriori unbounded number of tamperings.  General Access Structures. We extend our results beyond threshold secret sharing and give constructions of rateefficient, nonmalleable secret sharing schemes for more general monotone access structures that are secure against multiple (bounded) tampering attacks.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2019
 Contact author(s)
 akshayaram @ berkeley edu
 History
 20190819: last of 5 revisions
 20181203: received
 See all versions
 Short URL
 https://ia.cr/2018/1144
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/1144, author = {Saikrishna Badrinarayanan and Akshayaram Srinivasan}, title = {Revisiting NonMalleable Secret Sharing}, howpublished = {Cryptology ePrint Archive, Paper 2018/1144}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/1144}}, url = {https://eprint.iacr.org/2018/1144} }