Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 29, 2015 | Submitted
Report Open

Communication Efficient Secret Sharing

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.

Attached Files

Submitted - etr130.pdf

Files

etr130.pdf
Files (619.4 kB)
Name Size Download all
md5:376c55cfa7c5a3c21fc1fd25aacea1d0
619.4 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 23, 2023