{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T20:18:55Z","timestamp":1790626735522,"version":"4.1.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T00:00:00Z","timestamp":1694476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T00:00:00Z","timestamp":1694476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2023,10]]},"DOI":"10.1007\/s00145-023-09473-3","type":"journal-article","created":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T21:01:46Z","timestamp":1694552506000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Topology-Hiding Communication from Minimal Assumptions"],"prefix":"10.1007","volume":"36","author":[{"given":"Marshall","family":"Ball","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elette","family":"Boyle","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Cohen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lisa","family":"Kohl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tal","family":"Malkin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Meyer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tal","family":"Moran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,9,12]]},"reference":[{"key":"9473_CR1","doi-asserted-by":"crossref","unstructured":"A.\u00a0Akavia and T.\u00a0Moran. Topology-hiding computation beyond logarithmic diameter. In 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), part III (2017), pp. 609\u2013637","DOI":"10.1007\/978-3-319-56617-7_21"},{"key":"9473_CR2","doi-asserted-by":"crossref","unstructured":"A.\u00a0Akavia, R.\u00a0LaVigne, and T.\u00a0Moran. Topology-hiding computation on all graphs. In 37th Annual International Cryptology Conference (CRYPTO), part I (2017), pp. 447\u2013467","DOI":"10.1007\/978-3-319-63688-7_15"},{"key":"9473_CR3","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ball, E.\u00a0Boyle, T.\u00a0Malkin, and T.\u00a0Moran. Exploring the boundaries of topology-hiding computation. In 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), part III (2018), pp. 294\u2013325","DOI":"10.1007\/978-3-319-78372-7_10"},{"key":"9473_CR4","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ball, E.\u00a0Boyle, R.\u00a0Cohen, T.\u00a0Malkin, and T.\u00a0Moran. Is information-theoretic topology-hiding computation possible? In Proceedings of the 17th Theory of Cryptography Conference(TCC), part I (2019), pp. 502\u2013530","DOI":"10.1007\/978-3-030-36030-6_20"},{"key":"9473_CR5","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ball, E.\u00a0Boyle, R.\u00a0Cohen, L.\u00a0Kohl, T.\u00a0Malkin, P.\u00a0Meyer, and T.\u00a0Moran. Topology-hiding communication from minimal assumptions. In Proceedings of the 18th Theory of Cryptography Conference(TCC), part II (2020), pp. 473\u2013501","DOI":"10.1007\/978-3-030-64378-2_17"},{"key":"9473_CR6","doi-asserted-by":"crossref","unstructured":"D.\u00a0Beaver. Foundations of secure interactive computing. In 10th Annual International Cryptology Conference (CRYPTO) (1991), pp. 377\u2013391","DOI":"10.1007\/3-540-46766-1_31"},{"key":"9473_CR7","doi-asserted-by":"crossref","unstructured":"D.\u00a0Beaver. Precomputing oblivious transfer. In 14th Annual International Cryptology Conference (CRYPTO) (1995), pp. 97\u2013109","DOI":"10.1007\/3-540-44750-4_8"},{"key":"9473_CR8","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ben-Or, S.\u00a0Goldwasser, and A.\u00a0Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC) (1988), pp. 1\u201310","DOI":"10.1145\/62212.62213"},{"issue":"1","key":"9473_CR9","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R Canetti","year":"2000","unstructured":"R.\u00a0Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143\u2013202, 2000.","journal-title":"J. Cryptol."},{"key":"9473_CR10","doi-asserted-by":"crossref","unstructured":"R.\u00a0Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS) (2001), pp. 136\u2013145","DOI":"10.1109\/SFCS.2001.959888"},{"issue":"2","key":"9473_CR11","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/358549.358563","volume":"24","author":"D Chaum","year":"1981","unstructured":"D.\u00a0Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM, 24(2):84\u201388, 1981.","journal-title":"Commun. ACM"},{"issue":"1","key":"9473_CR12","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF00206326","volume":"1","author":"D Chaum","year":"1988","unstructured":"D.\u00a0Chaum. The dining cryptographers problem: Unconditional sender and recipient untraceability. Journal of Cryptology, 1(1):65\u201375, 1988.","journal-title":"J. Cryptol."},{"key":"9473_CR13","doi-asserted-by":"crossref","unstructured":"D.\u00a0Chaum, C.\u00a0Cr\u00e9peau, and I.\u00a0Damg\u00e5rd. Multiparty unconditionally secure protocols (extended abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC) (1988), pp. 11\u201319","DOI":"10.1145\/62212.62214"},{"issue":"1","key":"9473_CR14","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0196-6774(82)90004-9","volume":"3","author":"D Dolev","year":"1982","unstructured":"D.\u00a0Dolev. The Byzantine generals strike again. J. Algorithms, 3(1):14\u201330, 1982.","journal-title":"J. Algorithms"},{"issue":"1","key":"9473_CR15","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/138027.138036","volume":"40","author":"D Dolev","year":"1993","unstructured":"D.\u00a0Dolev, C.\u00a0Dwork, O.\u00a0Waarts, and M.\u00a0Yung. Perfectly secure message transmission. Journal of the ACM, 40(1):17\u201347, 1993.","journal-title":"J. ACM"},{"issue":"3","key":"9473_CR16","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0304-3975(76)90086-4","volume":"2","author":"S Even","year":"1976","unstructured":"S.\u00a0Even and R.\u00a0E. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2(3):339\u2013344, 1976.","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9473_CR17","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0304-3975(77)90061-5","volume":"4","author":"S Even","year":"1977","unstructured":"S.\u00a0Even and R.\u00a0E. Tarjan. Corrigendum: Computing an st-numbering. Theor. Comput. Sci., 4(1):123, 1977","journal-title":"Theor. Comput. Sci."},{"key":"9473_CR18","unstructured":"Y.\u00a0Gertner, S.\u00a0Kannan, T.\u00a0Malkin, O.\u00a0Reingold, and M.\u00a0Viswanathan. The relationship between public key encryption and oblivious transfer. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS) (2000), pp. 325\u2013335"},{"key":"9473_CR19","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, S.\u00a0Micali, and A.\u00a0Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC) (1987), pp. 218\u2013229","DOI":"10.1145\/28395.28420"},{"key":"9473_CR20","doi-asserted-by":"crossref","unstructured":"I.\u00a0Haitner, K.\u00a0Nissim, E.\u00a0Omri, R.\u00a0Shaltiel, and J.\u00a0Silbak. Computational two-party correlation: A dichotomy for key-agreement protocols. In Proceedings of the 59th Annual Symposium on Foundations of Computer Science (FOCS) (2018), pp. 136\u2013147","DOI":"10.1109\/FOCS.2018.00022"},{"key":"9473_CR21","doi-asserted-by":"crossref","unstructured":"M.\u00a0Hirt, U.\u00a0Maurer, D.\u00a0Tschudi, and V.\u00a0Zikas. Network-hiding communication and applications to multi-party protocols. In 36th Annual International Cryptology Conference (CRYPTO), part II (2016), pp. 335\u2013365","DOI":"10.1007\/978-3-662-53008-5_12"},{"key":"9473_CR22","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Ishai, E.\u00a0Kushilevitz, R.\u00a0Ostrovsky, and A.\u00a0Sahai. Cryptography from anonymity. In Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS) (2006), pp. 239\u2013248","DOI":"10.1109\/FOCS.2006.25"},{"key":"9473_CR23","doi-asserted-by":"crossref","unstructured":"J.\u00a0Katz, U.\u00a0Maurer, B.\u00a0Tackmann, and V.\u00a0Zikas. Universally composable synchronous computation. In Proceedings of the 10th Theory of Cryptography Conference(TCC) (2013), pp. 477\u2013498","DOI":"10.1007\/978-3-642-36594-2_27"},{"key":"9473_CR24","doi-asserted-by":"crossref","unstructured":"J.\u00a0Kilian. A general completeness theorem for two-party games. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC) (1991), pp. 553\u2013560","DOI":"10.1145\/103418.103475"},{"issue":"3","key":"9473_CR25","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"L.\u00a0Lamport, R.\u00a0E. Shostak, and M.\u00a0C. Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382\u2013401, 1982.","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"9473_CR26","doi-asserted-by":"crossref","unstructured":"R.\u00a0LaVigne, C.\u00a0L. Zhang, U.\u00a0Maurer, T.\u00a0Moran, M.\u00a0Mularczyk, and D.\u00a0Tschudi. Topology-hiding computation beyond semi-honest adversaries. In Proceedings of the 16th Theory of Cryptography Conference(TCC), part II (2018), pp. 3\u201335","DOI":"10.1007\/978-3-030-03810-6_1"},{"key":"9473_CR27","doi-asserted-by":"crossref","unstructured":"R.\u00a0LaVigne, C.\u00a0L. Zhang, U.\u00a0Maurer, T.\u00a0Moran, M.\u00a0Mularczyk, and D.\u00a0Tschudi. Topology-hiding computation for networks with unknown delays. In Proceedings of the 23rd International Conference on the Theory and Practice of Public-Key Cryptography (PKC), part II (2020), pp. 215\u2013245","DOI":"10.1007\/978-3-030-45388-6_8"},{"issue":"3","key":"9473_CR28","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/s00145-017-9267-7","volume":"31","author":"Y Lindell","year":"2018","unstructured":"Y.\u00a0Lindell, E.\u00a0Omri, and H.\u00a0Zarosim. Completeness for symmetric two-party functionalities: Revisited. Journal of Cryptology, 31(3):671\u2013697, 2018.","journal-title":"J. Cryptol."},{"key":"9473_CR29","doi-asserted-by":"crossref","unstructured":"T.\u00a0Moran, I.\u00a0Orlov, and S.\u00a0Richelson. Topology-hiding computation. In Proceedings of the 12th Theory of Cryptography Conference(TCC), part I (2015), pp. 159\u2013181","DOI":"10.1007\/978-3-662-46494-6_8"},{"issue":"2","key":"9473_CR30","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1145\/322186.322188","volume":"27","author":"MC Pease","year":"1980","unstructured":"M.\u00a0C. Pease, R.\u00a0E. Shostak, and L.\u00a0Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228\u2013234, 1980.","journal-title":"J. ACM"},{"key":"9473_CR31","doi-asserted-by":"crossref","unstructured":"T.\u00a0Rabin and M.\u00a0Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS) (1989), pp. 73\u201385","DOI":"10.1145\/73007.73014"},{"issue":"1","key":"9473_CR32","doi-asserted-by":"publisher","first-page":"85","DOI":"10.3233\/FI-1986-9105","volume":"9","author":"RE Tarjan","year":"1986","unstructured":"R.\u00a0E. Tarjan. Two streamlined depth-first search algorithms. Fundamenta Informaticae, 9(1):85\u201394, 1986.","journal-title":"Fundamenta Informaticae"},{"key":"9473_CR33","doi-asserted-by":"crossref","unstructured":"A.\u00a0C. Yao. Protocols for secure computations (extended abstract). In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS) (1982), pp. 160\u2013164","DOI":"10.1109\/SFCS.1982.38"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09473-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-023-09473-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09473-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T16:04:19Z","timestamp":1698163459000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-023-09473-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,12]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["9473"],"URL":"https:\/\/doi.org\/10.1007\/s00145-023-09473-3","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,12]]},"assertion":[{"value":"29 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"39"}}