Private Record Matching Using Differential Privacy
Private matching between datasets owned by distinct parties is a challengingproblem with several applications. Private matching allows two parties toidentify the records that are close to each other according to some distancefunctions, such that no additional information other than the join result isdisclosed to any party. Private matching can be solved securely andaccurately using secure multi-party computation (SMC) techniques, but suchan approach is prohibitively expensive in practice. Previous work proposedthe release of sanitized versions of the sensitive datasets which allowsblocking, i.e., filtering out sub-sets of records that cannot be part of the joinresult. This way, SMC is applied only to a small fraction of record pairs,reducing the matching cost to acceptable levels. The blocking step isessential for the privacy, accuracy and efficiency of matching. We propose analternative design centered on differential privacy, a novel paradigm thatprovides strong privacy guarantees. The realization of the new modelpresents difficult challenges, such as the evaluation of distance-basedmatching conditions with the help of only a statistical queries interface.Specialized versions of data indexing structures (e.g., kd-trees) also need tobe devised, in order to comply with differential privacy. This is a joint workwith Murat Kantarcioglu, Gabriel Ghinita and Elisa Bertino.
BIO. Ali Inan received the B.S. and M.S. degrees in Computer Engineeringfrom Sabanci University, Istanbul, Turkey, in 2004 and 2006 respectively andhis Ph.D. degree in Computer Science at the University of Texas at Dallas in2010. His research interests lie at the intersection of privacy, security, datamining and databases: security and privacy issues raised by data mining;distributed data mining techniques; security issues in databases; appliedcryptography and Secure Multi-Party Computation techniques. Ali is amember of the IEEE Computer Society.