University of Twente Student Theses


Privacy-Preserving Matching Using Bloom Filters: an Analysis and an Encrypted Variant

Stritzl, David (2019) Privacy-Preserving Matching Using Bloom Filters: an Analysis and an Encrypted Variant.

[img] PDF
Abstract:Record lookup schemes are utilised in distributed database systems to allow clients to efficiently identify databases that contain relevant information. In untrusted environments, where a client should not be able to learn about the database entries that are not explicitly queried, probabilistic record lookup schemes can be used to provide a certain level of privacy. In this paper, we provide a framework for evaluating different probabilistic record lookup schemes in terms of privacy, efficiency and utility. For privacy in such schemes, for the first time, we present an analysis of the privacy implications of additions and removals of database records. Using this framework, we furthermore analyse a Bloom filter-based record lookup scheme, for which we show that it can be privacy-preserving depending on the use case and the configuration of the scheme. However, updates of databases records in this scheme, can introduce a significant privacy impact. Finally, we provide an efficient interactive record lookup protocol using homomorphic encryption that reduces the impact on privacy in the case of database updates
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Computer Science MSc (60300)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page