Hybrid differentially-private string matching

Private record linkage enables multiple parties to exchange records of similar entities without disclosing their own data sets. Several techniques solve private matching for numerical attributes, but they cannot handle well string-typed data. We propose a protocol for differentially-private linkage of records with string-valued attributes. String-valued data are partitioned into groups, and each partition is represented by a synopsis. Strings are first embedded into a metric space which preserves the relative distance among them, and then they are translated to multi-dimensional points. We propose two partitioning algorithms: the first one uses solely Lipschitz embedding coordinates, whereas the second one also leverages string length information. To the best of our knowledge, this is the first efficient and provably secure solution to the private string matching problem. Extensive experimental results on a real dataset demonstrate that our solution is efficient and accurate. We also show that our solution can be adapted to alternative protection models, e.g., output-constrained differential privacy.