Secure Error-Tolerant Graph Matching Protocols

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.

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 ))$.

Fig. 5.

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.

Fig. 6.

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]:

$$\begin{aligned} C = \left[ \begin{array}{cccc | cccc} w_{11} &{} w_{12} &{} \cdots &{} w_{1m} &{} w_{1\epsilon } &{} \infty &{} \cdots &{} \infty \\ \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots \\ w_{n1} &{} w_{n2} &{} \cdots &{} w_{nm} &{} \infty &{} \infty &{} \cdots &{} w_{n\epsilon } \\ \hline \infty &{} w_{\epsilon 2} &{} \cdots &{} \infty &{} 0 &{} 0 &{} \cdots &{} 0 \\ \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots \\ \infty &{} \infty &{} \cdots &{} w_{\epsilon m} &{} 0 &{} 0 &{} \cdots &{} 0 \\ \end{array} \right] = \left[ \begin{array}{ c c} W_1 &{} W_2 \\ W_3 &{} W_4 \end{array} \right] \end{aligned}$$

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.