Cryptology ePrint Archive: Report 2019/434

Masking Fuzzy-Searchable Public Databases

Alexandra Boldyreva and Tianxin Tang and Bogdan Warinschi

Abstract: 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.

Category / Keywords: cryptographic protocols / keyless searchable encryption, LSH, image search

Original Publication (with major differences): ACNS 2019

Date: received 27 Apr 2019

Contact author: sasha at gatech edu, ttang at gatech edu, csxbw at bristol ac uk

Available format(s): PDF | BibTeX Citation

Version: 20190429:021248 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]