Paper Info
Title
Efficient Fuzzy Search on Encrypted Data.
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 closeness function on the message space, that we call efficiently fuzzy-searchable encryption (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.
Year
DOI
Venue
2014
10.1007/978-3-662-46706-0_31
Lecture Notes in Computer Science
DocType
Volume
ISSN
Journal
8540
0302-9743
Citations 
PageRank 
References 
2
0.35
0
Authors
2
Name
Order
Citations
PageRank
Alexandra Boldyreva12297114.80
Nathan Chenette253117.37