Paper 2020/964 Original: eprint.iacr.org/2020/964 ↗

Configurable Private Querying: Lookup and Partial Matching under Homomorphic Encryption

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.