{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T10:52:43Z","timestamp":1778064763905,"version":"3.51.4"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["639813"],"award-info":[{"award-number":["639813"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>\n            Consider the following secret-sharing problem: A file\n            <jats:italic>s<\/jats:italic>\n            should be distributed between\n            <jats:italic>n<\/jats:italic>\n            servers such that (d-1)-subsets cannot recover the file, (d+1)-subsets can recover the file, and\n            <jats:italic>d<\/jats:italic>\n            -subsets should be able to recover\n            <jats:italic>s<\/jats:italic>\n            if and only if they appear in some pre-defined list\n            <jats:italic>L<\/jats:italic>\n            . The goal is to minimize the information ratio\u2014that is, the number of bits stored on a server per each bit of the secret.\n          <\/jats:p>\n          <jats:p>\n            We show that for any constant\n            <jats:italic>d<\/jats:italic>\n            and any pre-defined list\n            <jats:italic>L<\/jats:italic>\n            , if the file is sufficiently long (exponential in\n            <jats:italic>\n              n\n              <jats:sup>d<\/jats:sup>\n            <\/jats:italic>\n            ), the problem can be solved with a\n            <jats:italic>constant<\/jats:italic>\n            asymptotic information ratio of\n            <jats:italic>\n              c\n              <jats:sub>d<\/jats:sub>\n            <\/jats:italic>\n            that does not grow with the number of servers\n            <jats:italic>n<\/jats:italic>\n            . This result is based on a new construction of\n            <jats:italic>d<\/jats:italic>\n            -party conditional disclosure of secrets for arbitrary predicates over an\n            <jats:italic>n<\/jats:italic>\n            -size domain in which each party communicates at most four bits per secret bit.\n          <\/jats:p>\n          <jats:p>\n            In both settings, previous results achieved a non-constant information ratio that grows asymptotically with\n            <jats:italic>n<\/jats:italic>\n            , even for the simpler special case of\n            <jats:italic>d = 2<\/jats:italic>\n            . Moreover, our constructions yield the first example of an access structure whose amortized information ratio is constant, whereas its best-known non-amortized information ratio is sub-exponential, thus providing a unique evidence for the potential power of\n            <jats:italic>amortization<\/jats:italic>\n            in the context of secret sharing.\n          <\/jats:p>\n          <jats:p>Our main result applies to exponentially long secrets, and so it should be mainly viewed as a barrier against amortizable lower-bound techniques. We also show that in some natural simple cases (e.g., low-degree predicates), amortization kicks in even for quasi-polynomially long secrets. Finally, we prove some limited lower bounds and point out some limitations of existing lower-bound techniques.<\/jats:p>","DOI":"10.1145\/3417756","type":"journal-article","created":{"date-parts":[[2020,10,1]],"date-time":"2020-10-01T04:07:32Z","timestamp":1601525252000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["On the Power of Amortization in Secret Sharing"],"prefix":"10.1145","volume":"12","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barak","family":"Arkis","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,9,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44987-6_8"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63688-7_24"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17659-4_15"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-019-09334-y"},{"key":"e_1_2_1_5_1","series-title":"Lecture Notes in Computer Science","volume-title":"Coding and Cryptology","author":"Beimel Amos","unstructured":"Amos Beimel . 2011. Secret-sharing schemes: A survey . In Coding and Cryptology . Lecture Notes in Computer Science , Vol. 6639 . Springer , 11--46. DOI:https:\/\/doi.org\/10.1007\/978-3-642-20901-7_2 10.1007\/978-3-642-20901-7_2 Amos Beimel. 2011. Secret-sharing schemes: A survey. In Coding and Cryptology. Lecture Notes in Computer Science, Vol. 6639. Springer, 11--46. DOI:https:\/\/doi.org\/10.1007\/978-3-642-20901-7_2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-014-9195-8"},{"key":"e_1_2_1_7_1","series-title":"Lecture Notes in Computer Science","volume-title":"Theory of Cryptography","author":"Beimel Amos","unstructured":"Amos Beimel , Oriol Farr\u00e0s , Yuval Mintz , and Naty Peter . 2017. Linear secret-sharing schemes for forbidden graph access structures . In Theory of Cryptography . Lecture Notes in Computer Science , Vol. 10678 . Springer , 394--423. DOI:https:\/\/doi.org\/10.1007\/978-3-319-70503-3_13 10.1007\/978-3-319-70503-3_13 Amos Beimel, Oriol Farr\u00e0s, Yuval Mintz, and Naty Peter. 2017. Linear secret-sharing schemes for forbidden graph access structures. In Theory of Cryptography. Lecture Notes in Computer Science, Vol. 10678. Springer, 394--423. DOI:https:\/\/doi.org\/10.1007\/978-3-319-70503-3_13"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/872746.873127"},{"key":"e_1_2_1_9_1","series-title":"Lecture Notes in Computer Science","volume-title":"Theory of Cryptography","author":"Beimel Amos","unstructured":"Amos Beimel , Yuval Ishai , Ranjit Kumaresan , and Eyal Kushilevitz . 2014. On the cryptographic complexity of the worst functions . In Theory of Cryptography . Lecture Notes in Computer Science , Vol. 8349 . Springer , 317--342. DOI:https:\/\/doi.org\/10.1007\/978-3-642-54242-8_14 10.1007\/978-3-642-54242-8_14 Amos Beimel, Yuval Ishai, Ranjit Kumaresan, and Eyal Kushilevitz. 2014. On the cryptographic complexity of the worst functions. In Theory of Cryptography. Lecture Notes in Computer Science, Vol. 8349. Springer, 317--342. DOI:https:\/\/doi.org\/10.1007\/978-3-642-54242-8_14"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78375-8_10"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2162183"},{"key":"e_1_2_1_12_1","volume-title":"Advances in Cryptology\u2014CRYPTO","author":"Benaloh Josh Cohen","year":"1988","unstructured":"Josh Cohen Benaloh and Jerry Leichter . 1988. Generalized secret sharing and monotone functions . In Advances in Cryptology\u2014CRYPTO 1988 . Lecture Notes in Computer Science, Vol. 403 . Springer , 27--35. DOI:https:\/\/doi.org\/10.1007\/0-387-34799-2_3 10.1007\/0-387-34799-2_3 Josh Cohen Benaloh and Jerry Leichter. 1988. Generalized secret sharing and monotone functions. In Advances in Cryptology\u2014CRYPTO 1988. Lecture Notes in Computer Science, Vol. 403. Springer, 27--35. DOI:https:\/\/doi.org\/10.1007\/0-387-34799-2_3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MARK.1979.8817296"},{"key":"e_1_2_1_14_1","series-title":"Lecture Notes in Computer Science","volume-title":"Theory of Cryptography","author":"Bogdanov Andrej","unstructured":"Andrej Bogdanov , Siyao Guo , and Ilan Komargodski . 2016. Threshold secret sharing requires a linear size alphabet . In Theory of Cryptography . Lecture Notes in Computer Science , Vol. 9986 . Springer , 471--484. DOI:https:\/\/doi.org\/10.1007\/978-3-662-53644-5_18 10.1007\/978-3-662-53644-5_18 Andrej Bogdanov, Siyao Guo, and Ilan Komargodski. 2016. Threshold secret sharing requires a linear size alphabet. In Theory of Cryptography. Lecture Notes in Computer Science, Vol. 9986. Springer, 471--484. DOI:https:\/\/doi.org\/10.1007\/978-3-662-53644-5_18"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00198463"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001459900029"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48000-7_24"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1689"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180418"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 1987 IEEE GLOBECOM Conference. IEEE","author":"Ito M.","unstructured":"M. Ito , A. Saito , and T. Nishizeki . 1987. Secret sharing scheme realizing general access structure . In Proceedings of the 1987 IEEE GLOBECOM Conference. IEEE , Los Alamitos, CA, 99--102. M. Ito, A. Saito, and T. Nishizeki. 1987. Secret sharing scheme realizing general access structure. In Proceedings of the 1987 IEEE GLOBECOM Conference. IEEE, Los Alamitos, CA, 99--102."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1993.336536"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056621"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings, Part I. Lecture Notes in Computer Science","volume":"10401","author":"Katz Jonathan","year":"2017","unstructured":"Jonathan Katz and Hovav Shacham ( Eds .). 2017 . Advances in Cryptology\u2014CRYPTO 2017: 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20--24, 2017 , Proceedings, Part I. Lecture Notes in Computer Science , Vol. 10401 . Springer. DOI:https:\/\/doi.org\/10.1007\/978-3-319-63688-7 10.1007\/978-3-319-63688-7 Jonathan Katz and Hovav Shacham (Eds.). 2017. Advances in Cryptology\u2014CRYPTO 2017: 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20--24, 2017, Proceedings, Part I. Lecture Notes in Computer Science, Vol. 10401. Springer. DOI:https:\/\/doi.org\/10.1007\/978-3-319-63688-7"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188936"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63688-7_25"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78381-9_21"},{"key":"e_1_2_1_28_1","volume-title":"Information Ratios of Graph Secret-Sharing Schemes. Master\u2019s Thesis. Department of Computer Science","author":"Mintz Yuval","unstructured":"Yuval Mintz . 2012. Information Ratios of Graph Secret-Sharing Schemes. Master\u2019s Thesis. Department of Computer Science , Ben Gurion University . Yuval Mintz. 2012. Information Ratios of Graph Secret-Sharing Schemes. Master\u2019s Thesis. Department of Computer Science, Ben Gurion University."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2500232"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11426639_27"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.272461"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 16th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM\u201997)","author":"Sun Hung-Min","year":"1997","unstructured":"Hung-Min Sun and Shiuh-Pyng Shieh . 1997 . Secret sharing in graph-based prohibited structures . In Proceedings of the 16th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM\u201997) . IEEE, Los Alamitos, CA, 718--724. http:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=4979. Hung-Min Sun and Shiuh-Pyng Shieh. 1997. Secret sharing in graph-based prohibited structures. In Proceedings of the 16th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM\u201997). IEEE, Los Alamitos, CA, 718--724. http:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=4979."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48797-6_27"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417756","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3417756","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:14Z","timestamp":1750197674000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417756"}},"subtitle":["<i>d<\/i>\n            -Uniform Secret Sharing and CDS with Constant Information Rate"],"short-title":[],"issued":{"date-parts":[[2020,9,30]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3417756"],"URL":"https:\/\/doi.org\/10.1145\/3417756","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,30]]},"assertion":[{"value":"2019-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}