{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:07Z","timestamp":1759638187213,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540858546"},{"type":"electronic","value":"9783540858553"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-85855-3_12","type":"book-chapter","created":{"date-parts":[[2008,8,28]],"date-time":"2008-08-28T13:27:52Z","timestamp":1219930072000},"page":"172-184","source":"Crossref","is-referenced-by-count":2,"title":["On Linear Secret Sharing for Connectivity in Directed Graphs"],"prefix":"10.1007","author":[{"given":"Amos","family":"Beimel","sequence":"first","affiliation":[]},{"given":"Anat","family":"Paskin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Fagin, R.: Reachability is harder for directed than for undirected finite graphs. J. Symb. Log.\u00a055(1) (1990)","DOI":"10.2307\/2274958"},{"issue":"3","key":"12_CR2","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s004930050058","volume":"19","author":"L. Babai","year":"1999","unstructured":"Babai, L., G\u00e1l, A., Wigderson, A.: Superpolynomial lower bounds for monotone span programs. Combinatorica\u00a019(3), 301\u2013319 (1999)","journal-title":"Combinatorica"},{"key":"12_CR3","unstructured":"Beimel, A.: Secure Schemes for Secret Sharing and Key Distribution. PhD thesis, Technion (1996), www.cs.bgu.ac.il\/beimel\/pub.html"},{"issue":"3","key":"12_CR4","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1109\/18.335890","volume":"40","author":"A. Beimel","year":"1994","unstructured":"Beimel, A., Chor, B.: Universally ideal secret sharing schemes. IEEE Trans. on Information Theory\u00a040(3), 786\u2013794 (1994)","journal-title":"IEEE Trans. on Information Theory"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1006\/jcss.1999.1648","volume":"59","author":"A. Beimel","year":"1999","unstructured":"Beimel, A., G\u00e1l, A.: On arithmetic branching programs. J. of Computer and System Sciences\u00a059, 195\u2013220 (1999)","journal-title":"J. of Computer and System Sciences"},{"issue":"1","key":"12_CR6","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF01202040","volume":"6","author":"A. Beimel","year":"1997","unstructured":"Beimel, A., G\u00e1l, A., Paterson, M.: Lower bounds for monotone span programs. Computational Complexity\u00a06(1), 29\u201345 (1997); Conference version: FOCS 1995","journal-title":"Computational Complexity"},{"issue":"5","key":"12_CR7","doi-asserted-by":"publisher","first-page":"1196","DOI":"10.1137\/S0097539704444038","volume":"34","author":"A. Beimel","year":"2005","unstructured":"Beimel, A., Weinreb, E.: Separating the power of monotone span programs over different fields. SIAM J. on Computing\u00a034(5), 1196\u20131215 (2005)","journal-title":"SIAM J. on Computing"},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computations. In: Proc. of the 20th ACM Symp. on the Theory of Computing, pp. 1\u201310 (1988)","DOI":"10.1145\/62212.62213"},{"key":"12_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/0-387-34799-2_3","volume-title":"Advances in Cryptology - CRYPTO \u201988","author":"J. Benaloh","year":"1990","unstructured":"Benaloh, J., Leichter, J.: Generalized secret sharing and monotone functions. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol.\u00a0403, pp. 27\u201335. Springer, Heidelberg (1990)"},{"key":"12_CR10","unstructured":"Benaloh, J., Rudich, S.: Private communication (1989)"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Blakley, G.R.: Safeguarding cryptographic keys. In: Merwin, R.E., Zanca, J.T., Smith, M. (eds.) Proc. of the 1979 AFIPS National Computer Conference, AFIPS Conference proceedings, vol.\u00a048, pp. 313\u2013317. AFIPS Press (1979)","DOI":"10.1109\/MARK.1979.8817296"},{"issue":"2","key":"12_CR12","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1023\/A:1008216403325","volume":"11","author":"C. Blundo","year":"1997","unstructured":"Blundo, C., De Santis, A., de Simone, R., Vaccaro, U.: Tight bounds on the information rate of secret sharing schemes. Designs, Codes and Cryptography\u00a011(2), 107\u2013122 (1997)","journal-title":"Designs, Codes and Cryptography"},{"issue":"2","key":"12_CR13","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1109\/18.370169","volume":"41","author":"C. Blundo","year":"1995","unstructured":"Blundo, C., De Santis, A., Giorgio Gaggia, A., Vaccaro, U.: New bounds on the information rate of secret sharing schemes. IEEE Trans. on Information Theory\u00a041(2), 549\u2013553 (1995)","journal-title":"IEEE Trans. on Information Theory"},{"key":"12_CR14","first-page":"105","volume":"6","author":"E.F. Brickell","year":"1989","unstructured":"Brickell, E.F.: Some ideal secret sharing schemes. Journal of Combin. Math. and Combin. Comput.\u00a06, 105\u2013113 (1989)","journal-title":"Journal of Combin. Math. and Combin. Comput."},{"issue":"3","key":"12_CR15","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00198463","volume":"6","author":"R.M. Capocelli","year":"1993","unstructured":"Capocelli, R.M., De Santis, A., Gargano, L., Vaccaro, U.: On the size of shares for secret sharing schemes. J. of Cryptology\u00a06(3), 157\u2013168 (1993)","journal-title":"J. of Cryptology"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., Damg\u00e5rd, I.: Multiparty unconditionally secure protocols. In: Proc. of the 20th ACM Symp. on the Theory of Computing, pp. 11\u201319 (1988)","DOI":"10.1145\/62212.62214"},{"key":"12_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/3-540-45539-6_22","volume-title":"Advances in Cryptology - EUROCRYPT 2000","author":"R. Cramer","year":"2000","unstructured":"Cramer, R., Damg\u00e5rd, I., Maurer, U.: General secure multi-party computation from any linear secret-sharing scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol.\u00a01807, pp. 316\u2013334. Springer, Heidelberg (2000)"},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BFb0053420","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 1994","author":"L. Csirmaz","year":"1995","unstructured":"Csirmaz, L.: The size of a share must be large. In: De Santis, A. (ed.) Advances in Cryptology \u2013 EUROCRYPT 1994. LNCS, vol.\u00a0950, pp. 13\u201322. Springer, Heidelberg (1995); Journal version in J. of Cryptology 10(4), 223\u2013231 (1997)"},{"issue":"3\u20134","key":"12_CR19","first-page":"429","volume":"32","author":"L. Csirmaz","year":"1996","unstructured":"Csirmaz, L.: The dealer\u2019s random bits in perfect secret sharing schemes. Studia Sci. Math. Hungar.\u00a032(3\u20134), 429\u2013437 (1996)","journal-title":"Studia Sci. Math. Hungar."},{"key":"12_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/3-540-46766-1_37","volume-title":"Advances in Cryptology - CRYPTO \u201991","author":"Y. Desmedt","year":"1992","unstructured":"Desmedt, Y., Frankel, Y.: Shared generation of authenticators and signatures. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol.\u00a0576, pp. 457\u2013469. Springer, Heidelberg (1992)"},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF01398012","volume":"6","author":"M. van Dijk","year":"1995","unstructured":"van Dijk, M.: On the information rate of perfect secret sharing schemes. Designs, Codes and Cryptography\u00a06, 143\u2013169 (1995)","journal-title":"Designs, Codes and Cryptography"},{"issue":"2","key":"12_CR22","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1023\/A:1008259214236","volume":"12","author":"M. van Dijk","year":"1997","unstructured":"van Dijk, M.: A linear construction of secret sharing schemes. Designs, Codes and Cryptography\u00a012(2), 161\u2013201 (1997)","journal-title":"Designs, Codes and Cryptography"},{"issue":"4","key":"12_CR23","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s000370100001","volume":"10","author":"A. G\u00e1l","year":"2002","unstructured":"G\u00e1l, A.: A characterization of span program size and improved lower bounds for monotone span programs. Computational Complexity\u00a010(4), 277\u2013296 (2002)","journal-title":"Computational Complexity"},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/S0020-0190(03)00334-X","volume":"87","author":"A. G\u00e1l","year":"2003","unstructured":"G\u00e1l, A., Pudl\u00e1k, P.: Monotone complexity and the rank of matrices. Inform. Process. Lett.\u00a087, 321\u2013326 (2003)","journal-title":"Inform. Process. Lett."},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: Proc. of the 13th ACM conference on Computer and communications security, pp. 89\u201398 (2006)","DOI":"10.1145\/1180405.1180418"},{"key":"#cr-split#-12_CR26.1","unstructured":"Ito, M., Saito, A., Nishizeki, T.: Secret sharing schemes realizing general access structure. In: Proc. of the IEEE Global Telecommunication Conf., Globecom 87, pp. 99-102 (1987)"},{"key":"#cr-split#-12_CR26.2","doi-asserted-by":"crossref","unstructured":"Journal version: Multiple assignment scheme for sharing secret. J. of Cryptology 6(1), 15-20 (1993)","DOI":"10.1007\/BF02620229"},{"issue":"2","key":"12_CR27","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M. Karchmer","year":"1990","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. on Discrete Mathematics\u00a03(2), 255\u2013265 (1990)","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: On span programs. In: Proc. of the 8th IEEE Structure in Complexity Theory, pp. 102\u2013111 (1993)","DOI":"10.1109\/SCT.1993.336536"},{"issue":"1","key":"12_CR29","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1109\/TIT.1983.1056621","volume":"29","author":"E.D. Karnin","year":"1983","unstructured":"Karnin, E.D., Greene, J.W., Hellman, M.E.: On secret sharing systems. IEEE Trans. on Information Theory\u00a029(1), 35\u201341 (1983)","journal-title":"IEEE Trans. on Information Theory"},{"issue":"1","key":"12_CR30","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1109\/71.722223","volume":"9","author":"M. Naor","year":"1998","unstructured":"Naor, M., Wool, A.: Access control and signatures via quorum secret sharing. IEEE Transactions on Parallel and Distributed Systems\u00a09(1), 909\u2013922 (1998)","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"12_CR31","doi-asserted-by":"publisher","first-page":"2596","DOI":"10.1109\/18.887867","volume":"46","author":"C. Padr\u00f3","year":"2000","unstructured":"Padr\u00f3, C., S\u00e1ez, G.: Secret sharing schemes with bipartite access structure. IEEE Trans. on Information Theory\u00a046, 2596\u20132605 (2000)","journal-title":"IEEE Trans. on Information Theory"},{"key":"12_CR32","doi-asserted-by":"crossref","unstructured":"Rabin, M.O.: Randomized Byzantine generals. In: Proc. of the 24th IEEE Symp. on Foundations of Computer Science, pp. 403\u2013409 (1983)","DOI":"10.1109\/SFCS.1983.48"},{"key":"12_CR33","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected ST-connectivity in log-space. In: Proc. of the 37th ACM Symp. on the Theory of Computing, pp. 376\u2013385 (2005)","DOI":"10.1145\/1060590.1060647"},{"issue":"3","key":"12_CR34","first-page":"717","volume":"14","author":"L. R\u00f3nyai","year":"2001","unstructured":"R\u00f3nyai, L., Babai, L., Ganapathy, M.K.: On the number of zero-patterns of a sequence of polynomials. Journal of the AMS\u00a014(3), 717\u2013735 (2001)","journal-title":"Journal of the AMS"},{"key":"12_CR35","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A. Shamir","year":"1979","unstructured":"Shamir, A.: How to share a secret. Communications of the ACM\u00a022, 612\u2013613 (1979)","journal-title":"Communications of the ACM"},{"key":"12_CR36","first-page":"71","volume":"1","author":"G.J. Simmons","year":"1991","unstructured":"Simmons, G.J., Jackson, W., Martin, K.M.: The geometry of shared secret schemes. Bulletin of the ICA\u00a01, 71\u201388 (1991)","journal-title":"Bulletin of the ICA"},{"issue":"1","key":"12_CR37","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1109\/18.272461","volume":"40","author":"D.R. Stinson","year":"1994","unstructured":"Stinson, D.R.: Decomposition construction for secret sharing schemes. IEEE Trans. on Information Theory\u00a040(1), 118\u2013125 (1994)","journal-title":"IEEE Trans. on Information Theory"},{"issue":"1","key":"12_CR38","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02122563","volume":"8","author":"E. Tardos","year":"1988","unstructured":"Tardos, E.: The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica\u00a08(1), 141\u2013142 (1988)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Security and Cryptography for Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85855-3_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T18:27:39Z","timestamp":1738348059000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-85855-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540858546","9783540858553"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85855-3_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}