LIPIcs.ITC.2023.3.pdf
- Filesize: 0.55 MB
- 6 pages
Document
Csirmaz’s Duality Conjecture and Threshold Secret Sharing
Author
Andrej Bogdanov 
-
Part of:
Volume:
4th Conference on Information-Theoretic Cryptography (ITC 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Conference on Information-Theoretic Cryptography (ITC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-07-21
File
Document Identifiers
Author Details
Acknowledgements
Part of the research was carried out while the author was with the Chinese University of Hong Kong. I thank the anonymous ITC 2023 reviewers for helpful suggestions.
Cite As Get BibTex
Andrej Bogdanov. Csirmaz’s Duality Conjecture and Threshold Secret Sharing. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 3:1-3:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITC.2023.3
Abstract
We conjecture that the smallest possible share size for binary secrets for the t-out-of-n and (n-t+1)-out-of-n access structures is the same for all 1 ≤ t ≤ n. This is a strenghtening of a recent conjecture by Csirmaz (J. Math. Cryptol., 2020). We prove the conjecture for t = 2 and all n. Our proof gives a new (n-1)-out-of-n secret sharing scheme for binary secrets with share alphabet size n.
Subject Classification
ACM Subject Classification
- Theory of computation → Randomness, geometry and discrete structures
- Theory of computation → Cryptographic primitives
- Mathematics of computing → Information theory
- Security and privacy → Mathematical foundations of cryptography
Keywords
- Threshold secret sharing
- Fourier analysis
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
G.R. Blakley. Safeguarding cryptographic keys. In Proceedings of the 1979 AFIPS National Computer Conference, pages 313-317, Monval, NJ, USA, 1979. AFIPS Press.
- Andrej Bogdanov, Siyao Guo, and Ilan Komargodski. Threshold secret sharing requires a linear-size alphabet. Theory of Computing, 16(2):1-18, 2020. URL: https://doi.org/10.4086/toc.2020.v016a002.
- Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen. Secure Multiparty Computation and Secret Sharing. Cambridge University Press, 2015. URL: http://www.cambridge.org/de/academic/subjects/computer-science/cryptography-cryptology-and-coding/secure-multiparty-computation-and-secret-sharing?format=HB&isbn=9781107043053.
- László Csirmaz. Secret sharing and duality. J. Math. Cryptol., 15(1):157-173, 2020. URL: https://doi.org/10.1515/jmc-2019-0045.
-
Satyanarayana V. Lokam. Complexity Lower Bounds Using Linear Algebra. Now Publishers Inc., Hanover, MA, USA, 2009.
- Ron Roth. Introduction to Coding Theory. Cambridge University Press, 2006. URL: https://doi.org/10.1017/CBO9780511808968.
- Adi Shamir. How to share a secret. Commun. ACM, 22(11):612-613, November 1979. URL: https://doi.org/10.1145/359168.359176.