Linear threshold secret-sharing with binary reconstruction

Marshall Ball, Alper Çakan, Tal Malkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 also study the complexity of 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. We prove upper and lower bounds on the share size of such schemes, where the size is measured by the total number of field elements distributed to the parties. We prove our results by defining and investigating an equivalent variant of Karchmer and Wigderson's Monotone Span Programs [CCC, 1993]. 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 monotone formulae are optimal for certain threshold values when the field's characteristic is any constant. For schemes with the uniform distribution requirement, we show that they must use Ω(n log n) field elements, for all thresholds 2 < t < n and regardless of the field. Moreover, 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.

Original languageEnglish (US)
Title of host publication2nd Conference on Information-Theoretic Cryptography, ITC 2021
EditorsStefano Tessaro
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771979
StatePublished - Jul 1 2021
Event2nd Conference on Information-Theoretic Cryptography, ITC 2021 - Virtual, Bertinoro, Italy
Duration: Jul 23 2021Jul 26 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference2nd Conference on Information-Theoretic Cryptography, ITC 2021
CityVirtual, Bertinoro


  • Lattice-based cryptography
  • Secret sharing
  • Span programs

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Linear threshold secret-sharing with binary reconstruction'. Together they form a unique fingerprint.

Cite this