Cryptology ePrint Archive: Report 2020/964

Configurable Private Querying: Lookup and Partial Matching under Homomorphic Encryption

Hamish Hunt and Jack Crawford and Oliver Masters and Enrico Steffinlongo and Flavio Bergamaschi

Abstract: The ability to query a database privately is nowadays ubiquitous via an encrypted channel. With the advent of homomorphic encryption, there is a want to expand the notion of privacy in this context to querying privately on the database with the database learning as little to no information of the query data or its result. The ability to compute the intersection from at least two parties’ sets that are kept private only to themselves is known as private set intersection (PSI) and should be considered a fundamental operation in several homomorphic computation scenarios to do useful work; not least for the ability to implement queries on a database. We outline in this paper a novel highly configurable PSI structure to be used in private querying providing the possibility that even the exact query itself can be protected from the database if required. As well as complex database lookups, there is also a more complex partial matching. The outline of the system design is discussed and we report preliminary results on some of the fundamental operations. We demonstrate that this technology is emerging as a viable given response to lookup queries and partially matching on an encrypted database with over a million entries in approximately 9 minutes.

Category / Keywords: public-key cryptography / Homomorphic encryption, Implementation, Homomorphic computation, Private set intersection, Private information retrieval, Partial matching, Relational databases

Date: received 7 Aug 2020, last revised 7 Aug 2020

Contact author: faberga at googlemail com, flavio@uk ibm com

Available format(s): PDF | BibTeX Citation

Version: 20200811:114110 (All versions of this report)

Short URL: ia.cr/2020/964


[ Cryptology ePrint archive ]