Title

Collusion-resistant protocols for private processing of aggregated queries in distributed databases

Publication Name

Distributed and Parallel Databases

Abstract

Private processing of database queries protects the confidentiality of sensitive data when queries are answered. It is important to design collusion-resistant protocols ensuring that privacy remains protected even when a certain number of honest-but-curious participants collude to share their knowledge in order to gain unauthorised access to sensitive information. A novel setting arises when aggregated queries need to be answered for a large distributed database, but legal requirements or commercial interests forbid making access to records in each subdatabase available to other counterparts. For example, a very large number of medical records may be stored in a distributed database, which is a union of several separate databases from different hospitals, or even from different countries. The present article introduces and investigates two protocols for collusion-resistant private processing of aggregated queries in this novel setting: Accelerated Multi-round Iterative Protocol (AMIP) and Restricted Multi-round Iterative Protocol (RMIP). We define a large collection of query functions and show that AMIP and RMIP protocols can answer all queries in this collection. Our experiments demonstrate that the AMIP protocol outperforms all other applicable algorithms, and this achievement is especially significant in terms of the communication complexity.

Open Access Status

This publication is not available as open access

Volume

39

Issue

1

First Page

97

Last Page

127

Funding Number

DP160100913

Funding Sponsor

Australian Research Council

Share

COinS
 

Link to publisher version (DOI)

http://dx.doi.org/10.1007/s10619-020-07293-z