TR2010-109

Privacy Preserving String Comparisons Based on Levenshtein Distance


    •  Rane, S., Sun, W., "Privacy Preserving String Comparisons Based on Levenshtein Distance", IEEE International Workshop on Information Forensics and Security (WIFS), December 2010, pp. 1-6.
      BibTeX TR2010-109 PDF
      • @inproceedings{Rane2010dec1,
      • author = {Rane, S. and Sun, W.},
      • title = {Privacy Preserving String Comparisons Based on Levenshtein Distance},
      • booktitle = {IEEE International Workshop on Information Forensics and Security (WIFS)},
      • year = 2010,
      • pages = {1--6},
      • month = dec,
      • isbn = {978-1-4244-9078-3},
      • url = {https://www.merl.com/publications/TR2010-109}
      • }
  • Research Area:

    Information Security

Abstract:

Alice and Bob possess strings x and y of length m and n respectively and want to compute the Levenshtein distance L(x, y) between the strings under privacy and communication constraints. The Levenshtein distance, or edit distance, has a dynamic programming formulation that solves a series of minimumfinding problems. Based on this formulation, there are known symmetric privacy-preserving protocols for the computation of L(x, y), in which the two parties incur equal protocol overhead. In this work, we propose an asymmetric two-party protocol in which a lightweight client Bob with a string y interacts with a single powerful server Alice containing string x in its database. We present a privacy-preserving minimum-finding protocol based on semantically secure homomorphic functions and additive secret sharing. This protocol is executed repeatedly, to enable private computation of the edit distance. Our protocol supports arbitrary finite insertion/deletion costs and a variety of substitution costs. While Alice requires similar effort as in previous approaches, the advantage is that Bob incurs far fewer ciphertext operations and transmissions, making the protocol well-suited for client-server querying applications.

 

  • Related News & Events

    •  NEWS    WIFS 2010: publication by Wei Sun and Shantanu D. Rane
      Date: December 12, 2010
      Where: IEEE International Workshop on Information Forensics and Security (WIFS)
      Research Area: Information Security
      Brief
      • The paper "Privacy Preserving String Comparisons Based on Levenshtein Distance" by Rane, S. and Sun, W. was presented at the IEEE International Workshop on Information Forensics and Security (WIFS).
    •