Privacy-preserving data linkage protocols

ABSTRACT

We address the problem of data linkage and data extraction across database tables of sensitive information about individuals, in an environment of constraints on organisations' ability to share data and a need to protect individuals' privacy and confidentiality.

We propose several privacy-preserving data linkage and data extraction protocols. Our first protocol enables data linkage across separate database tables, without requiring any identifying information to be revealed to any party outside the originating data source. Our second protocol enables the extraction of a cohort of individuals' data from a data source, without revealing the membership of any individual in that cohort to the data source. We describe a variation of the first protocol which enables data sources to generate common pseudonyms without revealing any identifying information to any party, and show how the protocols are applicable for any number of data sources.

REFERENCES

• 1: Rakesh Agrawal , Alexandre Evfimievski , Ramakrishnan Srikant, Information sharing across private databases, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872771]
• 2: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 3: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 4: F. Borst, F. Allaert, and C. Quantin. The Swiss solution for anonymously chaining patient files. In Proc. of MEDINFO 2001, 2001.
• 5: T. Churches and P. Christen. Blind data linkage using n-gram similarity comparisons. In Proc. of PAKDD'04, Sydney, Australia, May 26-28 2004, 121--126.
• 6: L. Dusserre, C. Quantin, and H. Bouzelat. A one way public key cryptosystem for the linkage of nominal files in epidemiological studies. International Journal of Medical Informatics, 8:644--647, 1995.
• 7: M. Freedman, K. Nissim, and B. Pinkas. Efficient Private Matching and Set Intersection. Preprint, 2004.
• 8: C. Kelman, A. Bass, and C. Holman. Research use of linked health data - a best practice protocol. Australian and New Zealand Journal of Public Health, 26:251--255, 2002.
• 9: Moni Naor , Benny Pinkas, Efficient oblivious transfer protocols, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 07-09, 2001, Washington, D.C., United States
• 10: Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001 [doi>10.1145/375360.375365]
• 11: P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology -- EUROCRYPT '99, pages 223--238, 1999.
• 12: K. Pommerening, M. Miller, I. Schidtmann, and J. Michaelis. Pseudonyms for cancer registries. Methods of Information in Medicine, 35:112--121, 1996.
• 13: C. Quantin, H. Bouzelat, F. Allaert, A. Benhamiche, J. Faivre, and L. Dussere. How to ensure data security of an epidemiological follow-up: quality assessment of an anonymous record linkage procedure. International Journal of Medical Informatics, 49:117--122, 1998.
• 14: RSA Laboratories. PKCS#1: RSA cryptography standard. 2002.
• 15: V. Shoup. A proposal for an ISO standard for public key encryption. Available at http://www.shoup.net/papers, 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms

Keywords:
confidentiality, data extraction, data linkage, privacy