Skip to main content
placeholder image

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

Journal Article


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.

Publication Date


  • 2021

Citation


  • Rylands, L., Seberry, J., Yi, X., Kelarev, A., Ryan, J., & Lin, Y. (2021). Collusion-resistant protocols for private processing of aggregated queries in distributed databases. Distributed and Parallel Databases, 39(1), 97-127. doi:10.1007/s10619-020-07293-z

Scopus Eid


  • 2-s2.0-85084846523

Web Of Science Accession Number


Start Page


  • 97

End Page


  • 127

Volume


  • 39

Issue


  • 1

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.

Publication Date


  • 2021

Citation


  • Rylands, L., Seberry, J., Yi, X., Kelarev, A., Ryan, J., & Lin, Y. (2021). Collusion-resistant protocols for private processing of aggregated queries in distributed databases. Distributed and Parallel Databases, 39(1), 97-127. doi:10.1007/s10619-020-07293-z

Scopus Eid


  • 2-s2.0-85084846523

Web Of Science Accession Number


Start Page


  • 97

End Page


  • 127

Volume


  • 39

Issue


  • 1