CaltechAUTHORS
  A Caltech Library Service

Communication Efficient Secret Sharing

Huang, Wentao and Langberg, Michael and Kliewer, Joerg and Bruck, Jehoshua (2015) Communication Efficient Secret Sharing. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20150529-105023455

[img] PDF - Submitted Version
See Usage Policy.

604Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20150529-105023455

Abstract

A secret sharing scheme is a method to store information securely and reliably. Particularly, in the threshold secret sharing scheme (due to Shamir), a secret is divided into shares, encoded and distributed to parties, such that any large enough collection of parties can decode the secret, and a smaller (then threshold) set of parties cannot collude to deduce any information about the secret. While Shamir’s scheme was studied for more than 35 years, the question of minimizing its communication bandwidth was not considered. Specifically, assume that a user (or a collection of parties) wishes to decode the secret by receiving information from a set of parties; the question we study is how to minimize the total amount of communication between the user and the parties. We prove a tight lower bound on the amount of communication necessary for decoding, and construct secret sharing schemes achieving the bound. The key idea for achieving optimal communication bandwidth is to let the user receive information from more than the necessary number of parties. In contrast, the current paradigm in secret sharing schemes is to decode from a minimum set of parties. Hence, existing secret sharing schemes are not optimal in terms of communication bandwidth. In addition, we consider secure distributed storage where our proposed communication efficient secret sharing schemes improve disk access complexity during decoding.


Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr130.pdfAuthorReport
http://arxiv.org/abs/1505.07515arXivDiscussion Paper
http://dx.doi.org/10.1109/TIT.2016.2616144DOIJournal Article
Group:Parallel and Distributed Systems Group
Other Numbering System:
Other Numbering System NameOther Numbering System ID
ParadiseETR130
Record Number:CaltechAUTHORS:20150529-105023455
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20150529-105023455
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:57900
Collection:CaltechPARADISE
Deposited By: Kristin Buxton
Deposited On:29 May 2015 18:28
Last Modified:12 Oct 2016 16:33

Repository Staff Only: item control page