Communication Efficient Secret Sharing

By Wentao Huang, Michael Langberg, Jörg Kliewer, Jehoshua Bruck. 2015

69 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Staircase-PIR: Universally Robust Private Information Retrieval (2018, methodology): “When accessing d servers, the user needs only to download the optimal rate d(k− t)/(d− t) units of information given in [35], [36].”
Staircase codes for secret sharing with optimal communication and read overheads (2015, background): “We consider the CESS problem and follow the majority of the notations in [12].”
Centralized Repair of Multiple Node Failures With Applications to Communication Efficient Secret Sharing (2016, methodology): “efficient secret sharing schemes that can achieve the bound provided in [16] for all parameter regimes.”
Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes (2018, methodology): “The information theoretic lower bound on the amount of information downloaded from each worker is referred to as communication cost CC(d) and is given [15] by CC(d) = k − z d− z .”