{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T15:55:09Z","timestamp":1766159709305,"version":"3.44.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T00:00:00Z","timestamp":1749168000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T00:00:00Z","timestamp":1749168000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"PNRR"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Evolving secret sharing (Komargodski, Naor, and Yogev, TCC\u201916) generalizes the notion of secret sharing to the setting of <jats:italic>evolving access structures<\/jats:italic>, in which the share holders are added to the system in an online manner, and where the dealer does not know neither the access structure nor the maximum psnber of parties in advance. Here, the main difficulty is to distribute shares to the new players without updating the shares of old players; moreover, one would like to minimize the share size as a function of the psnber of players. In this paper, we initiate a systematic study of evolving secret sharing in the <jats:italic>computational setting<\/jats:italic>, where the maximum psnber of parties is polynomial in the security parameter, but the dealer still does not know this value, neither it knows the access structure in advance. Moreover, the privacy guarantee only holds against computationally bounded adversaries corrupting an unauthorized subset of the players. Our main result is that for many interesting, and practically relevant, evolving access structures, under standard hardness assumptions, there exist efficient secret sharing schemes with computational privacy and in which the shares are <jats:italic>succinct<\/jats:italic> (i.e., much smaller compared to the size of a natural computational representation of the evolving access structure). These access structures include evolving graphs access structures, threshold access structures, and monotone circuits\/DNF\/CNF access structures meeting an additional <jats:italic>rigidity<\/jats:italic> property that we show to be necessary if one wants to avoid updating the shares of old parties.<\/jats:p>","DOI":"10.1007\/s10623-025-01658-0","type":"journal-article","created":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T06:21:50Z","timestamp":1749190910000},"page":"3809-3861","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Evolving secret sharing revisited: computational security and succinctness"],"prefix":"10.1007","volume":"93","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4639-0636","authenticated-orcid":false,"given":"Danilo","family":"Francati","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2379-8564","authenticated-orcid":false,"given":"Daniele","family":"Venturi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,6]]},"reference":[{"key":"1658_CR1","doi-asserted-by":"publisher","unstructured":"Alon, B., Beimel, A., Ben\u00a0David, T., Omri, E., Paskin-Cherniavsky, A.: New upper bounds for evolving secret sharing via infinite branching programs. In: Theory of Cryptography Conference. pp. 548\u2013580. Springer (2025). https:\/\/doi.org\/10.1007\/978-3-031-78023-3_18","DOI":"10.1007\/978-3-031-78023-3_18"},{"key":"1658_CR2","doi-asserted-by":"publisher","unstructured":"Applebaum, B., Beimel, A., Ishai, Y., Kushilevitz, E., Liu, T., Vaikuntanathan, V.: Succinct computational secret sharing. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. pp. 1553\u20131566 (2023). https:\/\/doi.org\/10.1145\/3564246.3585127","DOI":"10.1145\/3564246.3585127"},{"key":"1658_CR3","doi-asserted-by":"publisher","unstructured":"Applebaum, B., Nir, O.: Upslices, downslices, and secret-sharing with complexity of $${1.5}^n$$. In: Malkin, T., Peikert, C. (eds.) CRYPTO\u00a02021, Part\u00a0III. LNCS, vol. 12827, pp. 627\u2013655. Springer, Heidelberg, Virtual Event (Aug 2021). https:\/\/doi.org\/10.1007\/978-3-030-84252-9_21","DOI":"10.1007\/978-3-030-84252-9_21"},{"key":"1658_CR4","doi-asserted-by":"publisher","unstructured":"Backes, M., Kate, A., Patra, A.: Computational verifiable secret sharing revisited. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT\u00a02011. LNCS, vol.\u00a07073, pp. 590\u2013609. Springer, Heidelberg (Dec 2011). https:\/\/doi.org\/10.1007\/978-3-642-25385-0_32","DOI":"10.1007\/978-3-642-25385-0_32"},{"issue":"2","key":"1658_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2160158.2160159","volume":"59","author":"B Barak","year":"2012","unstructured":"Barak B., Goldreich O., Impagliazzo R., Rudich S., Sahai A., Vadhan S., Yang K.: On the (im) possibility of obfuscating programs. Journal of the ACM (JACM) 59(2), 1\u201348 (2012).","journal-title":"Journal of the ACM (JACM)"},{"key":"1658_CR6","doi-asserted-by":"publisher","unstructured":"B\u00e9guin, P., Cresti, A.: General short computational secret sharing schemes. In: Guillou, L.C., Quisquater, J.J. (eds.) EUROCRYPT\u201995. LNCS, vol.\u00a0921, pp. 194\u2013208. Springer, Heidelberg (May 1995). https:\/\/doi.org\/10.1007\/3-540-49264-X_16","DOI":"10.1007\/3-540-49264-X_16"},{"key":"1658_CR7","doi-asserted-by":"crossref","unstructured":"Beimel, A.: Secret-sharing schemes: A survey. In: Coding and Cryptology - Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings. vol.\u00a06639, pp. 11\u201346. Springer (2011)","DOI":"10.1007\/978-3-642-20901-7_2"},{"issue":"2","key":"1658_CR8","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. Journal of Cryptology 29(2), 336\u2013362 (2016). https:\/\/doi.org\/10.1007\/s00145-014-9195-8.","journal-title":"Journal of Cryptology"},{"key":"1658_CR9","doi-asserted-by":"publisher","unstructured":"Beimel, A., Othman, H.: Evolving ramp secret-sharing schemes. In: Catalano, D., De Prisco, R. (eds.) SCN 18. LNCS, vol. 11035, pp. 313\u2013332. Springer, Heidelberg (Sep 2018). https:\/\/doi.org\/10.1007\/978-3-319-98113-0_17","DOI":"10.1007\/978-3-319-98113-0_17"},{"key":"1658_CR10","doi-asserted-by":"publisher","unstructured":"Beimel, A., Othman, H.: Evolving ramp secret sharing with a small gap. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT\u00a02020, Part\u00a0I. LNCS, vol. 12105, pp. 529\u2013555. Springer, Heidelberg (May 2020). https:\/\/doi.org\/10.1007\/978-3-030-45721-1_19","DOI":"10.1007\/978-3-030-45721-1_19"},{"key":"1658_CR11","doi-asserted-by":"publisher","unstructured":"Beimel, A., Tassa, T., Weinreb, E.: Characterizing ideal weighted threshold secret sharing. In: Theory of Cryptography: Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005. Proceedings 2. pp. 600\u2013619. Springer (2005). https:\/\/doi.org\/10.1007\/978-3-540-30576-7_32","DOI":"10.1007\/978-3-540-30576-7_32"},{"key":"1658_CR12","doi-asserted-by":"crossref","unstructured":"Blakley, G.R.: Safeguarding cryptographic keys. Proceedings of AFIPS 1979 National Computer Conference 48, 313\u2013317 (1979)","DOI":"10.1109\/MARK.1979.8817296"},{"issue":"1","key":"1658_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.2020.v016a002","volume":"16","author":"A Bogdanov","year":"2020","unstructured":"Bogdanov A., Guo S., Komargodski I.: Threshold secret sharing requires a linear-size alphabet. Theory of Computing 16(1), 1\u201318 (2020).","journal-title":"Theory of Computing"},{"key":"1658_CR14","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1007\/3-540-60693-9_22","volume-title":"5th IMA International Conference on Cryptography and Coding","author":"C Cachin","year":"1995","unstructured":"Cachin C.: On-line secret sharing. In: Boyd C. (ed.) 5th IMA International Conference on Cryptography and Coding, vol. 1025, pp. 190\u2013198. LNCS. Springer, Heidelberg (Dec (1995)."},{"key":"1658_CR15","doi-asserted-by":"publisher","unstructured":"Csirmaz, L.: The size of a share must be large. In: Santis, A.D. (ed.) EUROCRYPT\u201994. LNCS, vol.\u00a0950, pp. 13\u201322. Springer, Heidelberg (May 1995). https:\/\/doi.org\/10.1007\/BFb0053420","DOI":"10.1007\/BFb0053420"},{"issue":"4","key":"1658_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. Journal of Cryptology 10(4), 223\u2013231 (1997). https:\/\/doi.org\/10.1007\/s001459900029.","journal-title":"Journal of Cryptology"},{"issue":"1","key":"1658_CR17","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/s10623-011-9540-y","volume":"63","author":"L Csirmaz","year":"2012","unstructured":"Csirmaz L., Tardos G.: On-line secret sharing. Des. Codes Cryptogr. 63(1), 127\u2013147 (2012).","journal-title":"Des. Codes Cryptogr."},{"key":"1658_CR18","doi-asserted-by":"publisher","unstructured":"Desmedt, Y., Dutta, S., Morozov, K.: Evolving perfect hash families: A combinatorial viewpoint of evolving secret sharing. In: Mu, Y., Deng, R.H., Huang, X. (eds.) CANS 19. LNCS, vol. 11829, pp. 291\u2013307. Springer, Heidelberg (Oct 2019). https:\/\/doi.org\/10.1007\/978-3-030-31578-8_16","DOI":"10.1007\/978-3-030-31578-8_16"},{"key":"1658_CR19","doi-asserted-by":"publisher","unstructured":"Dutta, S., Roy, P.S., Fukushima, K., Kiyomoto, S., Sakurai, K.: Secret sharing on evolving multi-level access structure. In: You, I. (ed.) WISA 19. LNCS, vol. 11897, pp. 180\u2013191. Springer, Heidelberg (Aug 2019). https:\/\/doi.org\/10.1007\/978-3-030-39303-8_14","DOI":"10.1007\/978-3-030-39303-8_14"},{"key":"1658_CR20","doi-asserted-by":"publisher","unstructured":"Faonio, A., Venturi, D.: Non-malleable secret sharing in the computational setting: Adaptive tampering, noisy-leakage resilience, and improved rate. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO\u00a02019, Part\u00a0II. LNCS, vol. 11693, pp. 448\u2013479. Springer, Heidelberg (Aug 2019). https:\/\/doi.org\/10.1007\/978-3-030-26951-7_16","DOI":"10.1007\/978-3-030-26951-7_16"},{"key":"1658_CR21","doi-asserted-by":"publisher","unstructured":"Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: 21st ACM STOC. pp. 25\u201332. ACM Press (May 1989). https:\/\/doi.org\/10.1145\/73007.73010","DOI":"10.1145\/73007.73010"},{"key":"1658_CR22","doi-asserted-by":"publisher","unstructured":"Goyal, V., Kumar, A.: Non-malleable secret sharing. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) 50th ACM STOC. pp. 685\u2013698. ACM Press (Jun 2018). https:\/\/doi.org\/10.1145\/3188745.3188872","DOI":"10.1145\/3188745.3188872"},{"key":"1658_CR23","doi-asserted-by":"publisher","unstructured":"Hubacek, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: Roughgarden, T. (ed.) ITCS 2015. pp. 163\u2013172. ACM (Jan 2015). https:\/\/doi.org\/10.1145\/2688073.2688105","DOI":"10.1145\/2688073.2688105"},{"key":"1658_CR24","unstructured":"Ito, M., Saito, A., Nishizeki, T.: Secret sharing schemes realizing general access structure. In: Proc. IEEE Global Telecommunication Conf. (Globecom\u201987). pp. 99\u2013102 (1987)"},{"key":"1658_CR25","doi-asserted-by":"publisher","unstructured":"Jafargholi, Z., Kamath, C., Klein, K., Komargodski, I., Pietrzak, K., Wichs, D.: Be adaptive, avoid overcommitting. In: Katz, J., Shacham, H. (eds.) CRYPTO\u00a02017, Part\u00a0I. LNCS, vol. 10401, pp. 133\u2013163. Springer, Heidelberg (Aug 2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_5","DOI":"10.1007\/978-3-319-63688-7_5"},{"key":"1658_CR26","doi-asserted-by":"publisher","unstructured":"Komargodski, I., Naor, M., Yogev, E.: How to share a secret, infinitely. In: Hirt, M., Smith, A.D. (eds.) TCC\u00a02016-B, Part\u00a0II. LNCS, vol.\u00a09986, pp. 485\u2013514. Springer, Heidelberg (Oct\u00a0\/\u00a0Nov 2016). https:\/\/doi.org\/10.1007\/978-3-662-53644-5_19","DOI":"10.1007\/978-3-662-53644-5_19"},{"issue":"2","key":"1658_CR27","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/s00145-015-9226-0","volume":"30","author":"I Komargodski","year":"2017","unstructured":"Komargodski I., Naor M., Yogev E.: Secret-sharing for NP. Journal of Cryptology 30(2), 444\u2013469 (2017). https:\/\/doi.org\/10.1007\/s00145-015-9226-0.","journal-title":"Journal of Cryptology"},{"key":"1658_CR28","doi-asserted-by":"publisher","unstructured":"Komargodski, I., Paskin-Cherniavsky, A.: Evolving secret sharing: Dynamic thresholds and robustness. In: Kalai, Y., Reyzin, L. (eds.) TCC\u00a02017, Part\u00a0II. LNCS, vol. 10678, pp. 379\u2013393. Springer, Heidelberg (Nov 2017). https:\/\/doi.org\/10.1007\/978-3-319-70503-3_12","DOI":"10.1007\/978-3-319-70503-3_12"},{"key":"1658_CR29","doi-asserted-by":"publisher","unstructured":"Krawczyk, H.: Secret sharing made short. In: Stinson, D.R. (ed.) CRYPTO\u201993. LNCS, vol.\u00a0773, pp. 136\u2013146. Springer, Heidelberg (Aug 1994). https:\/\/doi.org\/10.1007\/3-540-48329-2_12","DOI":"10.1007\/3-540-48329-2_12"},{"key":"1658_CR30","doi-asserted-by":"publisher","unstructured":"Larsen, K.G., Simkin, M.: Secret sharing lower bound: Either reconstruction is hard or shares are long. In: Galdi, C., Kolesnikov, V. (eds.) SCN 20. LNCS, vol. 12238, pp. 566\u2013578. Springer, Heidelberg (Sep 2020). https:\/\/doi.org\/10.1007\/978-3-030-57990-6_28","DOI":"10.1007\/978-3-030-57990-6_28"},{"key":"1658_CR31","doi-asserted-by":"publisher","unstructured":"Luby, M.: Lt codes. In: 43rd FOCS. pp. 271\u2013282. IEEE Computer Society Press (Nov 2002). https:\/\/doi.org\/10.1109\/SFCS.2002.1181950","DOI":"10.1109\/SFCS.2002.1181950"},{"issue":"2","key":"1658_CR32","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1109\/18.910575","volume":"47","author":"M Luby","year":"2001","unstructured":"Luby M., Mitzenmacher M., Shokrollahi M.A., Spielman D.A.: Efficient erasure correcting codes. IEEE Trans. Inf. Theory 47(2), 569\u2013584 (2001).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1658_CR33","doi-asserted-by":"publisher","unstructured":"Mazor, N.: A lower bound on the share size in evolving secret sharing. In: 4th Conference on Information-Theoretic Cryptography (ITC 2023). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ITC.2023.2","DOI":"10.4230\/LIPIcs.ITC.2023.2"},{"key":"1658_CR34","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M.: Digital fountains: a survey and look forward. In: 2004 IEEE Information Theory Workshop, San Antonio, TX, USA, 24-29 October, 2004. pp. 271\u2013276. IEEE (2004)","DOI":"10.1109\/ITW.2004.1405313"},{"key":"1658_CR35","doi-asserted-by":"publisher","unstructured":"Okamoto, T., Pietrzak, K., Waters, B., Wichs, D.: New realizations of somewhere statistically binding hashing and positional accumulators. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT\u00a02015, Part\u00a0I. LNCS, vol.\u00a09452, pp. 121\u2013145. Springer, Heidelberg (Nov\u00a0\/\u00a0Dec 2015). https:\/\/doi.org\/10.1007\/978-3-662-48797-6_6","DOI":"10.1007\/978-3-662-48797-6_6"},{"key":"1658_CR36","unstructured":"Paskin-Cherniavsky, A.: How to infinitely share a secret more efficiently. Cryptology ePrint Archive, Report 2016\/1088 (2016), https:\/\/eprint.iacr.org\/2016\/1088"},{"issue":"9","key":"1658_CR37","doi-asserted-by":"crossref","first-page":"5600","DOI":"10.1109\/TIT.2013.2264504","volume":"59","author":"IC Pueyo","year":"2013","unstructured":"Pueyo I.C., Cramer R., Xing C.: Bounds on the threshold gap in secret sharing and its applications. IEEE Trans. Inf. Theory 59(9), 5600\u20135612 (2013).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1658_CR38","doi-asserted-by":"publisher","unstructured":"Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In: 21st ACM STOC. pp. 73\u201385. ACM Press (May 1989). https:\/\/doi.org\/10.1145\/73007.73014","DOI":"10.1145\/73007.73014"},{"issue":"2","key":"1658_CR39","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest R.L., Shamir A., Adleman L.M.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the Association for Computing Machinery 21(2), 120\u2013126 (1978). https:\/\/doi.org\/10.1145\/359340.359342.","journal-title":"Communications of the Association for Computing Machinery"},{"issue":"11","key":"1658_CR40","doi-asserted-by":"crossref","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 Association for Computing Machinery 22(11), 612\u2013613 (1979).","journal-title":"Communications of the Association for Computing Machinery"},{"issue":"3\u20134","key":"1658_CR41","first-page":"213","volume":"6","author":"MA Shokrollahi","year":"2009","unstructured":"Shokrollahi M.A., Luby M.: Raptor codes. Found. Trends Commun. Inf. Theory 6(3\u20134), 213\u2013322 (2009).","journal-title":"Found. Trends Commun. Inf. Theory"},{"key":"1658_CR42","first-page":"162","volume-title":"INDOCRYPT 2003","author":"V Vinod","year":"2003","unstructured":"Vinod V., Narayanan A., Srinathan K., Rangan C.P., Kim K.: On the power of computational secret sharing. In: Johansson T., Maitra S. (eds.) INDOCRYPT 2003, vol. 2904, pp. 162\u2013176. LNCS. Springer, Heidelberg (2003)."},{"key":"1658_CR43","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2024.3379278","author":"C Xing","year":"2024","unstructured":"Xing C., Yuan C.: Evolving secret sharing schemes based on polynomial evaluations and algebraic geometry codes. IEEE Transactions on Information Theory (2024). https:\/\/doi.org\/10.1109\/TIT.2024.3379278.","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-025-01658-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-025-01658-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-025-01658-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T02:05:00Z","timestamp":1757988300000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-025-01658-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,6]]},"references-count":43,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["1658"],"URL":"https:\/\/doi.org\/10.1007\/s10623-025-01658-0","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"type":"print","value":"0925-1022"},{"type":"electronic","value":"1573-7586"}],"subject":[],"published":{"date-parts":[[2025,6,6]]},"assertion":[{"value":"13 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}