@inproceedings{ac7cc88d875c4d52a74da32bbd814bd7,

title = "Secure and Private Sequence Comparisons",

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.",

keywords = "Dynamic programming, Edit distance, Longest common subsequence, Privacy, Secure multi-party computation, String matching",

author = "Atallah, {Mikhail J.} and Florian Kerschbaum and Wenliang Du",

year = "2003",

doi = "10.1145/1005140.1005147",

language = "English (US)",

isbn = "1581137761",

series = "Proceedings of the ACM Workshop on Privacy in the Electronic Society",

publisher = "Association for Computing Machinery",

pages = "39--44",

editor = "P. Samarati and P. Syverson",

booktitle = "Proceedings of the 2003 ACM Workshop on Privacy in the Electronic Society, WPES 2003",

note = "Proceedings of the 2003 ACM Workshop on Privacy in the Electronic Society, WPES 2003 ; Conference date: 30-10-2003 Through 30-10-2003",

}