Formal Anonymity Models for Efficient Privacy-preserving Joins

Abstract

Organizations, such as federally-funded medical research centers, must share de-identified data on their consumers to publicly accessible repositories to adhere to regulatory requirements. Many repositories are managed by third-parties and it is often unknown if records received from disparate organizations correspond to the same individual. Failure to resolve this issue can lead to biased (e.g., double counting of identical records) and underpowered (e.g., unlinked records of different data types) investigations. in this paper, we present a secure multiparty computation protocol that enables record joins via consumers' encrypted identifiers. Our solution is more practical than prior secure join models in that data holders need to interact with the third party one time per data submission. Though technically feasible, the speed of the basic protocol scales quadratically with the number of records. Thus, we introduce an extended version of our protocol in which data holders append k-anonymous features of their consumers to their encrypted submissions. These features facilitate a more efficient join computation, while providing a formal guarantee that each record is linkable to no less than k individuals in the union of all organizations' consumers. Beyond a theoretical treatment of the problem, we provide an extensive experimental investigation with data derived from the US Census to illustrate the significant gains in efficiency such an approach can achieve. © 2009 Elsevier B.V. All rights reserved.

Department(s)

Computer Science

Comments

National Science Foundation, Grant None

Keywords and Phrases

Anonymity; Data integration; Privacy; Security

International Standard Serial Number (ISSN)

0169-023X

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2024 Elsevier, All rights reserved.

Publication Date

01 Nov 2009

Link to Full Text

Share

 
COinS