You are looking at a specific version 20140401:064935 of this paper. See the latest version.

Paper 2014/235

Efficient Fuzzy Search on Encrypted Data

Alexandra Boldyreva and Nathan Chenette

Abstract

We study the problem of efficient (sub-linear) fuzzy search on encrypted outsourced data, in the symmetric-key setting. In particular, a user who stores encrypted data on a remote untrusted server forms queries that enable the server to efficiently locate the records containing the requested keywords, even though the user may misspell keywords or provide noisy data in the query. We define an appropriate primitive for a general \emph{closeness} function on the message space that we call \emph{efficiently fuzzy-searchable encryption} (\emph{EFSE}). Next we identify an optimal security notion for EFSE. We demonstrate that existing schemes do not meet our security definition and propose a new scheme that we prove secure under basic assumptions. Unfortunately, the scheme requires large ciphertext length, but we show that, in a sense, this space-inefficiency is unavoidable for a general, optimally-secure scheme. Seeking the right balance between efficiency and security, we then show how to construct schemes that are more efficient and satisfy a weaker security notion that we propose. To illustrate, we present and analyze a more space-efficient scheme for supporting fuzzy search on biometric data that achieves the weaker notion.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in FSE 2014
Keywords
Searchable encryptionsymmetric encryptionfuzzy search
Contact author(s)
nlchenette @ gmail com
History
2014-04-01: received
Short URL
https://ia.cr/2014/235
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.