TY - JOUR
T1 - Communication efficient secret sharing
AU - Huang, Wentao
AU - Langberg, Michael
AU - Kliewer, Jorg
AU - Bruck, Jehoshua
N1 - Funding Information:
This work was supported in part by NSF under Grant CCF-1218005, Grant CCF-1321129, Grant CCF-1526771, and Grant CNS-152654, in part by the United States-Israel Binational Science Foundation under Grant 2010075, and in part by the Caltech Lee Center.
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2016/12
Y1 - 2016/12
N2 - 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 t1 shares suffice to decode the secret, and any set of at most t2 < t1 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 t1 ≤ 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.
AB - 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 t1 shares suffice to decode the secret, and any set of at most t2 < t1 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 t1 ≤ 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.
KW - Reed-Solomon codes
KW - Security
KW - communication bandwidth
KW - distributed storage
KW - secret sharing
UR - http://www.scopus.com/inward/record.url?scp=84999106904&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84999106904&partnerID=8YFLogxK
U2 - 10.1109/TIT.2016.2616144
DO - 10.1109/TIT.2016.2616144
M3 - Article
AN - SCOPUS:84999106904
SN - 0018-9448
VL - 62
SP - 7195
EP - 7206
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 12
M1 - 7587343
ER -