Prof. Amos Beimel

All known constructions of information theoretic t-out-of-n secret sharing schemes require secure, private communication channels among the parties for the reconstruction of the secret. In this work we investigate the cost of performing the reconstruction over public communication channels. A naive implementation of this task distributes O(n) one times pads to each party. This results in shares whose size is O(n) times the secret size. We present three implementations of such schemes that are substantially more efficient: A scheme enabling multiple reconstructions of the secret by different subsets of parties, with factor O(n/t) increase in the shares’ size. A one-time scheme, enabling a single reconstruction of the secret, with O(log(n/t)) increase in the shares’ size. A one-time scheme, enabling a single reconstruction by a set of size exactly t, with factor O(1) increase in the shares’ size. We prove that the first implementation is optimal (up to constant factors) by showing a tight Ω(n/t) lower bound for the increase in the shares’ size.