Threshold Secret Sharing Requires a Linear-Size Alphabet

by Andrej Bogdanov, Siyao Guo, and Ilan Komargodski

Theory of Computing, Volume 16(2), pp. 1-18, 2020

Bibliography with links to cited articles

[1]   László Babai, Anna Gál, and Avi Wigderson: Superpolynomial lower bounds for monotone span programs. Combinatorica, 19(3):301–319, 1999. [doi:10.1007/s004930050058]

[2]   Amos Beimel: Secure Schemes for Secret Sharing and Key Distribution. Ph. D. thesis, Technion – Israel Institute of Technology, 1996. Accessible in PS on the author’s home page and in PDF at

[3]   Amos Beimel: Secret-sharing schemes: A survey. In Coding and Cryptology – 3rd Internat. Workshop, IWCC’11, volume 6639, pp. 11–46. Springer, 2011. [doi:10.1007/978-3-642-20901-7_2]

[4]   Amos Beimel and Benny Chor: Universally ideal secret-sharing schemes. IEEE Trans. Inform. Theory, 40(3):786–794, 1994. Preliminary version in CRYPTO’92. [doi:10.1109/18.335890]

[5]   Amos Beimel and Matthew K. Franklin: Weakly-private secret sharing schemes. In 4th Theory of Cryptography Conf., TCC’07, volume 4392, pp. 253–272, 2007. [doi:10.1007/978-3-540-70936-7_14]

[6]   Amos Beimel, Anna Gál, and Mike Paterson: Lower bounds for monotone span programs. Comput. Complexity, 6(1):29–45, 1996. Preliminary version in FOCS’95. [doi:10.1007/BF01202040]

[7]   Amos Beimel and Yuval Ishai: On the power of nonlinear secrect-sharing. In Proc. 16th IEEE Conf. on Computational Complexity (CCC’01), pp. 188–202. IEEE Comp. Soc., 2001. [doi:10.1109/CCC.2001.933886]

[8]   Amos Beimel and Ilan Orlov: Secret sharing and non-Shannon information inequalities. IEEE Trans. Inform. Theory, 57(9):5634–5649, 2011. Preliminary version in TCC’09. [doi:10.1109/TIT.2011.2162183]

[9]   Amos Beimel and Enav Weinreb: Separating the power of monotone span programs over different fields. SIAM J. Comput., 34(5):1196–1215, 2005. Preliminary version in FOCS’03. [doi:10.1137/S0097539704444038]

[10]   Josh Cohen Benaloh and Jerry Leichter: Generalized secret sharing and monotone functions. In Proc. of 8th Internat. Cryptology Conf. (CRYPTO’88), pp. 27–35. Springer, 1988. [doi:10.1007/0-387-34799-2_3]

[11]   George Robert Blakley: Safeguarding cryptographic keys. In Proc. AFIPS Nat. Computer Conf., volume 1, pp. 313–317. IEEE Comp. Soc., 1979. [doi:10.1109/AFIPS.1979.98]

[12]   George Robert Blakley and Catherine A. Meadows: Security of ramp schemes. In Proc. of 4th Internat. Cryptology Conf. (CRYPTO’84), pp. 242–268. Springer, 1984. [doi:10.1007/3-540-39568-7_20]

[13]   Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson: Bounded indistinguishability and the complexity of recovering secrets. In Proc. of 36th Internat. Cryptology Conf. (CRYPTO’16), pp. 593–618. Springer, 2016. [doi:10.1007/978-3-662-53015-3_21]

[14]   Renato M. Capocelli, Alfredo De Santis, Luisa Gargano, and Ugo Vaccaro: On the size of shares for secret sharing schemes. J. Cryptology, 6(3):157–167, 1993. Preliminary version in CRYPTO’91. [doi:10.1007/BF00198463]

[15]   Ignacio Cascudo Pueyo, Ronald Cramer, and Chaoping Xing: Bounds on the threshold gap in secret sharing and its applications. IEEE Trans. Inform. Theory, 59(9):5600–5612, 2013. [doi:10.1109/TIT.2013.2264504]

[16]   Hao Chen and Ronald Cramer: Algebraic geometric secret sharing schemes and secure multi-party computations over small fields. In Proc. of 26th Internat. Cryptology Conf. (CRYPTO’06), pp. 521–536. Springer, 2006. [doi:10.1007/11818175_31]

[17]   Ronald Cramer, Ivan Bjerre Damgård, and Jesper Buus Nielsen: Secure Multiparty Computation and Secret Sharing. Cambridge Univ. Press, 2015. [doi:10.1017/CBO9781107337756]

[18]   Ronald Cramer and Serge Fehr: Optimal black-box secret sharing over arbitrary Abelian groups. In Proc. 22nd Internat. Cryptology Conf. (CRYPTO’02), pp. 272–287. Springer, 2002. [doi:10.1007/3-540-45708-9_18]

[19]   László Csirmaz: The dealer’s random bits in perfect secret sharing schemes. Studia Scientiarum Mathematicarum Hungarica, 32(3–4):429–438, 1996. Available at Rényi Institute.

[20]   László Csirmaz: The size of a share must be large. J. Cryptology, 10(4):223–231, 1997. Preliminary version in EUROCRYPT’94. [doi:10.1007/s001459900029]

[21]   László Csirmaz and Gábor Tardos: Optimal information rate of secret sharing schemes on trees. IEEE Trans. Inform. Theory, 59(4):2527–2530, 2013. [doi:10.1109/TIT.2012.2236958]

[22]   Oriol Farràs, Torben Brandt Hansen, Tarik Kaced, and Carles Padró: Optimal non-perfect uniform secret sharing schemes. In Proc. of 34th Internat. Cryptology Conf. (CRYPTO’14), pp. 217–234. Springer, 2014. [doi:10.1007/978-3-662-44381-1_13]

[23]   Oriol Farràs, Sebastià Martín Molleví, and Carles Padró: A note on non-perfect secret sharing. IACR Cryptology ePrint Archive, Report 2016/348, 2016.

[24]   Matthew K. Franklin and Moti Yung: Communication complexity of secure computation (extended abstract). In Proc. 24th STOC, pp. 699–710. ACM Press, 1992. [doi:10.1145/129712.129780]

[25]   Anna Gál: A characterization of span program size and improved lower bounds for monotone span programs. Comput. Complexity, 10(4):277–296, 2001. Preliminary version in STOC’98. [doi:10.1007/s000370100001]

[26]   Mitsuru Ito, Akira Saito, and Takao Nishizeki: Multiple assignment scheme for sharing secret. J. Cryptology, 6(1):15–20, 1993. [doi:10.1007/BF02620229]

[27]   Mauricio Karchmer and Avi Wigderson: On span programs. In Proc. 8th Structure in Complexity Theory Conf. (SCT’93), pp. 102–111. IEEE Comp. Soc., 1993. [doi:10.1109/SCT.1993.336536]

[28]   Joe Kilian and Noam Nisan: Unpublished. Referenced in [42515], 1990.

[29]   Ilan Komargodski, Moni Naor, and Eylon Yogev: How to share a secret, infinitely. IEEE Trans. Inform. Theory, 64(6):4179–4190, 2018. Preliminary version in TCC’16. [doi:10.1109/TIT.2017.2779121]

[30]   Tianren Liu and Vinod Vaikuntanathan: Breaking the circuit-size barrier in secret sharing. In Proc. 50th STOC, pp. 699–708. ACM Press, 2018. [doi:10.1145/3188745.3188936]

[31]   Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee: Conditional disclosure of secrets via non-linear reconstruction. In Proc. of 37th Internat. Cryptology Conf. (CRYPTO’17), pp. 758–790, 2017. [doi:10.1007/978-3-319-63688-7_25]

[32]   Keith M. Martin, Maura B. Paterson, and Douglas R. Stinson: Error decodable secret sharing and one-round perfectly secure message transmission for general adversary structures. Cryptography and Communications, 3(2):65–86, 2011. [doi:10.1007/s12095-010-0039-6]

[33]   Sebastià Martín Molleví, Carles Padró, and An Yang: Secret sharing, rank inequalities, and information inequalities. IEEE Trans. Inform. Theory, 62(1):599–609, 2016. Preliminary version in CRYPTO’13. [doi:10.1109/TIT.2015.2500232]

[34]   Maura B. Paterson and Douglas R. Stinson: A simple combinatorial treatment of constructions and threshold gaps of ramp schemes. Cryptography and Communications, 5(4):229–240, 2013. [doi:10.1007/s12095-013-0082-1]

[35]   Toniann Pitassi and Robert Robere: Lifting Nullstellensatz to monotone span programs over any field. In Proc. 50th STOC, pp. 1207–1219. ACM Press, 2018. [doi:10.1145/3188745.3188914, ECCC:TR17-165]

[36]   Adi Shamir: How to share a secret. Comm. ACM, 22(11):612–613, 1979. [doi:10.1145/359168.359176]

[37]   Douglas R. Stinson and Ruizhong Wei: An application of ramp schemes to broadcast encryption. Info. Processing Lett., 69(3):131–135, 1999. [doi:10.1016/S0020-0190(98)00204-X]

[38]   Vinod Vaikuntanathan and Prashant Nalini Vasudevan: Secret sharing and statistical zero knowledge. In Proc. 21st Internat. Conf. on Theory and Appl. of Cryptology and Inform. Security (ASIACRYPT’15), pp. 656–680. Springer, 2015. [doi:10.1007/978-3-662-48797-6_27]