Paper 2019/434
Masking Fuzzy-Searchable Public Databases
Alexandra Boldyreva, 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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. ACNS 2019
- Keywords
- keyless searchable encryptionLSHimage search
- Contact author(s)
-
sasha @ gatech edu
ttang @ gatech edu
csxbw @ bristol ac uk - History
- 2019-04-29: received
- Short URL
- https://ia.cr/2019/434
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/434,
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{https://eprint.iacr.org/2019/434}},
url = {https://eprint.iacr.org/2019/434}
}
