Secure and Private Sequence Comparisons

Mikhail J. Atallah, Florian Kerschbaum, Wenliang Du

Research output: Chapter in Book/Report/Conference proceedingConference contribution

126 Scopus citations

Abstract

We give an efficient protocol for sequence comparisons of the edit-distance kind, such that neither party reveals anything about their private sequence to the other party (other than what can be inferred from the edit distance between their two sequences - which is unavoidable because computing that distance is the purpose of the protocol). The amount of communication done by our protocol is proportional to the time complexity of the best-known algorithm for performing the sequence comparison. The problem of determining the similarity between two sequences arises in a large number of applications, in particular in bioinformatics. In these application areas, the edit distance is one of the most widely used notions of sequence similarity: It is the least-cost set of insertions, deletions, and substitutions required to transform one string into the other. The generalizations of edit distance that are solved by the same kind of dynamic programming recurrence relation as the one for edit distance, cover an even wider domain of applications.

Original languageEnglish (US)
Title of host publicationProceedings of the 2003 ACM Workshop on Privacy in the Electronic Society, WPES 2003
EditorsP. Samarati, P. Syverson, P. Samarati, P. Syverson
Pages39-44
Number of pages6
StatePublished - Dec 1 2003
EventProceedings of the 2003 ACM Workshop on Privacy in the Electronic Society, WPES 2003 - Washington, DC, United States
Duration: Oct 30 2003Oct 30 2003

Publication series

NameProceedings of the ACM Workshop on Privacy in the Electronic Society

Other

OtherProceedings of the 2003 ACM Workshop on Privacy in the Electronic Society, WPES 2003
CountryUnited States
CityWashington, DC
Period10/30/0310/30/03

    Fingerprint

Keywords

  • Dynamic programming
  • Edit distance
  • Longest common subsequence
  • Privacy
  • Secure multi-party computation
  • String matching

ASJC Scopus subject areas

  • Human-Computer Interaction
  • Computer Networks and Communications

Cite this

Atallah, M. J., Kerschbaum, F., & Du, W. (2003). Secure and Private Sequence Comparisons. In P. Samarati, P. Syverson, P. Samarati, & P. Syverson (Eds.), Proceedings of the 2003 ACM Workshop on Privacy in the Electronic Society, WPES 2003 (pp. 39-44). (Proceedings of the ACM Workshop on Privacy in the Electronic Society).