Secure pseudonymisation for privacy-preserving probabilistic record linkage

In applications where the data used for matching must be kept private the raw values are replaced by pseudonyms. For better linkage performance these pseudonyms should also convey information regarding similarities. Existing approaches are often based on Bloom filters, yet these are susceptible to attack. Secure schemes based on Bloom filters inevitably involve additional security measures. Here we introduce a new scheme that produces pseudonyms that are far more secure than Bloom filters. It can be used a drop-in replacement for many schemes that use Bloom filters. The new scheme allows similarity scores to be estimated from pairs of pseudonyms with negligible bias and with known variance for a given similarity score.