Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-050 | 2nd April 2021 16:13

Linear Threshold Secret-Sharing with Binary Reconstruction


Authors: Marshall Ball, Alper Cakan, Tal Malkin
Publication: 4th April 2021 09:36
Downloads: 120


Motivated in part by applications in lattice-based cryptography, we initiate the study of the size of linear threshold (`$t$-out-of-$n$') secret-sharing where the linear reconstruction function is restricted to coefficients in $\{0,1\}$. We prove upper and lower bounds on the share size of such schemes. One ramification of our results is that a natural variant of Shamir's classic scheme [Comm. of ACM, 1979], where bit-decomposition is applied to each share, is optimal for when the underlying field has characteristic 2. Another ramification is that schemes obtained from some monotone formulae are optimal for certain threshold values when the field's characteristic is any constant. We prove our results by defining and investigating an equivalent variant of Karchmer and Wigderson's Monotone Span Programs [CCC, 1993].

We also study the complexity such schemes with the additional requirement that the joint distribution of the shares of any unauthorized set of parties is not only independent of the secret, but also uniformly distributed. This property is critical for security of certain applications in lattice-based cryptography. We show that any such scheme must use $\Omega(n\log n)$ field elements, regardless of the field. Moreover, for any field this is tight up to constant factors for the special cases where any $t=n-1$ parties can reconstruct, as well as for any threshold when the field characteristic is 2.

ISSN 1433-8092 | Imprint