Real-time Private Membership Test using Homomorphic Encryption

Eduardo Chielle, Homer Gamil, Michail Maniatakos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


With the ever increasing volume of private data residing on the cloud, privacy is becoming a major concern. Often times, sensitive information is leaked during a querying process between a client and an online server hosting a database; The query may leak information about the element the client is looking up, while sensitive details about the contents of its database can leak on the server side. The ability to check if an element is included in a database while maintaining both the client's and the server's privacy is known as the Private Membership Test. In this context, we propose a method to privately query a database with computational complexity O(1) using Bloom filters and Homomorphic Encryption. The proposed methodology also enables post-encryption insertions and deletions without requiring a new setup. Experimental results show that our proposed solution has practical setup, insertion and deletion times for databases of up to a few million entries, with constant query time less than 0.3 s, considering a false positive rate lower than 10-3. We instantiate our methodology for a URL denylisting service, and demonstrate that it can provide solid security guarantees without affecting the user experience.

Original languageEnglish (US)
Title of host publicationProceedings of the 2021 Design, Automation and Test in Europe, DATE 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9783981926354
StatePublished - Feb 1 2021
Event2021 Design, Automation and Test in Europe Conference and Exhibition, DATE 2021 - Virtual, Online
Duration: Feb 1 2021Feb 5 2021

Publication series

NameProceedings -Design, Automation and Test in Europe, DATE
ISSN (Print)1530-1591


Conference2021 Design, Automation and Test in Europe Conference and Exhibition, DATE 2021
CityVirtual, Online

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Real-time Private Membership Test using Homomorphic Encryption'. Together they form a unique fingerprint.

Cite this