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.

REFERENCES

• 1: J. D. Ullman , A. V. Aho , D. S. Hirschberg, Bounds on the Complexity of the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.23 n.1, p.1-12, Jan. 1976 [doi>10.1145/321921.321922]
• 2: J. Benaloh. Dense Probabilistic Encryption, Proceedings of the Workshop on Selected Areas of Cryptography, pp. 120--128 (1994).
• 3: Christian Cachin, Efficient private bidding and auctions with an oblivious third party, Proceedings of the 6th ACM conference on Computer and communications security, p.120-127, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319726]
• 4: W. Du and M. J. Atallah. Protocols for Secure Remote Database Access with Approximate Matching. Proceedings of the 1st ACM Workshop on Security and Privacy in E-Commerce (2000).
• 5: Marc Fischlin, A Cost-Effective Pay-Per-Multiplication Comparison Method for Millionaires, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.457-472, April 08-12, 2001
• 6: O. Goldreich. Secure Multi-party Computation (working draft). Available at http://www.wisdom.weizmann.ac.il/~oded/pp.html (2001).
• 7: S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Computer and System Sciences 28, 2, pp. 270--299 (1984).
• 8: G M Landau , U Vishkin, Introducing efficient parallelism into approximate string matching and a new serial algorithm, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.220-230, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12152]
• 9: H. M. Martinez (ed.) Mathematical and Computational Problems in the Analysis of Molecular Sequences, Bulletin of Mathematical Biology (Special Issue Honoring M. O. Dayhoff), 46, 4 (1984).
• 10: W. J. Masek and M. S. Paterson. A Faster Algorithm Computing String Edit Distances, Journal of Computer and System Science 20, pp. 18--31 (1980).
• 11: David Naccache , Jacques Stern, A new public key cryptosystem based on higher residues, Proceedings of the 5th ACM conference on Computer and communications security, p.59-66, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288106]
• 12: S. B. Needleman and C. D. Wunsch. A General Method Applicable to the Search for Similarities in the Amino-acid Sequence of Two Proteins, Journal of Molecular Biology 48, pp. 443--453 (1973).
• 13: T. Okamoto and S. Uchiyama. A New Public-Key Cryptosystem as Secure as Factoring. Eurocrypt'98 Lecture Notes in Computer Science 1403, pp. 308--318 (1998).
• 14: D. Sankoff. Matching Sequences Under Deletion-insertion Constraints, Proceedings of the National Academy of Sciences of the U.S.A. 69, pp. 4--6 (1972).
• 15: D. Sankoff and J. B. Kruskal (eds.). Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley, Reading, PA (1983).
• 16: Bruce Schneier, Applied cryptography (2nd ed.): protocols, algorithms, and source code in C, John Wiley & Sons, Inc., New York, NY, 1995
• 17: P. H. Sellers. An Algorithm for the Distance between two Finite Sequences, J. of Combinatorial Theory 16, pp. 253--258 (1974).
• 18: P. H. Sellers. The Theory and Computation of Evolutionary Distance: Pattern Recognition, Journal of Algorithms 1, pp. 359--373 (1980).
• 19: E. Ukkonen. Finding Approximate Patterns in Strings, Journal of Algorithms 6, pp. 132--137 (1985).
• 20: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
• 21: C. K. Wong , Ashok K. Chandra, Bounds for the String Editing Problem, Journal of the ACM (JACM), v.23 n.1, p.13-16, Jan. 1976 [doi>10.1145/321921.321923]
• 22: A. Yao. Protocols for Secure Computations. Proceedings of the Annual IEEE Symposium on Foundations of Computer Science 23, pp. 160--164 (1982).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

General Terms:
Algorithms, Security

Keywords:
dynamic programming, edit distance, longest common subsequence, privacy, secure multi-party computation, string matching