Topology-hiding computation on all graphs. (English) Zbl 1455.94103
Summary: A distributed computation in which nodes are connected by a partial communication graph is called topology hiding if it does not reveal information about the graph beyond what is revealed by the output of the function. Previous results have shown that topology-hiding computation protocols exist for graphs of constant degree and logarithmic diameter in the number of nodes [T. Moran et al., TCC 2015, Lect. Notes Comput. Sci. 9014, 159–181 (2015; Zbl 1354.94041); M. Hirt et al., Crypto 2016, Lect. Notes Comput. Sci. 9815, 335–365 (2016; Zbl 1391.94759)] as well as for other graph families, such as cycles, trees, and low circumference graphs [A. Akavia and T. Moran, Eurocrypt 2017, Lect. Notes Comput. Sci. 10212, 609–637 (2017; Zbl 1415.94400), but the feasibility question for general graphs was open. In this work, we positively resolve the above open problem: we prove that topology-hiding computation is feasible for all graphs under either the decisional Diffie-Hellman or quadratic residuosity assumption. Our techniques employ random or deterministic walks to generate paths covering the graph, upon which we apply the Akavia-Moran topology-hiding broadcast for chain graphs (paths). To prevent topology information revealed by the random walk, we design multiple graph-covering sequences that, together, are locally identical to receiving at each round a message from each neighbor and sending back a processed message from some neighbor (in a randomly permuted order).
The preliminary version appeared in [Crypto 2017, Lect. Notes Comput. Sci. 10401, 447–467 (2017; Zbl 1407.94067)].
Keywords:
secure multiparty computation; topology-hiding computation; random walks; networks; broadcastReferences:
| [1] | Akavia, Adi; Lavigne, Rio; Moran, Tal, Topology-Hiding Computation on All Graphs, Advances in Cryptology - CRYPTO 2017, 447-467 (2017), Cham: Springer International Publishing, Cham · Zbl 1407.94067 |
| [2] | Akavia, Adi; Moran, Tal, Topology-Hiding Computation Beyond Logarithmic Diameter, Lecture Notes in Computer Science, 609-637 (2017), Cham: Springer International Publishing, Cham · Zbl 1415.94400 |
| [3] | 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 ’79 (IEEE Computer Society, Washington, DC, USA, 1979), pp. 218-223 |
| [4] | M. Ball, E. Boyle, T. Malkin, T. Moran, Exploring the boundaries of topology-hiding computation, in Advances in Cryptology—EUROCRYPT 2018—37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part III (2018), pp. 294-325 · Zbl 1415.94405 |
| [5] | Balogh, J.; Bollobs, B.; Krivelevich, M.; Mller, T.; Walters, M., Hamilton cycles in random geometric graphs, Ann. Appl. Probab., 21, 3, 1053-1072 (2011) · Zbl 1222.05235 · doi:10.1214/10-AAP718 |
| [6] | A. Beimel, A. Gabizon, Y. Ishai, E. Kushilevitz, S. Meldgaard, A. Paskin-Cherniavsky, Non-interactive secure multiparty computation, in J.A. Garay, R. Gennaro, editors, Advances in Cryptology—CRYPTO 2014—34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part II, Lecture Notes in Computer Science, vol. 8617 (Springer, 2014), pp. 387-404 · Zbl 1335.94030 |
| [7] | R. Canetti, Universally composable security: A new paradigm for cryptographic protocols, in FOCS (IEEE Computer Society, 2001), pp. 136-145 |
| [8] | 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 ’89 (ACM, New York, NY, USA, 1989), pp. 574-586 · Zbl 0905.60049 |
| [9] | 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 ’15 (ACM, New York, NY, USA, 2015), pp. 153-162 · Zbl 1365.68255 |
| [10] | Clear, Michael; Hughes, Arthur; Tewari, Hitesh, Homomorphic Encryption with Access Policies: Characterization and New Constructions, Progress in Cryptology - AFRICACRYPT 2013, 61-87 (2013), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1312.94040 |
| [11] | Cocks, Clifford, An Identity Based Encryption Scheme Based on Quadratic Residues, Cryptography and Coding, 360-363 (2001), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 0999.94532 |
| [12] | 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-270 |
| [13] | Friedrich, T.; Sauerwald, T.; Stauffer, A., Diameter and broadcast time of random geometric graphs in arbitrary dimensions, Algorithmica, 67, 1, 65-88 (2013) · Zbl 1275.05050 · doi:10.1007/s00453-012-9710-y |
| [14] | Goldreich, O., Foundations of Cryptography: Basic Applications (2004), New York, NY, USA: Cambridge University Press, New York, NY, USA · Zbl 1068.94011 |
| [15] | Goldreich, O., Foundations of Cryptography: Basic Applications (2004), New York, NY, USA: Cambridge University Press, New York, NY, USA · Zbl 1068.94011 |
| [16] | 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 ’87 (ACM, New York, NY, USA, 1987), pp. 218-229 |
| [17] | 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. Oswald, editors, Advances in Cryptology—EUROCRYPT 2014—33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8441 (Springer, 2014), pp. 578-602 · Zbl 1327.94048 |
| [18] | S.D. Gordon, T. Malkin, M. Rosulek, H. Wee, Multi-party computation of polynomials and branching programs without simultaneous interaction, in Advances in Cryptology—EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings (2013), pp. 575-591 · Zbl 1312.94052 |
| [19] | 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 ’16 (ACM, New York, NY, USA, 2016), pp. 157-168 · Zbl 1334.94081 |
| [20] | Halevi, Shai; Lindell, Yehuda; Pinkas, Benny, Secure Computation on the Web: Computing without Simultaneous Interaction, Advances in Cryptology - CRYPTO 2011, 132-150 (2011), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1287.94070 |
| [21] | Hinkelmann, Markus; Jakoby, Andreas, Communications in unknown networks: Preserving the secret of topology, Theoretical Computer Science, 384, 2-3, 184-200 (2007) · Zbl 1125.68047 · doi:10.1016/j.tcs.2007.04.031 |
| [22] | Hirt, Martin; Maurer, Ueli; Tschudi, Daniel; Zikas, Vassilis, Network-Hiding Communication and Applications to Multi-party Protocols, Advances in Cryptology - CRYPTO 2016, 335-365 (2016), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1391.94759 |
| [23] | M. Joye, Identity-based cryptosystems and quadratic residuosity, in Public-Key Cryptography—PKC 2016—19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part I (2016), pp. 225-254 · Zbl 1388.94062 |
| [24] | Kahn, Jd; Linial, N.; Nisan, N.; Saks, Me, On the cover time of random walks on graphs, J. Theor. Probab., 2, 1, 121-128 (1989) · Zbl 0681.60064 · doi:10.1007/BF01048274 |
| [25] | M. Koucky, On Traversal Sequences, Exploration Sequences and Completeness of Kolmogorov Random Strings. Ph.D. thesis, New Brunswick, NJ, USA, AAI3092958 (2003). |
| [26] | Lavigne, R., Simple homomorphisms of cocks IBE and applications, IACR Cryptol. ePrint Arch., 2016, 1150 (2016) |
| [27] | R. LaVigne, C.L. Zhang, U. Maurer, T. Moran, M. Mularczyk, D. Tschudi, Topology-hiding computation beyond semi-honest adversaries, in Theory of Cryptography—16th International Conference, TCC 2018, Panaji, India, November 11-14, 2018, Proceedings, Part II (2018), pp. 3-35 · Zbl 1430.94078 |
| [28] | Mitzenmacher, M.; Upfal, E., Probability and Computing—Randomized Algorithms and Probabilistic Analysis (2005), Cambridge: Cambridge University Press, Cambridge · Zbl 1092.60001 |
| [29] | T. Moran, I. Orlov, S. Richelson, Topology-hiding computation, in Y. Dodis, J. B. Nielsen, editors, TCC 2015, Lecture Notes in Computer Science, vol. 9014 (Springer, 2015), pp. 169-198 · Zbl 1354.94041 |
| [30] | M. Penrose, Random geometric graphs, vol. 5 (Oxford University Press, 2003) · Zbl 1029.60007 |
| [31] | Pottie, Gj; Kaiser, Wj, Wireless integrated network sensors, Commun. ACM, 43, 5, 51-58 (2000) · doi:10.1145/332833.332838 |
| [32] | 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-24, 2005 (2005), pp. 84-93 · Zbl 1192.94106 |
| [33] | Reingold, O., Undirected connectivity in log-space, J. ACM, 55, 4, 17:1-17:24 (2008) · Zbl 1315.68156 · doi:10.1145/1391289.1391291 |
| [34] | P. Rogaway, editor. Advances in Cryptology—CRYPTO 2011—31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6841 (Springer, 2011) · Zbl 1290.94139 |
| [35] | A.C.-C. Yao, How to generate and exchange secrets, in Proceedings of the 27th Annual Symposium on Foundations of Computer Science, SFCS ’86 (IEEE Computer Society, Washington, DC, USA, 1986), pp. 162-167 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
