Huang, Wentao and Langberg, Michael and Kliewer, Joerg and Bruck, Jehoshua (2016) Communication Efficient Secret Sharing. IEEE Transactions on Information Theory, 62 (12). pp. 7195-7206. ISSN 0018-9448. doi:10.1109/TIT.2016.2616144. https://resolver.caltech.edu/CaltechAUTHORS:20161011-150403696
![]() |
PDF
- Accepted Version
See Usage Policy. 380kB |
![]() |
PDF
- Submitted Version
See Usage Policy. 401kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161011-150403696
Abstract
A secret sharing scheme is a method to store information securely and reliably. Particularly, in a threshold secret sharing scheme, a secret is encoded into n shares, such that any set of at least t_1 shares suffice to decode the secret, and any set of at most t_2 < t_1 shares reveal no information about the secret. Assuming that each party holds a share and a user wishes to decode the secret by receiving information from a set of parties; the question we study is how to minimize the amount of communication between the user and the parties. We show that the necessary amount of communication, termed “decoding bandwidth”, decreases as the number of parties that participate in decoding increases. We prove a tight lower bound on the decoding bandwidth, and construct secret sharing schemes achieving the bound. Particularly, we design a scheme that achieves the optimal decoding bandwidth when d parties participate in decoding, universally for all t_1 ≤ d ≤ n. The scheme is based on a generalization of Shamir’s secret sharing scheme and preserves its simplicity and efficiency. In addition, we consider the setting of secure distributed storage where the proposed communication efficient secret sharing schemes not only improve decoding bandwidth but further improve disk access complexity during decoding.
Item Type: | Article | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||||
ORCID: |
| ||||||||||||||
Additional Information: | © 2016 IEEE. We thank an anonymous reviewer for pointing us to the paper by Wang and Wong [23]. This work has been supported in part by NSF grant CCF-1218005, CCF-1321129, CCF-1526771, CNS-152654, United States - Israel Binational Science Foundation (BSF) grant 2010075, and the Caltech Lee Center. | ||||||||||||||
Funders: |
| ||||||||||||||
Subject Keywords: | Security, secret sharing, communication bandwidth, distributed storage, Reed-Solomon codes | ||||||||||||||
Issue or Number: | 12 | ||||||||||||||
DOI: | 10.1109/TIT.2016.2616144 | ||||||||||||||
Record Number: | CaltechAUTHORS:20161011-150403696 | ||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20161011-150403696 | ||||||||||||||
Official Citation: | W. Huang, M. Langberg, J. Kliewer and J. Bruck, "Communication Efficient Secret Sharing," in IEEE Transactions on Information Theory, vol. 62, no. 12, pp. 7195-7206, Dec. 2016. doi: 10.1109/TIT.2016.2616144 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7587343&isnumber=7748579 | ||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||
ID Code: | 71002 | ||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||
Deposited By: | Kristin Buxton | ||||||||||||||
Deposited On: | 12 Oct 2016 16:34 | ||||||||||||||
Last Modified: | 11 Nov 2021 04:38 |
Repository Staff Only: item control page