Communication efficient secret sharing

Wentao Huang, Michael Langberg, Jorg Kliewer, Jehoshua Bruck

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

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 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.

Original languageEnglish (US)
Article number7587343
Pages (from-to)7195-7206
Number of pages12
JournalIEEE Transactions on Information Theory
Volume62
Issue number12
DOIs
StatePublished - Dec 2016

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Reed-Solomon codes
  • Security
  • communication bandwidth
  • distributed storage
  • secret sharing

Fingerprint

Dive into the research topics of 'Communication efficient secret sharing'. Together they form a unique fingerprint.

Cite this