Interactive Range Queries for Healthcare Data under Differential Privacy

Analyses of fine-grained healthcare data by medical researchers can have many societal benefits, including helping to track the spread of COVID-19 and treatment successes. As healthcare data includes personally identifying information (PII), privacy loss needs to be prevented. Differential privacy permits data analysis without loss of individual privacy via a curator who guards the data and determines its appropriate release. An $\in$ parameter measures the noise applied to the query results to control exposure of sensitive data: a low $\in$ value corresponds to more privacy protection, while a higher $\in$ value releases more accurate results with less privacy. Range queries, which count the number of values in a dataset within a user-defined range, pose privacy challenges that are especially concerning in healthcare applications. For example, an adversary can make sequential and overlapping range queries over a sensitive attribute, resulting in isolating information about a specific individual. This work addresses range query privacy concerns in the healthcare domain by proposing an $\epsilon$-private Multi-Attribute DisAssembly Mechanism (MADAM). MADAM supports both single-attribute and multiattribute range queries involving sensitive attributes. The paper also presents BiMADAM, an extension that reduces the error to be polylogarithmic in the sensitivity degree of the queries.