Private membership test protocol with low communication complexity

• 作者: Masoud Naderpour Sara Ramezanian Tommi Meskanen Valtteri Niemi Ville Junnil
• 来源期刊: 数字通信与网络:英文版
• 学科: 工学
• 关键词: Privacy enhancing technologies Applied cryptography Private information retrieval Private membership test Homomorphic encryption
• 年，卷（期）: 2020,（3）
• 页码范围: 321-332
• 页数: 12页
• 分类号: TP3

摘要

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.