Paper 2014/235

Efficient Fuzzy Search on Encrypted Data

Alexandra Boldyreva and Nathan Chenette


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.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in FSE 2014
Searchable encryptionsymmetric encryptionfuzzy search
Contact author(s)
nlchenette @ gmail com
2014-04-01: received
Short URL
Creative Commons Attribution


      author = {Alexandra Boldyreva and Nathan Chenette},
      title = {Efficient Fuzzy Search on Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2014/235},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.