Private membership test protocol with low communication complexity
: Sara Ramezanian, Tommi Meskanen, Masoud Naderpour, Ville Junnila, Valtteri Niemi
Publisher: Elsevier
: 2020
: Digital Communications and Networks
: Digital Communications and Networks
: 6
: 3
: 321
: 332
: 2352-8648
DOI: https://doi.org/10.1016/j.dcan.2019.05.002(external)
: https://research.utu.fi/converis/portal/detail/Publication/41851516(external)
We introduce a practical method to perform private membership tests. In this method, clients are able to test whether an item is in a set controlled by the server without revealing their query item to the server. After executing the queries, the content of the server's set remains secret. One use case for a private membership test is to check whether a file contains any malware by checking its signature against a database of malware samples in a privacy preserving way. We apply the Bloom filter and the Cuckoo filter in the membership test procedure. In order to achieve privacy properties, we present a novel protocol based on some homomorphic encryption schemes. In our protocol, we rearrange the data in the set into N
-dimensional hypercubes. We have implemented our method in a realistic scenario where a client of an anti-malware company wants to privately check whether a hash value of a given file is in the malware database of the company. The evaluation shows that our method is feasible for real-world applications. We also have tested the performance of our protocol for databases of different sizes and data structures with different dimensions: 2-dimensional, 3-dimensional and 4-dimensional hypercubes. We present formulas to estimate the cost of computation and communication in our protocol.