Paper 2017/683

Efficient Privacy-Preserving General Edit Distance and Beyond

Ruiyu Zhu and Yan Huang

Abstract

Edit distance is an important non-linear metric that has many applications ranging from matching patient genomes to text-based intrusion detection. Depends on the application, related string-comparison metrics, such as weighted edit distance, Needleman-Wunsch distance, longest common subsequences, and heaviest common subsequences, can usually fit better than the basic edit distance. When these metrics need to be calculated on sensitive input strings supplied by mutually distrustful parties, it is more desirable but also more challenging to compute them in privacy-preserving ways. In this paper, we propose efficient secure computation protocols for private edit distance as well as several generalized applications including weighted edit distance (with potentially content-dependent weights), longest common subsequence, and heaviest common subsequence. Our protocols run 20+ times faster and use an order-of-magnitude less bandwidth than their best previous counterparts. Along- side, we propose a garbling scheme that allows free arithmetic addition, free multiplication with constants, and low-cost comparison/minimum for inputs of restricted relative-differences. Moreover, the encodings (i.e. wire-labels) in our garbling scheme can be converted from and to encodings used by traditional binary circuit garbling schemes with light to moderate costs. Therefore, while being extremely efficient on certain kinds of computations, the new garbling scheme remains composable and capable of handling generic computational tasks.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
secure edit distancesecure weighted edit distancesecure longest common subsequencesecure heaviest common subsequence
Contact author(s)
yh33 @ indiana edu
History
2017-08-01: last of 2 revisions
2017-07-18: received
See all versions
Short URL
https://ia.cr/2017/683
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/683,
      author = {Ruiyu Zhu and Yan Huang},
      title = {Efficient Privacy-Preserving General Edit Distance and Beyond},
      howpublished = {Cryptology ePrint Archive, Paper 2017/683},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/683}},
      url = {https://eprint.iacr.org/2017/683}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.