Paper 2016/908

Secure Error-Tolerant Graph Matching Protocols

Kalikinkar Mandal, Basel Alomair, and Radha Poovendran


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. CANS-2016
Secure two-partycomputationGraph edit distancePrivacyGraph algorithms
Contact author(s)
kmandal @ uwaterloo ca
2016-09-19: received
Short URL
Creative Commons Attribution


      author = {Kalikinkar Mandal and Basel Alomair and Radha Poovendran},
      title = {Secure Error-Tolerant Graph Matching Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2016/908},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.