Paper 2017/153

Storage Efficient Substring Searchable Symmetric Encryption

Iraklis Leontiadis and Ming Li


We address the problem of substring searchable encryption. A single user produces a big stream of data and later on wants to learn the positions in the string that some patterns occur. Although current techniques exploit auxiliary data structures to achieve efficient substring search on the server side, the cost at the user side may be prohibitive. We revisit the work of substring searchable encryption in order to reduce the storage cost of auxiliary data structures. Our solution entails a suffix array based index design, which allows optimal storage cost $O(n)$ with small hidden factor at the size of the string $n$. We analyze the security of the protocol in the real ideal framework. Moreover, we implemented our scheme and the state of the art protocol \cite{Chase} to demonstrate the performance advantage of our solution with precise benchmark results. We improved the storage overhead of the encrypted index by a factor of $\mathbf{1.7}$ and the computation time thereof $\mathbf{4x}$ on $10^6$ character data stream.

Available format(s)
Publication info
Preprint. MINOR revision.
substring searchable encryption
Contact author(s)
leontiad @ njit edu
2017-06-28: last of 8 revisions
2017-02-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Iraklis Leontiadis and Ming Li},
      title = {Storage Efficient Substring Searchable Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2017/153},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.