SECRET SHARING WITH PUBLIC RECONSTRUCTION

All known constructions of information theoretic t-out-of-n secret-sha ring schemes require secure, private communication channels among the parties for the reconstruction of the secret. In this work we investig ate the cost of performing the reconstruction over public communicatio n channels. A naive implementation of this task distributes 2n - 2 one times pads to each party, This results in shares whose size is 2n - 1 times the secret size, We present three implementations of such schem es that are substantially more efficient. A scheme enabling multiple r econstructions of the secret by different subsets of parties, with fac tor 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 t he shares' size. A one-time scheme, enabling a single reconstruction b y a set of size exactly t, with factor O (1) increase in the shares' s ize. We prove that the first implementation is optimal (up to constant factors) by showing a tight Omega(n/t) lower bound for the increase i n the shares' size.