Document Open Access Logo

Secret Sharing, Slice Formulas, and Monotone Real Circuits

Authors Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.8.pdf
  • Filesize: 0.83 MB
  • 23 pages

Document Identifiers

Author Details

Benny Applebaum
  • Tel-Aviv University, Tel-Aviv, Israel
Amos Beimel
  • Ben-Gurion University, Be'er-Sheva, Israel
Oded Nir
  • Tel-Aviv University, Tel-Aviv, Israel
Naty Peter
  • Tel-Aviv University, Tel-Aviv, Israel
Toniann Pitassi
  • University of Toronto, Toronto, Canada
  • Columbia University, New York, NY, USA

Funding

The first, third and forth authors (BA, ON, NP) are supported by the European Union’s Horizon 2020 Programme (ERC-StG-2014-2020) under Grant Agreement No. 639813 ERC-CLC, and by the Israel Science Foundation grant no. 2805/21. The second author (AB) is supported by ERC grant 742754 (project NTSC), Israel Science Foundation grant no. 391/21, and a grant from the Cyber Security Research Center at Ben-Gurion University. The fifth author (TP) is supported by NSERC, IAS School of Mathematics, and NSF Grant CCF-1900-460.

Acknowledgements

We thank Klim Efremenko for discussions that started this project.

Cite AsGet BibTex

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, and Toniann Pitassi. Secret Sharing, Slice Formulas, and Monotone Real Circuits. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.8

Abstract

A secret-sharing scheme allows to distribute a secret s among n parties such that only some predefined "authorized" sets of parties can reconstruct the secret s, and all other "unauthorized" sets learn nothing about s. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size 2^{n-o(n)} and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to 2^{0.994n+o(n)}, and this was further improved by several follow-ups accumulating in an upper bound of 1.5^{n+o(n)} (Applebaum and Nir, CRYPTO 2021). Following these advances, it is natural to ask whether these new approaches can lead to a truly sub-exponential upper-bound of 2^{n^{1-ε}} for some constant ε > 0, or even all the way down to polynomial upper-bounds. In this paper, we relate this question to the complexity of computing monotone Boolean functions by monotone real circuits (MRCs) - a computational model that was introduced by Pudlák (J. Symb. Log., 1997) in the context of proof complexity. We introduce a new notion of "separable" MRCs that lies between monotone real circuits and monotone real formulas (MRFs). As our main results, we show that recent constructions of general secret-sharing schemes implicitly give rise to separable MRCs for general monotone functions of similar complexity, and that some monotone functions (in monotone NP) cannot be computed by sub-exponential size separable MRCs. Interestingly, it seems that proving similar lower-bounds for general MRCs is beyond the reach of current techniques. We use this connection to obtain lower-bounds against a natural family of secret-sharing schemes, as well as new non-trivial upper-bounds for MRCs. Specifically, we conclude that recent approaches for secret-sharing schemes cannot achieve sub-exponential share size and that every monotone function can be realized by an MRC (or even MRF) of complexity 1.5^{n+o(n)}. To the best of our knowledge, this is the first improvement over the trivial 2^{n-o(n)} upper-bound. Along the way, we show that the recent constructions of general secret-sharing schemes implicitly give rise to Boolean formulas over slice functions and prove that such formulas can be simulated by separable MRCs of similar size. On a conceptual level, our paper continues the rich line of study that relates the share size of secret-sharing schemes to monotone complexity measures.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
  • Theory of computation → Cryptographic primitives
  • Theory of computation → Circuit complexity
Keywords
  • Secret Sharing Schemes
  • Monotone Real Circuits

Metrics

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

References

  1. Benny Applebaum, Amos Beimel, Oriol Farràs, Oded Nir, and Naty Peter. Secret-sharing schemes for general and uniform access structures. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part III, volume 11478 of Lecture Notes in Computer Science, pages 441-471. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-17659-4_15.
  2. Benny Applebaum, Amos Beimel, Oded Nir, and Naty Peter. Better secret sharing via robust conditional disclosure of secrets. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 280-293. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384293.
  3. Benny Applebaum and Oded Nir. Upslices, downslices, and secret-sharing with complexity of 1.5^n. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Part III, volume 12827 of Lecture Notes in Computer Science, pages 627-655. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-84252-9_21.
  4. László Babai, Anna Gál, and Avi Wigderson. Superpolynomial lower bounds for monotone span programs. Comb., 19(3):301-319, 1999. URL: https://doi.org/10.1007/s004930050058.
  5. Amos Beimel. Secret-sharing schemes: A survey. In Yeow Meng Chee, Zhenbo Guo, San Ling, Fengjing Shao, Yuansheng Tang, Huaxiong Wang, and Chaoping Xing, editors, Coding and Cryptology - Third International Workshop, IWCC 2011, volume 6639 of Lecture Notes in Computer Science, pages 11-46. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-20901-7_2.
  6. Amos Beimel and Oriol Farràs. The share size of secret-sharing schemes for almost all access structures and graphs. In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography - 18th International Conference, TCC 2020, volume 12552 of Lecture Notes in Computer Science, pages 499-529. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-64381-2_18.
  7. Amos Beimel, Hussien Othman, and Naty Peter. Quadratic secret sharing and conditional disclosure of secrets. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Part III, volume 12827 of Lecture Notes in Computer Science, pages 748-778. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-84252-9_25.
  8. Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 1-10. ACM, 1988. URL: https://doi.org/10.1145/62212.62213.
  9. Josh Cohen Benaloh and Jerry Leichter. Generalized secret sharing and monotone functions. In Shafi Goldwasser, editor, Advances in Cryptology - CRYPTO '88, 8th Annual International Cryptology Conference, volume 403 of Lecture Notes in Computer Science, pages 27-35. Springer, 1988. URL: https://doi.org/10.1007/0-387-34799-2_3.
  10. Michael Bertilsson and Ingemar Ingemarsson. A construction of practical secret sharing schemes using linear block codes. In Jennifer Seberry and Yuliang Zheng, editors, Advances in Cryptology - AUSCRYPT '92, Workshop on the Theory and Application of Cryptographic Techniques, volume 718 of Lecture Notes in Computer Science, pages 67-79. Springer, 1992. URL: https://doi.org/10.1007/3-540-57220-1_53.
  11. George R. Blakley. Safeguarding cryptographic keys. In Richard E. Merwin, Jacqueline T. Zanca, and Merlin Smith, editors, Proceedings of the 1979 AFIPS National Computer Conference, volume 48 of AFIPS Conference proceedings, pages 313-317. AFIPS Press, 1979. Google Scholar
  12. Maria Luisa Bonet and Samuel R. Buss. Size-depth tradeoffs for Boolean fomulae. Inf. Process. Lett., 49(3):151-155, 1994. Google Scholar
  13. Richard P. Brent. The parallel evaluation of general arithmetic expressions. J. ACM, 21(2):201-206, 1974. Google Scholar
  14. Nader H. Bshouty, Richard Cleve, and Wayne Eberly. Size-depth tradeoffs for algebraic formulas. SIAM J. Comput., 24(4):682-705, 1995. Google Scholar
  15. Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals. Equality alone does not simulate randomness. In Amir Shpilka, editor, 34th Computational Complexity Conference, CCC 2019, volume 137 of LIPIcs, pages 14:1-14:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.14.
  16. David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 11-19. ACM, 1988. URL: https://doi.org/10.1145/62212.62214.
  17. László Csirmaz. The size of a share must be large. In Alfredo De Santis, editor, Advances in Cryptology - EUROCRYPT '94, Workshop on the Theory and Application of Cryptographic Techniques, volume 950 of Lecture Notes in Computer Science, pages 13-22. Springer, 1994. URL: https://doi.org/10.1007/BFb0053420.
  18. László Csirmaz. The dealer’s random bits in perfect secret sharing schemes. Studia Sci. Math. Hungar., 32(3-4):429-437, 1996. Google Scholar
  19. László Csirmaz. Secret sharing and duality. J. Math. Cryptol., 15(1):157-173, 2020. Google Scholar
  20. Yvo Desmedt and Yair Frankel. Shared generation of authenticators and signatures (extended abstract). In Joan Feigenbaum, editor, Advances in Cryptology - CRYPTO '91, 11th Annual International Cryptology Conference, volume 576 of Lecture Notes in Computer Science, pages 457-469. Springer, 1991. URL: https://doi.org/10.1007/3-540-46766-1_37.
  21. Xudong Fu. Lower bounds on sizes of cutting plane proofs for modular coloring principles. In Paul Beam and Samuel R. Buss, editors, Proof Complexity and Feasible Arithmetics, Proceedings of a DIMACS Workshop, volume 39 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 135-148. DIMACS/AMS, 1996. URL: https://doi.org/10.1090/dimacs/039/08.
  22. Anna Gál and Jing-Tang Jang. A generalization of spira’s theorem and circuits with small segregators or separators. Inf. Comput., 251:252-262, 2016. Google Scholar
  23. Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. Theory Comput., 16:1-30, 2020. Google Scholar
  24. Mika Göös and Toniann Pitassi. Communication lower bounds via critical block sensitivity. SIAM J. Comput., 47(5):1778-1806, 2018. URL: https://doi.org/10.1137/16M1082007.
  25. Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters. Attribute-based encryption for fine-grained access control of encrypted data. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, pages 89-98. ACM, 2006. URL: https://doi.org/10.1145/1180405.1180418.
  26. Armin Haken and Stephen A. Cook. An exponential lower bound for the size of monotone real circuits. J. Comput. Syst. Sci., 58(2):326-335, 1999. Google Scholar
  27. Pavel Hrubes and Pavel Pudlák. A note on monotone real circuits. Inf. Process. Lett., 131:15-19, 2018. URL: https://doi.org/10.1016/j.ipl.2017.11.002.
  28. Mitsuru Ito, Akira Saito, and Takao Nishizeki. Secret sharing schemes realizing general access structure. In Globecom 87, pages 99-102. IEEE, 1987. Journal version: Multiple assignment scheme for sharing secret. J. Cryptol., 6(1):15-20, 1993. Google Scholar
  29. Stasys Jukna. Combinatorics of monotone computations. Comb., 19(1):65-85, 1999. Google Scholar
  30. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and combinatorics. Springer-Verlag, 2012. Google Scholar
  31. Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 539-550. ACM, 1988. URL: https://doi.org/10.1145/62212.62265.
  32. Mauricio Karchmer and Avi Wigderson. On span programs. In Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 102-111. IEEE Computer Society, 1993. URL: https://doi.org/10.1109/SCT.1993.336536.
  33. Jan Krajícek. Interpolation by a game. Math. Log. Q., 44:450-458, 1998. URL: https://doi.org/10.1002/malq.19980440403.
  34. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1996. Google Scholar
  35. Tianren Liu and Vinod Vaikuntanathan. Breaking the circuit-size barrier in secret sharing. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 699-708. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188936.
  36. Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee. Towards breaking the exponential barrier for general secret sharing. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part I, volume 10820 of Lecture Notes in Computer Science, pages 567-596. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-78381-9_21.
  37. Moni Naor and Avishai Wool. Access control and signatures via quorum secret sharing. In Li Gong and Jacques Stearn, editors, CCS '96, Proceedings of the 3rd ACM Conference on Computer and Communications Security, New Delhi, India, March 14-16, 1996, pages 157-168. ACM, 1996. URL: https://doi.org/10.1145/238168.238209.
  38. Noam Nisan. The communication complexity of threshold gates. In Combinatorics, Paul Erdos is Eighty, in Bolyai Society Mathematical Studies, pages 301-315, 1993. Google Scholar
  39. Toniann Pitassi and Robert Robere. Lifting nullstellensatz to monotone span programs over any field. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1207-1219. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188914.
  40. Pavel Pudlák. Lower bounds for resolution and cutting plane proofs and monotone computations. J. Symb. Log., 62(3):981-998, 1997. URL: https://doi.org/10.2307/2275583.
  41. Alexander A. Razborov. A lower bound on the monotone network complexity of the logical permanent. Math. Notes of the Acad. of Sci. of the USSR, 37(6):485-493, 1985. Google Scholar
  42. John Riordan and Claude E. Shannon. The number of two-terminal series-parallel networks. J. Math. Phys., 21(1-4):83-93, 1942. URL: https://doi.org/10.1002/sapm194221183.
  43. Arnold Rosenbloom. Monotone real circuits are more powerful than monotone Boolean circuits. Inf. Process. Lett., 61(3):161-164, 1997. URL: https://doi.org/10.1016/S0020-0190(97)00007-0.
  44. John E. Savage. The Complexity of Computing. John Wiley & Sons Inc., 1976. Google Scholar
  45. Adi Shamir. How to share a secret. Communications of the ACM, 22:612-613, 1979. Google Scholar
  46. Bhavani Shankar, Kannan Srinathan, and C. Pandu Rangan. Alternative protocols for generalized oblivious transfer. In Shrisha Rao, Mainak Chatterjee, Prasad Jayanti, C. Siva Ram Murthy, and Sanjoy Kumar Saha, editors, Distributed Computing and Networking, 9th International Conference, ICDCN 2008, volume 4904 of Lecture Notes in Computer Science, pages 304-309. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-77444-0_31.
  47. Philip M. Spira. On time-hardware complexity tradeoffs for Boolean functions. In Proceedings of the 4th Hawaii Symposium on System Sciences, 1971, pages 525-527, 1971. Google Scholar
  48. Ulfberg Stafan. On Lower Bounds for Circuits and Selection. Ph.D., Royal Institute of Technology, Stockholm, Sweden, 1999. Google Scholar
  49. Tamir Tassa. Generalized oblivious transfer by secret sharing. Des. Codes Cryptogr., 58(1):11-21, 2011. URL: https://doi.org/10.1007/s10623-010-9378-8.
  50. Leslie G. Valiant, Sven Skyum, Stuart Berkowitz, and Charles Rackoff. Fast parallel computation of polynomials using few processors. SIAM J. Comput., 12(4):641-644, 1983. Google Scholar
  51. Emanuele Viola. The communication complexity of addition. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pages 632-651. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.46.
  52. Brent Waters. Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization. In Dario Catalano, Nelly Fazio, Rosario Gennaro, and Antonio Nicolosi, editors, Public Key Cryptography - PKC 2011 - 14th International Conference on Practice and Theory in Public Key Cryptography, volume 6571 of Lecture Notes in Computer Science, pages 53-70. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-19379-8_4.
  53. Ingo Wegener. Relating monotone formula size and monotone depth of Boolean functions. Inf. Process. Lett., 16(1):41-42, 1983. 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 Imprint Privacy Contact