Paper 2020/964

Configurable Private Querying: Lookup and Partial Matching under Homomorphic Encryption

Hamish Hunt, Jack Crawford, Oliver Masters, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Homomorphic encryptionImplementationHomomorphic computationPrivate set intersectionPrivate information retrievalPartial matchingRelational databases
Contact author(s)
faberga @ googlemail com
flavio @ uk ibm com
History
2020-08-11: received
Short URL
https://ia.cr/2020/964
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/964,
      author = {Hamish Hunt and Jack Crawford and Oliver Masters and Enrico Steffinlongo and Flavio Bergamaschi},
      title = {Configurable Private Querying: Lookup and Partial Matching under Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/964},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/964}},
      url = {https://eprint.iacr.org/2020/964}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.