Paper 2013/732

SSS-V2: Secure Similarity Search

Hyun-A Park

Abstract

Encrypting information has been regarded as one of the most substantial approaches to protect users’ sensitive information in radically changing internet technology era. In prior research, researchers have considered similarity search over encrypted documents infeasible, because the single-bit difference of a plaintext would result in an enormous bits difference in the corresponding ciphertext. However, we propose a novel idea of Security Similarity Search (SSS) over encrypted documents by applying character-wise encryption with approximate string matching to keyword index search systems. In order to do this, we define the security requirements of similarity search over encrypted data, propose two similarity search schemes, and formally prove the security of the schemes. The first scheme is more efficient, while the second scheme achieves perfect similarity search privacy. Surprisingly, the second scheme turns out to be faster than other keyword index search schemes with keywordwise encryption, while enjoying the same level of security. The schemes of SSS support “like query(‘ab%’)” and a query with misprints in that the character-wise encryption preserves the degree of similarity between two plaintexts, and renders approximate string matching between the corresponding ciphertexts possible without decryption.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. MINOR revision.
Keywords
encrypted datasimilarity searchcharacter-wise encryptionapproximate string matching
Contact author(s)
kokokzi @ naver com
History
2013-11-14: received
Short URL
https://ia.cr/2013/732
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/732,
      author = {Hyun-A Park},
      title = {SSS-V2: Secure Similarity Search},
      howpublished = {Cryptology ePrint Archive, Paper 2013/732},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/732}},
      url = {https://eprint.iacr.org/2013/732}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.