{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T00:35:25Z","timestamp":1775262925306,"version":"3.50.1"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030038069","type":"print"},{"value":"9783030038076","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-03807-6_12","type":"book-chapter","created":{"date-parts":[[2018,11,3]],"date-time":"2018-11-03T23:42:46Z","timestamp":1541288566000},"page":"317-344","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["On the Power of Amortization in Secret Sharing: d-Uniform Secret Sharing and CDS with Constant Information Rate"],"prefix":"10.1007","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barak","family":"Arkis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,11,4]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Arkis, B.: Conditional disclosure of secrets and d-uniform secret sharing with constant information rate. IACR Cryptology ePrint Archive 2018\/1 (2018)","DOI":"10.1007\/978-3-030-03807-6_12"},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/978-3-319-63688-7_24","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"B Applebaum","year":"2017","unstructured":"Applebaum, B., Arkis, B., Raykov, P., Vasudevan, P.N.: Conditional disclosure of secrets: amplification, closure, amortization, lower-bounds, and separations. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 727\u2013757. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_24"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-319-78375-8_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"B Applebaum","year":"2018","unstructured":"Applebaum, B., Holenstein, T., Mishra, M., Shayevitz, O.: The communication complexity of private simultaneous messages, revisited. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 261\u2013286. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78375-8_9. https:\/\/eprint.iacr.org\/2018\/144"},{"issue":"4","key":"12_CR4","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B Applebaum","year":"2006","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in $$\\text{ NC }^{0}$$ . SIAM J. Comput. 36(4), 845\u2013888 (2006)","journal-title":"SIAM J. Comput."},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/3-540-44987-6_8","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2001","author":"B Aiello","year":"2001","unstructured":"Aiello, B., Ishai, Y., Reingold, O.: Priced oblivious transfer: how to sell digital goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 119\u2013135. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44987-6_8"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-642-20901-7_2","volume-title":"Coding and Cryptology","author":"A Beimel","year":"2011","unstructured":"Beimel, A.: Secret-sharing schemes: a survey. In: Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 11\u201346. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20901-7_2"},{"issue":"2","key":"12_CR7","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/s00145-014-9195-8","volume":"29","author":"A Beimel","year":"2016","unstructured":"Beimel, A., Farr\u00e0s, O., Mintz, Y.: Secret-sharing schemes for very dense graphs. J. Cryptol. 29(2), 336\u2013362 (2016)","journal-title":"J. Cryptol."},{"key":"12_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-319-70503-3_13","volume-title":"Theory of Cryptography","author":"A Beimel","year":"2017","unstructured":"Beimel, A., Farr\u00e0s, O., Mintz, Y., Peter, N.: Linear secret-sharing schemes for forbidden graph access structures. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 394\u2013423. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70503-3_13"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y.: On the power of nonlinear secrect-sharing. In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, 18\u201321 June 2001, pp. 188\u2013202. IEEE Computer Society (2001)","DOI":"10.1109\/CCC.2001.933886"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-642-54242-8_14","volume-title":"Theory of Cryptography","author":"A Beimel","year":"2014","unstructured":"Beimel, A., Ishai, Y., Kumaresan, R., Kushilevitz, E.: On the cryptographic complexity of the worst functions. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 317\u2013342. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54242-8_14"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-3-319-78375-8_10","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"A Beimel","year":"2018","unstructured":"Beimel, A., Kushilevitz, E., Nissim, P.: The Complexity of Multiparty PSM Protocols and Related Models. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 287\u2013318. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78375-8_10. https:\/\/eprint.iacr.org\/2018\/148"},{"key":"12_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/0-387-34799-2_3","volume-title":"Advances in Cryptology\u2014CRYPTO \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. 403, pp. 27\u201335. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34799-2_3"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings AFIPS 1979 National Computer Conference, pp. 313\u2013317. AFIPS (1979)","DOI":"10.1109\/MARK.1979.8817296"},{"issue":"6","key":"12_CR14","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B Chor","year":"1998","unstructured":"Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. J. ACM 45(6), 965\u2013981 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"12_CR15","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00198463","volume":"6","author":"RM Capocelli","year":"1993","unstructured":"Capocelli, R.M., Santis, A.D., Gargano, L., Vaccaro, U.: On the size of shares for secret sharing schemes. J. Cryptol. 6(3), 157\u2013167 (1993)","journal-title":"J. Cryptol."},{"issue":"4","key":"12_CR16","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s001459900029","volume":"10","author":"L Csirmaz","year":"1997","unstructured":"Csirmaz, L.: The size of a share must be large. J. Cryptol. 10(4), 223\u2013231 (1997)","journal-title":"J. Cryptol."},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: Leighton, F.T., Goodrich, M.T. (eds.) Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23\u201325 May 1994, Montr\u00e9al, Qu\u00e9bec, Canada, pp. 554\u2013563. ACM (1994)","DOI":"10.1145\/195058.195408"},{"issue":"3","key":"12_CR18","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1006\/jcss.1999.1689","volume":"60","author":"Y Gertner","year":"2000","unstructured":"Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T.: Protecting data privacy in private information retrieval schemes. J. Comput. Syst. Sci. 60(3), 592\u2013629 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/978-3-662-48000-7_24","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"R Gay","year":"2015","unstructured":"Gay, R., Kerenidis, I., Wee, H.: Communication complexity of conditional disclosure of secrets and attribute-based encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 485\u2013502. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_24"},{"key":"12_CR20","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 Juels, A., Wright, R.N., di Vimercati, S.D.C. (eds.) Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, Alexandria, VA, USA, 30 october\u20133 November 2006, pp. 89\u201398. ACM (2006)","DOI":"10.1145\/1180405.1180418"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E.: Randomizing polynomials: A new representation with applications to round-efficient secure computation. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12\u201314 November 2000, Redondo Beach, California, USA, pp. 294\u2013304. IEEE Computer Society (2000)","DOI":"10.1109\/SFCS.2000.892118"},{"key":"12_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/3-540-45465-9_22","volume-title":"Automata, Languages and Programming","author":"Y Ishai","year":"2002","unstructured":"Ishai, Y., Kushilevitz, E.: Perfect constant-round secure computation via perfect randomizing polynomials. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 244\u2013256. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45465-9_22"},{"key":"12_CR23","unstructured":"Ishai, Y.: Randomization techniques for secure computation. In: Prabhakaran, M., Sahai, A. (eds.) Secure Multi-Party Computation, Volume 10 of Cryptology and Information Security Series, pp. 222\u2013248. IOS Press (2013)"},{"key":"12_CR24","unstructured":"Ito, M., Saito, A., Nishizeki, T.: Secret sharing scheme realizing general access structure. In: Proceedings IEEE Globecom 1987, pp. 99\u2013102. IEEE (1987)"},{"key":"12_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1007\/978-3-662-43948-7_54","volume-title":"Automata, Languages, and Programming","author":"Y Ishai","year":"2014","unstructured":"Ishai, Y., Wee, H.: Partial garbling schemes and their applications. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 650\u2013662. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_54"},{"issue":"1","key":"12_CR26","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1109\/TIT.1983.1056621","volume":"29","author":"ED Karnin","year":"1983","unstructured":"Karnin, E.D., Greene, J.W., Hellman, M.E.: On secret sharing systems. IEEE Trans. Inf. Theor. 29(1), 35\u201341 (1983)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"12_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63688-7","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","year":"2017","unstructured":"Katz, J., Shacham, H. (eds.): CRYPTO 2017. LNCS, vol. 10401. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, 18\u201321 May 1993, pp. 102\u2013111. IEEE Computer Society (1993)","DOI":"10.1109\/SCT.1993.336536"},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"Liu, T., Vaikuntanathan, V.: Breaking the circuit-size barrier in secret sharing. In: To appear in STOC2018 (2018). https:\/\/eprint.iacr.org\/2018\/333","DOI":"10.1145\/3188745.3188936"},{"key":"12_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1007\/978-3-319-63688-7_25","volume-title":"Advances in Cryptology - CRYPTO 2017","author":"T Liu","year":"2017","unstructured":"Liu, T., Vaikuntanathan, V., Wee, H.: Conditional disclosure of secrets via non-linear reconstruction. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. Lecture Notes in Computer Science, vol. 10401, pp. 758\u2013790. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_25"},{"key":"12_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/978-3-319-78381-9_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"T Liu","year":"2018","unstructured":"Liu, T., Vaikuntanathan, V., Wee, H.: Towards breaking the exponential barrier for general secret sharing. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 567\u2013596. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78381-9_21"},{"key":"12_CR32","unstructured":"Mintz, Y.: Information ratios of graph secret-sharing schemes. Master\u2019s thesis, Department of Computer Science, Ben Gurion University (2012)"},{"issue":"11","key":"12_CR33","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. Commun. ACM 22(11), 612\u2013613 (1979)","journal-title":"Commun. ACM"},{"key":"12_CR34","unstructured":"Sun, H., Shieh, S.: Secret sharing in graph-based prohibited structures. In: Proceedings IEEE INFOCOM 1997, The Conference on Computer Communications, Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Driving the Information Revolution, Kobe, Japan, 7\u201312 April 1997, pp. 718\u2013724. IEEE (1997)"},{"issue":"1","key":"12_CR35","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1109\/18.272461","volume":"40","author":"DR Stinson","year":"1994","unstructured":"Stinson, D.R.: Decomposition constructions for secret-sharing schemes. IEEE Trans. Inf. Theor. 40(1), 118\u2013125 (1994)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"12_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/11426639_27","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"A Sahai","year":"2005","unstructured":"Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457\u2013473. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11426639_27"},{"key":"12_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1007\/978-3-662-48797-6_27","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2015","author":"V Vaikuntanathan","year":"2015","unstructured":"Vaikuntanathan, V., Vasudevan, P.N.: Secret sharing and statistical zero knowledge. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 656\u2013680. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48797-6_27"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-03807-6_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T23:24:05Z","timestamp":1775258645000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-03807-6_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030038069","9783030038076"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-03807-6_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"4 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Panaji","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 November 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 November 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}