A Caltech Library Service

Communication Efficient Secret Sharing

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.

[img] PDF - Accepted Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription Paper ItemTechnical Report
Huang, Wentao0000-0003-0963-3624
Langberg, Michael0000-0002-7470-0718
Bruck, Jehoshua0000-0001-8474-0812
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.
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2010075
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:Security, secret sharing, communication bandwidth, distributed storage, Reed-Solomon codes
Issue or Number:12
Record Number:CaltechAUTHORS:20161011-150403696
Persistent URL:
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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71002
Deposited By: Kristin Buxton
Deposited On:12 Oct 2016 16:34
Last Modified:11 Nov 2021 04:38

Repository Staff Only: item control page