{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T04:26:31Z","timestamp":1769315191154,"version":"3.49.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T00:00:00Z","timestamp":1552608000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00145-019-09318-y","type":"journal-article","created":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T15:04:07Z","timestamp":1552662247000},"page":"176-227","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Topology-Hiding Computation on All Graphs"],"prefix":"10.1007","volume":"33","author":[{"given":"Adi","family":"Akavia","sequence":"first","affiliation":[]},{"given":"Rio","family":"LaVigne","sequence":"additional","affiliation":[]},{"given":"Tal","family":"Moran","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,3,15]]},"reference":[{"key":"9318_CR1","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/978-3-319-63688-7_15","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"Adi Akavia","year":"2017","unstructured":"A. Akavia, R. LaVigne, T. Moran, Topology-hiding computation on all graphs, in Advances in Cryptology\u2014CRYPTO 2017\u201437th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20\u201324, 2017, Proceedings, Part I (2017), pp. 447\u2013467"},{"key":"9318_CR2","first-page":"609","volume-title":"Lecture Notes in Computer Science","author":"Adi Akavia","year":"2017","unstructured":"A. Akavia, T. Moran, Topology-hiding computation beyond logarithmic diameter, in Advances in Cryptology\u2014EUROCRYPT 2017\u201436th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30\u2013May 4, 2017, Proceedings, Part III (2017), pp. 609\u2013637"},{"key":"9318_CR3","doi-asserted-by":"crossref","unstructured":"R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz, C. Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, in Proceedings of the 20th Annual Symposium on Foundations of Computer Science, SFCS \u201979 (IEEE Computer Society, Washington, DC, USA, 1979), pp. 218\u2013223","DOI":"10.1109\/SFCS.1979.34"},{"key":"9318_CR4","unstructured":"M. Ball, E. Boyle, T. Malkin, T. Moran, Exploring the boundaries of topology-hiding computation, in Advances in Cryptology\u2014EUROCRYPT 2018\u201437th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29\u2013May 3, 2018 Proceedings, Part III (2018), pp. 294\u2013325"},{"issue":"3","key":"9318_CR5","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.1214\/10-AAP718","volume":"21","author":"J Balogh","year":"2011","unstructured":"J. Balogh, B. Bollobs, M. Krivelevich, T. Mller, M. Walters. Hamilton cycles in random geometric graphs. Ann. Appl. Probab.21(3), 1053\u20131072 (2011)","journal-title":"Ann. Appl. Probab."},{"key":"9318_CR6","doi-asserted-by":"crossref","unstructured":"A. Beimel, A. Gabizon, Y. Ishai, E. Kushilevitz, S. Meldgaard, A. Paskin-Cherniavsky, Non-interactive secure multiparty computation, in J.A. Garay, R.\u00a0Gennaro, editors, Advances in Cryptology\u2014CRYPTO 2014\u201434th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17\u201321, 2014, Proceedings, Part II, Lecture Notes in Computer Science, vol. 8617 (Springer, 2014), pp. 387\u2013404","DOI":"10.1007\/978-3-662-44381-1_22"},{"key":"9318_CR7","doi-asserted-by":"crossref","unstructured":"R. Canetti, Universally composable security: A new paradigm for cryptographic protocols, in FOCS (IEEE Computer Society, 2001), pp. 136\u2013145","DOI":"10.1109\/SFCS.2001.959888"},{"key":"9318_CR8","doi-asserted-by":"crossref","unstructured":"A.K. Chandra, P. Raghavan, W.L. Ruzzo, R. Smolensky, The electrical resistance of a graph captures its commute and cover times, in Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, STOC \u201989 (ACM, New York, NY, USA, 1989), pp. 574\u2013586","DOI":"10.1145\/73007.73062"},{"key":"9318_CR9","doi-asserted-by":"crossref","unstructured":"N. Chandran, W. Chongchitmate, J.A. Garay, S. Goldwasser, R. Ostrovsky, V. Zikas, The hidden graph model: Communication locality and optimal resiliency with adaptive faults, in Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS \u201915 (ACM, New York, NY, USA, 2015), pp. 153\u2013162","DOI":"10.1145\/2688073.2688102"},{"key":"9318_CR10","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-38553-7_4","volume-title":"Progress in Cryptology \u2013 AFRICACRYPT 2013","author":"Michael Clear","year":"2013","unstructured":"M. Clear, A. Hughes, H. Tewari, Homomorphic Encryption with Access Policies: Characterization and New Constructions (Springer, Berlin, Heidelberg, 2013), pp. 61\u201387"},{"key":"9318_CR11","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/3-540-45325-3_32","volume-title":"Cryptography and Coding","author":"Clifford Cocks","year":"2001","unstructured":"C. Cocks, An identity based encryption scheme based on quadratic residues, in Proceedings of the 8th IMA International Conference on Cryptography and Coding (Springer-Verlag, London, UK, 2001), pp. 360\u2013363"},{"key":"9318_CR12","doi-asserted-by":"crossref","unstructured":"D. Estrin, R. Govindan, J. Heidemann, S. Kumar, Next century challenges: Scalable coordination in sensor networks, in Proceedings of the 5th Annual ACM\/IEEE International Conference on Mobile Computing and Networking (ACM, 1999), pp. 263\u2013270","DOI":"10.1145\/313451.313556"},{"issue":"1","key":"9318_CR13","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s00453-012-9710-y","volume":"67","author":"T Friedrich","year":"2013","unstructured":"T. Friedrich, T. Sauerwald, A. Stauffer, Diameter and broadcast time of random geometric graphs in arbitrary dimensions. Algorithmica67(1), 65\u201388 (2013)","journal-title":"Algorithmica"},{"key":"9318_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography: Basic Applications","author":"O Goldreich","year":"2004","unstructured":"O. Goldreich, Foundations of Cryptography: Basic Applications (Cambridge University Press, New York, NY, USA, 2004), vol.\u00a02"},{"key":"9318_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography: Basic Applications","author":"O Goldreich","year":"2004","unstructured":"O. Goldreich, Foundations of Cryptography: Basic Applications (Cambridge University Press, New York, NY, USA, 2004), vol. 2"},{"key":"9318_CR16","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, A. Wigderson, How to play any mental game, in Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC \u201987 (ACM, New York, NY, USA, 1987), pp. 218\u2013229","DOI":"10.1145\/28395.28420"},{"key":"9318_CR17","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, S.D. Gordon, V. Goyal, A. Jain, J. Katz, F. Liu, A. Sahai, E. Shi, H. Zhou, Multi-input functional encryption, in P.Q. Nguyen, E.\u00a0Oswald, editors, Advances in Cryptology\u2014EUROCRYPT 2014\u201433rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11\u201315, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8441 (Springer, 2014), pp. 578\u2013602","DOI":"10.1007\/978-3-642-55220-5_32"},{"key":"9318_CR18","unstructured":"S.D. Gordon, T. Malkin, M. Rosulek, H. Wee, Multi-party computation of polynomials and branching programs without simultaneous interaction, in Advances in Cryptology\u2014EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26\u201330, 2013. Proceedings (2013), pp. 575\u2013591"},{"key":"9318_CR19","doi-asserted-by":"crossref","unstructured":"S. Halevi, Y. Ishai, A. Jain, E. Kushilevitz, T. Rabin, Secure multiparty computation with general interaction patterns, in Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS \u201916 (ACM, New York, NY, USA, 2016), pp. 157\u2013168","DOI":"10.1145\/2840728.2840760"},{"key":"9318_CR20","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-642-22792-9_8","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"Shai Halevi","year":"2011","unstructured":"S. Halevi, Y. Lindell, B. Pinkas, Secure computation on the web: Computing without simultaneous interaction, in Rogaway [34], pp. 132\u2013150"},{"issue":"2-3","key":"9318_CR21","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.tcs.2007.04.031","volume":"384","author":"Markus Hinkelmann","year":"2007","unstructured":"M. Hinkelmann, A. Jakoby, Communications in unknown networks: Preserving the secret of topology. Theor. Comput. Sci., 384(2\u20133), 184\u2013200 (2007). Structural Information and Communication Complexity (SIROCCO 2005).","journal-title":"Theoretical Computer Science"},{"key":"9318_CR22","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-662-53008-5_12","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"Martin Hirt","year":"2016","unstructured":"M. Hirt, U. Maurer, D. Tschudi, V. Zikas, Network-hiding communication and applications to multi-party protocols, in Advances in Cryptology\u2014CRYPTO 2016\u201436th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14\u201318, 2016, Proceedings, Part II (2016), pp. 335\u2013365"},{"key":"9318_CR23","unstructured":"M. Joye, Identity-based cryptosystems and quadratic residuosity, in Public-Key Cryptography\u2014PKC 2016\u201419th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6\u20139, 2016, Proceedings, Part I (2016), pp. 225\u2013254"},{"issue":"1","key":"9318_CR24","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF01048274","volume":"2","author":"JD Kahn","year":"1989","unstructured":"J.D. Kahn, N. Linial, N. Nisan, M.E. Saks, On the cover time of random walks on graphs. J. Theor. Probab., 2(1), 121\u2013128 (1989)","journal-title":"J. Theor. Probab."},{"key":"9318_CR25","unstructured":"M. Koucky, On Traversal Sequences, Exploration Sequences and Completeness of Kolmogorov Random Strings. Ph.D. thesis, New Brunswick, NJ, USA, AAI3092958 (2003)."},{"key":"9318_CR26","first-page":"1150","volume":"2016","author":"R LaVigne","year":"2016","unstructured":"R.\u00a0LaVigne, Simple homomorphisms of cocks IBE and applications. IACR Cryptol. ePrint Arch., 2016, 1150 (2016)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"9318_CR27","unstructured":"R. LaVigne, C.L. Zhang, U. Maurer, T. Moran, M. Mularczyk, D. Tschudi, Topology-hiding computation beyond semi-honest adversaries, in Theory of Cryptography\u201416th International Conference, TCC 2018, Panaji, India, November 11\u201314, 2018, Proceedings, Part II (2018), pp. 3\u201335"},{"key":"9318_CR28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing\u2014Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"M. Mitzenmacher, E. Upfal, Probability and Computing\u2014Randomized Algorithms and Probabilistic Analysis (Cambridge University Press, Cambridge, 2005)"},{"key":"9318_CR29","unstructured":"T.\u00a0Moran, I.\u00a0Orlov, S.\u00a0Richelson, Topology-hiding computation, in Y.\u00a0Dodis, J.\u00a0B. Nielsen, editors, TCC 2015, Lecture Notes in Computer Science, vol. 9014 (Springer, 2015), pp. 169\u2013198"},{"key":"9318_CR30","doi-asserted-by":"crossref","unstructured":"M. Penrose, Random geometric graphs, vol.\u00a05 (Oxford University Press, 2003)","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"issue":"5","key":"9318_CR31","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/332833.332838","volume":"43","author":"GJ Pottie","year":"2000","unstructured":"G.J. Pottie, W.J. Kaiser, Wireless integrated network sensors. Commun. ACM, 43(5), 51\u201358 (2000)","journal-title":"Commun. ACM"},{"key":"9318_CR32","unstructured":"O. Regev, On lattices, learning with errors, random linear codes, and cryptography, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22\u201324, 2005 (2005), pp. 84\u201393"},{"issue":"4","key":"9318_CR33","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"O. Reingold, Undirected connectivity in log-space. J. ACM, 55(4), 17:1\u201317:24 (2008)","journal-title":"J. ACM"},{"key":"9318_CR34","doi-asserted-by":"crossref","unstructured":"P. Rogaway, editor. Advances in Cryptology\u2014CRYPTO 2011\u201431st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14\u201318, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6841 (Springer, 2011)","DOI":"10.1007\/978-3-642-22792-9"},{"key":"9318_CR35","unstructured":"A.C.-C. Yao, How to generate and exchange secrets, in Proceedings of the 27th Annual Symposium on Foundations of Computer Science, SFCS \u201986 (IEEE Computer Society, Washington, DC, USA, 1986), pp. 162\u2013167"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09318-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-019-09318-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09318-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,14]],"date-time":"2020-03-14T00:07:29Z","timestamp":1584144449000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-019-09318-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,15]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["9318"],"URL":"https:\/\/doi.org\/10.1007\/s00145-019-09318-y","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,15]]},"assertion":[{"value":"12 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}