Failure to supply a care provider with timely access to a patient's medical record can lead to patient harm or death. As such, healthcare organizations often endow care providers with broad access privileges to electronic medical record (EMR) systems. In doing so, however, care providers may access a patient's record without legitimate purpose and violate patient privacy. Healthcare privacy officials use EMR access logs to investigate potential violations. The typical log is limited in its information, so that it is often necessary to merge access logs with other information systems. The problem with this practice is that sensitive information about patients and care providers may be disclosed in the process.

In this paper, we present a privacy preserving technique that enables linkage of disparate health information systems without revealing sensitive information. The technique permits any number of vested parties to contribute to audit investigations without learning information about those being investigated. We motivate the protocol in a real world medical center and then generalize the protocol for implementation in existing healthcare environments.