Document Open Access Logo

Linear Threshold Secret-Sharing with Binary Reconstruction

Authors Marshall Ball, Alper Çakan, Tal Malkin

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.12.pdf
  • Filesize: 0.77 MB
  • 22 pages

Document Identifiers

Author Details

Marshall Ball
  • University of Washington, Seattle, WA, USA
Alper Çakan
  • Bogazici University, Istanbul, Turkey
Tal Malkin
  • Columbia University, New York, NY, USA

Funding

  • Ball, Marshall: This material is based upon work partly supported by the National Science Foundation under Grant #2030859 to the Computing Research Association for the CIFellows Project, a grant from the Columbia-IBM center for Blockchain and Data Transparency, and by JP Morgan Chase & Co. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of JPMorgan Chase & Co. or its affiliates, the National Science Foundation, or the Computing Research Association.
  • Çakan, Alper: Part of this work was performed while this author was visiting Columbia University in NY, USA.
  • Malkin, Tal: This research was supported in part by a grant from the Columbia-IBM center for Blockchain and Data Transparency, and by JPMorgan Chase & Co. Any views or opinions expressed herein are solely those of the authors, and may differ from the views and opinions expressed by JPMorgan Chase & Co. or its affiliates.

Acknowledgements

We are grateful to Hoeteck Wee who proposed the problem to us, and provided many useful comments and suggestions towards solving it. We also thank anonymous referees for helpful comments.

Cite As Get BibTex

Marshall Ball, Alper Çakan, and Tal Malkin. Linear Threshold Secret-Sharing with Binary Reconstruction. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITC.2021.12

Abstract

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 Ω(nlog 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Secret sharing
  • Span programs
  • Lattice-based cryptography

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Shweta Agrawal, Xavier Boyen, Vinod Vaikuntanathan, Panagiotis Voulgaris, and Hoeteck Wee. Functional encryption for threshold functions (or fuzzy IBE) from lattices. In Public Key Cryptography, volume 7293 of Lecture Notes in Computer Science, pages 280-297. Springer, 2012. Google Scholar
  2. Rudolf Ahlswede and Levon H. Khachatrian. The complete intersection theorem for systems of finite sets. European Journal of Combinatorics, 18(2):125-136, 1997. URL: http://www.sciencedirect.com/science/article/pii/S0195669885700923.
  3. Miklós Ajtai, János Komlós, and Endre Szemerédi. Sorting in c log n parallel sets. Comb., 3(1):1-19, 1983. Google Scholar
  4. Amos Beimel. Secure schemes for secret sharing and key distribution, 1996. Google Scholar
  5. Amos Beimel. Secret-sharing schemes: A survey. In IWCC, volume 6639 of Lecture Notes in Computer Science, pages 11-46. Springer, 2011. Google Scholar
  6. Josh Cohen Benaloh and Jerry Leichter. Generalized secret sharing and monotone functions. In CRYPTO, volume 403 of Lecture Notes in Computer Science, pages 27-35. Springer, 1988. Google Scholar
  7. George Robert Blakley. Safeguarding cryptographic keys. In 1979 International Workshop on Managing Requirements Knowledge (MARK), pages 313-318. IEEE, 1979. Google Scholar
  8. Andrej Bogdanov, Siyao Guo, and Ilan Komargodski. Threshold secret sharing requires a linear size alphabet. In Theory of Cryptography Conference, pages 471-484. Springer, 2016. Google Scholar
  9. Dan Boneh, Rosario Gennaro, Steven Goldfeder, Aayush Jain, Sam Kim, Peter M. R. Rasmussen, and Amit Sahai. Threshold cryptosystems from threshold fully homomorphic encryption. In CRYPTO (1), volume 10991 of Lecture Notes in Computer Science, pages 565-596. Springer, 2018. Google Scholar
  10. Ravi B. Boppana. Amplification of probabilistic boolean formulas. Adv. Comput. Res., 5:27-45, 1989. Google Scholar
  11. Xavier Boyen. Attribute-based functional encryption on lattices. In TCC, volume 7785 of Lecture Notes in Computer Science, pages 122-142. Springer, 2013. Google Scholar
  12. Ronald Cramer and Serge Fehr. Optimal black-box secret sharing over arbitrary abelian groups. In Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’02, page 272–287, Berlin, Heidelberg, 2002. Springer-Verlag. Google Scholar
  13. J. Friedman. Constructing o(n log n) size monotone formulae for the k-th elementary symmetric polynomial of n boolean variables. In 25th Annual Symposium onFoundations of Computer Science, 1984., pages 506-515, 1984. Google Scholar
  14. Anna Gal. A characterization of span program size and improved lower bounds for monotone span programs. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC '98, page 429–437, New York, NY, USA, 1998. Association for Computing Machinery. URL: https://doi.org/10.1145/276698.276855.
  15. Christopher Godsil and Karen Meagher. Erdős–Ko–Rado Theorems: Algebraic Approaches. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2015. Google Scholar
  16. Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Attribute-based encryption for circuits. In STOC, pages 545-554. ACM, 2013. Google Scholar
  17. M. M. Halldorsson, J. Radhakrishnan, and K. V. Subrahmanyam. Directed vs. undirected monotone contact networks for threshold functions. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 604-613, 1993. Google Scholar
  18. Kenneth Hoffman and Ray A. Kunze. Linear Algebra. PHI Learning, second edition, 2004. URL: http://www.worldcat.org/isbn/8120302702.
  19. Shlomo Hoory, Avner Magen, and Toniann Pitassi. Monotone circuits for the majority function. In APPROX-RANDOM, volume 4110 of Lecture Notes in Computer Science, pages 410-425. Springer, 2006. Google Scholar
  20. M. Karchmer and A. Wigderson. On span programs. In [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 102-111, 1993. Google Scholar
  21. Gyula O.H. Katona. Around the complete intersection theorem. Discrete Applied Mathematics, 216:618-621, 2017. Levon Khachatrian’s Legacy in Extremal Combinatorics. URL: http://www.sciencedirect.com/science/article/pii/S0166218X1600010X.
  22. Mike Paterson. Improved sorting networks with o(log N) depth. Algorithmica, 5(1):65-92, 1990. Google Scholar
  23. Adi Shamir. How to share a secret. Commun. ACM, 22(11):612-613, 1979. Google Scholar
  24. Leslie G. Valiant. Short monotone formulae for the majority function. J. Algorithms, 5(3):363-366, 1984. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact