Secure and Private Sequence Comparisons

Mikhail J. Atallah, Florian Kerschbaum, Wenliang Du

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

129 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

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

Fingerprint Dive into the research topics of 'Secure and Private Sequence Comparisons'. Together they form a unique fingerprint.

  • 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).