PrivCQ: Trading multi-dimensional conditional queries under personalised local differential privacy

Abstract A private data query system (PDQS) enables data consumers to access privately owned data while compensating data owners for their privacy loss. The two main tasks of a PDQS include procurement, i.e., collecting data from multiple data owners with an appropriate pricing scheme, and querying, i.e., aggregating the collected dataset for a query output while preserving data owners’ privacy. Existing PDQS are designed for unconditional queries over single-attribute data. In this paper, we design PrivCQ, a new PDQS that supports conditional queries over multi-dimensional data. To accommodate heterogeneous attribute-level privacy preferences, we introduce a new privacy concept, multi-dimensional personalised local differential privacy (m-PLDP), which specifies privacy requirements across multiple sensitive attributes for each data owner. For procurement, we propose total purchased privacy maximisation (TPPM), a principle linking query accuracy to m-PLDP. For query, we propose two techniques, attribute fusion and aggregation conditioning, to process conditional queries over multi-dimensional sensitive data. We design three query mechanisms that achieve m-PLDP under different paradigms and empirically validate them on three real-world datasets.