Secure Error-Tolerant Graph Matching Protocols

Kalikinkar Mandal, Basel Alomair, Radha Poovendran

TL;DR

This paper introduces a novel framework and protocol for two parties to securely compute the graph edit distance (GED) between their private graphs without revealing any information about the graphs themselves. This is achieved through a combination of secure multi-party computation techniques and a specialized protocol for optimal assignment, enabling privacy-preserving structural similarity analysis.

What Problem Does This Paper Address?

Graph matching, and specifically graph edit distance (GED), is a crucial metric for quantifying the structural dissimilarity between graphs. This has applications in areas like pattern recognition, biometrics (e.g., fingerprint identification), and social network analysis. However, computing GED typically requires access to the full graph structures, which can be sensitive private information. The challenge is to enable two parties, each holding a private graph, to jointly compute their GED without either party learning anything about the other's graph beyond the final GED value. This is a significant privacy concern in collaborative data analysis scenarios.

Methods

The authors propose a general framework for secure GED computation, which involves three main phases:

  1. Secure Cost Matrix Construction: Parties jointly compute the entries of a cost matrix that represents the costs of various graph edit operations (node/edge insertion, deletion, substitution).
  2. Secure Optimal Assignment: A secure protocol is used to solve the assignment problem based on the computed cost matrix, aiming to find the minimum cost assignment of nodes between the two graphs. This is a core sub-problem for GED.
  3. Optional Processing: Further steps to refine the GED if needed.

As a concrete example, they develop a protocol based on the Riesen and Bunke algorithm [26], which utilizes bipartite matching. The protocol relies on threshold additive homomorphic encryption, specifically the threshold Paillier encryption scheme [13, 25]. Key novel sub-protocols developed include:

  • Private Maximum Computation (PMC) protocol: To securely find the maximum value and its index from encrypted vectors.
  • Optimal Assignment (OA) protocol: Based on the Hungarian algorithm, this protocol securely computes the optimal assignment value on an encrypted cost matrix.

The security is proven in the semi-honest model, where adversaries follow the protocol but try to learn extra information.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and protocol for secure computation on private graph inputs, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Privacy-Preserving GED is Achievable: The paper demonstrates that it's possible to compute a meaningful measure of graph dissimilarity (GED) between private graphs without compromising privacy.
  • Decomposition into Secure Sub-problems: The core idea is to break down the GED computation into smaller, manageable secure sub-protocols (cost matrix, assignment) that can be solved using existing and novel cryptographic techniques.
  • Leveraging Homomorphic Encryption for GED: The use of threshold additive homomorphic encryption is crucial for enabling computations on encrypted graph data, particularly for operations like addition and multiplication required in GED algorithms.
  • Novel Secure Sub-protocols: The development of secure protocols for private maximum computation and optimal assignment is a significant contribution, enabling the secure execution of the GED algorithm.
  • Hungarian Algorithm in a Secure Setting: Adapting and securing the Hungarian algorithm for bipartite matching is a key technical challenge addressed by the OA protocol.

Key Results

  • Secure Protocol for Approximated GED: The paper presents a protocol that securely computes an approximated graph edit distance in the semi-honest model.
  • Asymptotic Complexity: The proposed protocol has an asymptotic complexity of $O(n^5 l \log^*(l))$, where $l$ is the bit length of ring elements and $n$ is the number of nodes in the graphs. This indicates a polynomial time complexity, which is expected for graph algorithms.
  • Security Proof: The protocol is proven secure against semi-honest adversaries using a hybrid model and simulator-based approach.

Limitations and Future Work

  • Semi-Honest Model: The security is proven only in the semi-honest model. Extending this to the malicious model, where adversaries can deviate from the protocol, would be a significant next step.
  • Approximated GED: The protocol computes an approximated graph edit distance. While this is often sufficient in practice, exact GED computation in a secure setting remains a harder problem.
  • Complexity: The $O(n^5)$ complexity, while polynomial, can be computationally intensive for very large graphs. Future work might focus on optimizing this complexity.
  • Edge Operations: The paper primarily focuses on node edit operations for cost matrix construction, noting that edge operations can be incorporated but not detailing their secure computation.
  • Practical Efficiency: While theoretically sound, the practical efficiency of the protocol would depend on the performance of the underlying homomorphic encryption and secure multi-party computation primitives.

Summary updated

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.
BibTeX
@article{mandal2016secure,
  author = {Kalikinkar Mandal and Basel Alomair and Radha Poovendran},
  title = {{Secure Error-Tolerant Graph Matching Protocols}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2016},
}
Figure