CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20161011-150403696

[img] PDF - Accepted Version
See Usage Policy.

371Kb

Use this Persistent URL to link to this item: http://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:
URLURL TypeDescription
http://dx.doi.org/10.1109/TIT.2016.2616144DOIArticle
http://ieeexplore.ieee.org/document/7587343/PublisherArticle
http://resolver.caltech.edu/CaltechAUTHORS:20150529-105023455Related ItemTechnical Report
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:
Funding AgencyGrant Number
NSFCCF-1218005
NSFCCF-1321129
NSFCCF-1526771
NSFCNS-152654
Binational Science Foundation (USA-Israel)2010075
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:Security, secret sharing, communication bandwidth, distributed storage, Reed-Solomon codes
Record Number:CaltechAUTHORS:20161011-150403696
Persistent URL:http://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:05 Jan 2018 17:45

Repository Staff Only: item control page