Abstract
We consider a setting where there are two parties, each party holds a private graph and they wish to jointly compute the structural dissimilarity between two graphs without revealing any information about their private input graph. Graph edit distance (GED) is a widely accepted metric for measuring the dissimilarity of graphs. It measures the minimum cost for transforming one graph into the other graph by applying graph edit operations. In this paper we present a framework for securely computing approximated GED and as an example, present a protocol based on threshold additive homomorphic encryption scheme. We develop several new sub-protocols such as private maximum computation and optimal assignment protocols to construct the main protocol. We show that our protocols are secure against semi-honest adversaries. The asymptotic complexity of the protocol is \(O(n^5\ell \log ^*(\ell ))\) where \(\ell \) is the bit length of ring elements and n is the number of nodes in the graph.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aggarwal, C.C., Wang, H.: Managing and Mining Graph Data. Springer, US (2010)
Aly, A., Cuvelier, E., Mawet, S., Pereira, O., Vyve, M.: Securely solving simple combinatorial graph problems. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 239–257. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39884-1_21
Atallah, M.J., Kerschbaum, F., Wenliang, D.: Secure and private sequence comparisons. In: Proceedings of the 2003 ACM Workshop on Privacy in the Electronic Society, WPES 2003, pp. 39–44. ACM, New York (2003)
Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS 2012, pp. 784–796. ACM, New York (2012)
Blanton, M., Saraph, S.: Oblivious maximum bipartite matching size algorithm with applications to secure fingerprint identification. In: Pernul, G., Ryan, P.Y.A., Weippl, E. (eds.) ESORICS 2015. LNCS, vol. 9326, pp. 384–406. Springer, Heidelberg (2015). doi:10.1007/978-3-319-24174-6_20
Blanton, M., Steele, A., Alisagari, M.: Data-oblivious graph algorithms for secure computation and outsourcing. In: Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security, ASIA CCS 2013, pp. 207–218. ACM, New York (2013)
Cheon, J.H., Kim, M., Lauter, K.: Homomorphic computation of edit distance. In: Brenner, M., Christin, N., Johnson, B., Rohloff, K. (eds.) FC 2015. LNCS, vol. 8976, pp. 194–212. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48051-9_15
Damgård, I., Fitzi, M., Kiltz, E., Nielsen, J.B., Toft, T.: Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 285–304. Springer, Heidelberg (2006). doi:10.1007/11681878_15
Fankhauser, S., Riesen, K., Bunke, H.: Speeding up graph edit distance computation through fast bipartite matching. In: Jiang, X., Ferrer, M., Torsello, A. (eds.) GbRPR 2011. LNCS, vol. 6658, pp. 102–111. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20844-7_11
Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24676-3_1
Gentry, C., Halevi, S., Jutla, C.S., Raykova, M.: Private database access with he-over-oram architecture. IACR Cryptology ePrint Archive 2014, 345 (2014)
Goldreich, O.: Foundations of Cryptography Volume II Basic Applications, vol. II. Cambridge University Press, New York (2004)
Hazay, C., Mikkelsen, G.L., Rabin, T., Toft, T.: Efficient RSA key generation and threshold paillier in the two-party setting. In: Dunkelman, O. (ed.) CT-RSA 2012. LNCS, vol. 7178, pp. 313–331. Springer, Heidelberg (2012). doi:10.1007/978-3-642-27954-6_20
Henecka, W., Stefan, K., Sadeghi, A.-R., Schneider, T., Wehrenberg, I.: Tasty: tool for automating secure two-party computations. In: Proceedings of the 17th ACM Conference on Computer and Communications Security, CCS 2010, pp. 451–462. ACM, New York (2010)
Huang, Y., Evans, D., Katz, J., Malka, L.: Faster secure two-party computation using garbled circuits. In: Proceedings of the 20th USENIX Conference on Security, SEC 2011, pp. 35–35. USENIX Association, Berkeley (2011)
Jha, S., Kruger, L., Shmatikov, V.: Towards practical privacy for genomic computation. In: Proceedings of the 2008 IEEE Symposium on Security and Privacy, SP 2008, pp. 216–230. IEEE Computer Society, Washington, DC (2008)
Lindell, Y., Pinkas, B.: An efficient protocol for secure two-party computation in the presence of malicious adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72540-4_4
Lipmaa, H., Toft, T.: Secure equality and greater-than tests with sublinear online complexity. In: Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Part II, Riga, Latvia, 8–12 July 2013, pp. 645–656 (2013)
Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay–a secure two-party computation system. In: Proceedings of the 13th Conference on USENIX Security Symposium, SSYM 2004, vol. 13, p. 20. USENIX Association, Berkeley (2004)
Maltoni, D., Maio, D., Jain, A.K., Prabhakar, S.: Handbook of Fingerprint Recognition, 2nd edn. Springer Publishing Company, London (2009)
Mandal, K., Alomair, B., Poovendran, R.: Secure error-tolerant graph matching protocols. Cryptology ePrint Archive, Report 2016/908 (2016). http://eprint.iacr.org/
Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5(1), 32–38 (1957)
Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2001, pp. 448–457. Society for Industrial and Applied Mathematics, Philadelphia (2001)
Neuhaus, M., Bunke, H.: A graph matching based approach to fingerprint classification using directional variance. In: Kanade, T., Jain, A., Ratha, N.K. (eds.) AVBPA 2005. LNCS, vol. 3546, pp. 191–200. Springer, Heidelberg (2005). doi:10.1007/11527923_20
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). doi:10.1007/3-540-48910-X_16
Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image Vision Comput. 27(7), 950–959 (2009)
Toft, T.: Sub-linear, secure comparison with two non-colluding parties. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 174–191. Springer, Heidelberg (2011). doi:10.1007/978-3-642-19379-8_11
Yao, A.C.-C: How to generate and exchange secrets. In: Proceedings of the 27th Annual Symposium on Foundations of Computer Science, SFCS 1986, pp. 162–167. IEEE Computer Society, Washington, DC (1986)
Zeng, Z., Tung, A.K.H., Wang, J., Feng, J., Zhou, L.: Comparing stars: on approximating graph edit distance. Proc. VLDB Endow. 2(1), 25–36 (2009)
Acknowledgement
This work was supported by ONR grant N00014-14-1-0029 and a grant from the King Abdulaziz City for Science and Technology (KACST). The authors would like to thank Seny Kamara for conducting several discussions during the initial phase of this work. The authors also thank the anonymous reviewers of CANS 2016 for bringing the references [3, 16] into our attention and for their helpful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
A Description of Sub-protocols
1.1 A.1 Encrypted Equality Test Protocol and Comparison Protocol
Given encryptions \(\text {Enc}(y_1)\) and \(\text {Enc}(y_2)\) of \(y_1\) and \(y_2\), respectively, where \(y_1\) and \(y_2\) are of \(\ell \)-bit numbers in \({\mathbb Z}_{N}\). In our setting, the secure equality testing protocol outputs the encrypted value \(\text {Enc}(b)\) where \(b = 0\) if \(y_1 \ne y_2\) and \(b = 1\) if \(y_1 = y_2\), without revealing \(y_1\), \(y_2\) and b where \(y_1\) and \(y_2\) are of \(\ell \) bits. Our equality testing protocol is based on the idea of plaintext-space reduction introduced in [11], which can also be found in [18]. The setting of the equality check is different from the one proposed in [11]. In our case, the private key is shared between the parties, but in [11], one party holds the private key and the other party holds the encrypted numbers. We describe a secure encrypted equality test protocol based on plaintext-space reduction in Fig. 5. We use the greater-than protocol of Toft [27] with the modification that we replace the equality test protocol by \(\pi _{\textsf {EQ}}\). We denote this protocol by \(\pi _{\textsf {CMP}}\) which takes inputs \(\text {Enc}(x)\) and \(\text {Enc}(y)\) and outputs \(\text {Enc}(b)\) where \(b = 1\) iff \(x \ge y\) and \(b = 0\), otherwise. Its round complexity is \(O(\log (\ell ))\) and computation complexity is \(O(\ell \log (\ell )\log ^*(\ell ))\).
Protocol for equality of encrypted numbers using Paillier threshold encryption
1.2 A.2 Substitution Cost Protocol
Figure 6 presents the protocol for computing the substitution cost for constructing the cost matrix. The proof of the security of the protocols can be found in the full paper.
Protocol for computing node substitution cost \(c( u_i \rightarrow v_j)\)
B Graph Edit Operations and Cost Matrix
A standard set of graph edit operations are node insertion (\(\epsilon \rightarrow u\)), deletion (\(u \rightarrow \epsilon \)) and substitution (\(u \rightarrow v\)) and edge insertion (\(\epsilon \rightarrow e\)), deletion (\(e \rightarrow \epsilon \)) and substitution (\(e_1 \rightarrow e_2\)) and substitution of node and edge labels where \(\epsilon \) denotes empty nodes or edges. The edge edit operations can be defined in terms of the node edit operations as follows. Let \(e_1 = (u_1, u_2) \in E_1\) and \(e_2 = (v_1, v_2) \in E_2\) where \(u_1, u_2 \in V_1\cup \{\epsilon \}\) and \(v_1, v_2 \in V_2\cup \{\epsilon \}\). An edge substitution operation between \(e_1\) and \(e_2\), denoted by \(e_1 \rightarrow e_2\), is defined as the node substitution operations \(u_1 \rightarrow v_1\) and \(u_2 \rightarrow v_2\). If there is no edge \(e_1\) in \(E_1\) and \(e_2 \in E_2\), then the edge insertion in \(G_1\), denoted by \((\epsilon \rightarrow e_2)\) is defined by \(\epsilon \rightarrow v_1\) and \(\epsilon \rightarrow v_2\). Similarly, if there is an edge \(e_1 \in E_1\) and no edge \(e_2\) in \(E_2\), then the edge deletion, denoted by \((e_1 \rightarrow \epsilon )\) is defined by \(u_1 \rightarrow \epsilon \) and \(v_2 \rightarrow \epsilon \).
The cost matrix is constructed by considering substitution costs of vertices and the costs of vertex insertions and deletions. The structure of the edit cost matrix \(W = (w_{ij})_{(n+m)\times (n+m)}\) has the following form [26]:
where the submatrix \(W_1\) is corresponding to the cost assignment of nodes \((i \rightarrow j)\), \(W_2\) and \(W_3\) are corresponding to the cost assignment of node deletion \((i \rightarrow \epsilon )\) and insertion \((\epsilon \rightarrow i)\) of nodes. The insertion and deletion of edges are not taken care of in the cost matrix. However, it is not hard to incorporate the edge substitution cost into the matrix entries. We omit the details here.
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Mandal, K., Alomair, B., Poovendran, R. (2016). Secure Error-Tolerant Graph Matching Protocols. In: Foresti, S., Persiano, G. (eds) Cryptology and Network Security. CANS 2016. Lecture Notes in Computer Science(), vol 10052. Springer, Cham. https://doi.org/10.1007/978-3-319-48965-0_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-48965-0_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-48964-3
Online ISBN: 978-3-319-48965-0
eBook Packages: Computer ScienceComputer Science (R0)