Paper 2019/434

Masking Fuzzy-Searchable Public Databases

Alexandra Boldyreva, Tianxin Tang, and Bogdan Warinschi


We introduce and study the notion of keyless fuzzy search (KlFS) which allows to mask a publicly available database in such a way that any third party can retrieve content if and only if it possesses some data that is “close to” the encrypted data – no cryptographic keys are involved. We devise a formal security model that asks a scheme not to leak any information about the data and the queries except for some well-defined leakage function if attackers cannot guess the right query to make. In particular, our definition implies that recovering high entropy data protected with a KlFS scheme is costly. We propose two KlFS schemes: both use locality-sensitive hashes (LSH), cryptographic hashes and symmetric encryption as building blocks. The first scheme is generic and works for abstract plaintext domains. The second scheme is specifically suited for databases of images. To demonstrate the feasibility of our KlFS for images, we implemented and evaluated a prototype system that supports image search by object similarity on a masked database.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACNS 2019
keyless searchable encryptionLSHimage search
Contact author(s)
sasha @ gatech edu
ttang @ gatech edu
csxbw @ bristol ac uk
2019-04-29: received
Short URL
Creative Commons Attribution


      author = {Alexandra Boldyreva and Tianxin Tang and Bogdan Warinschi},
      title = {Masking Fuzzy-Searchable Public Databases},
      howpublished = {Cryptology ePrint Archive, Paper 2019/434},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.