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)

[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 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 Paper Article
Huang, Wentao0000-0003-0963-3624
Langberg, Michael0000-0002-7470-0718
Bruck, Jehoshua0000-0001-8474-0812
Group:Parallel and Distributed Systems Group
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Record Number:CaltechAUTHORS:20150529-105023455
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:57900
Deposited On:29 May 2015 18:28
Last Modified:10 Nov 2021 21:56

Repository Staff Only: item control page