{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:00Z","timestamp":1781031420427,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800870","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1627-1638","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sub-linear Secure Broadcast and Applications"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0405-9651","authenticated-orcid":false,"given":"Yuval","family":"Gelles","sequence":"first","affiliation":[{"name":"Hebrew University of Jerusalem, Jerusalem, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1647-2112","authenticated-orcid":false,"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Jerusalem, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2357-2445","authenticated-orcid":false,"given":"Merav","family":"Parter","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77618"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1286955"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611491"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626183.3659959"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/138027.138036"},{"key":"e_1_3_2_1_6_1","volume-title":"Proc. 42nd Annual Allerton Conference on Communication, Control, and Computing. 63\u201368","author":"Feldman Jon","year":"2004","unstructured":"Jon Feldman, Tal Malkin, Cliff Stein, and Rocco A Servedio. 2004. On the capacity of secure network coding. In Proc. 42nd Annual Allerton Conference on Communication, Control, and Computing. 63\u201368."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583668.3594578"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261118"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_41"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M113277X"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_1"},{"key":"e_1_3_2_1_13_1","volume-title":"32nd International Symposium on Distributed Computing (DISC","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari and Fabian Kuhn. 2018. Distributed MST and broadcast with fewer messages, and faster gossiping. In 32nd International Symposium on Distributed Computing (DISC 2018). 121, 30\u20131."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_14"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48405-1_37"},{"key":"e_1_3_2_1_16_1","first-page":"1","article-title":"Time-Message Trade-Offs in Distributed Algorithms. In DISC (LIPIcs, Vol. 121)","volume":"32","author":"Gmyr Robert","year":"2018","unstructured":"Robert Gmyr and Gopal Pandurangan. 2018. Time-Message Trade-Offs in Distributed Algorithms. In DISC (LIPIcs, Vol. 121). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 32:1\u201332:18.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1097808"},{"key":"e_1_3_2_1_18_1","first-page":"1","article-title":"General CONGEST Compilers against Adversarial Edges. In DISC (LIPIcs, Vol. 209)","volume":"24","author":"Hitron Yael","year":"2021","unstructured":"Yael Hitron and Merav Parter. 2021. General CONGEST Compilers against Adversarial Edges. In DISC (LIPIcs, Vol. 209). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 24:1\u201324:18.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_19_1","volume-title":"36th International Symposium on Distributed Computing (DISC","author":"Hitron Yael","year":"2022","unstructured":"Yael Hitron, Merav Parter, and Eylon Yogev. 2022. Broadcast CONGEST algorithms against eavesdroppers. In 36th International Symposium on Distributed Computing (DISC 2022)."},{"key":"e_1_3_2_1_20_1","volume-title":"14th Innovations in Theoretical Computer Science Conference (ITCS","author":"Hitron Yael","year":"2023","unstructured":"Yael Hitron, Merav Parter, and Eylon Yogev. 2023. Secure distributed network optimization against eavesdroppers. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). 71\u20131."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/MWC.2004.1269720"},{"key":"e_1_3_2_1_22_1","volume-title":"Proc. 5th Symp. on Discrete Algorithms. 424","author":"Karger David R","year":"1994","unstructured":"David R Karger. 1994. Using randomized sparsi cation to approximate minimum cuts. In Proc. 5th Symp. on Discrete Algorithms. 424, 432."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Valerie King Shay Kutten and Mikkel Thorup. 2015. Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication. In PODC. ACM 71\u201380.","DOI":"10.1145\/2767386.2767405"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/224964.224990"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0929"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Christoph Lenzen and Boaz Patt-Shamir. 2013. Fast routing table construction using small messages: extended abstract. In STOC. ACM 381\u2013390.","DOI":"10.1145\/2488608.2488656"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Danupon Nanongkai. 2014. Distributed approximation algorithms for weighted shortest paths. In STOC. ACM 565\u2013573.","DOI":"10.1145\/2591796.2591850"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_30"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_3_2_1_30_1","volume-title":"Otakar Boruvka on minimum spanning tree problem Translation of both the 1926 papers, comments, history. Discrete mathematics, 233, 1-3","author":"Ne\u0161et\u0159il Jaroslav","year":"2001","unstructured":"Jaroslav Ne\u0161et\u0159il, Eva Milkov\u00e1, and Helena Ne\u0161et\u0159ilov\u00e1. 2001. Otakar Boruvka on minimum spanning tree problem Translation of both the 1926 papers, comments, history. Discrete mathematics, 233, 1-3 (2001), 3\u201336."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00144"},{"key":"e_1_3_2_1_32_1","volume-title":"Distributed Algorithms Made Secure: A Graph Theoretic Approach","author":"Parter Merav","unstructured":"Merav Parter and Eylon Yogev. 2019. Distributed Algorithms Made Secure: A Graph Theoretic Approach. In SODA. SIAM, 1693\u20131710."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.101"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Merav Parter and Eylon Yogev. 2019. Secure Distributed Computing Made (Nearly) Optimal. In PODC. ACM 107\u2013116.","DOI":"10.1145\/3293611.3331620"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.221"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800870","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:59:15Z","timestamp":1781027955000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800870"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":38,"alternative-id":["10.1145\/3798129.3800870","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800870","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}