Paper 2016/553

Storage Efficient Substring Searchable Symmetric Encryption

Iraklis Leontiadis and Ming Li

Abstract

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 suffix array which allows optimal storage cost $O(n)$ with small hidden factor at the size of the string $n$. On top of that we build an encrypted index that allows the server to answer substring queries without learning neither the query nor the result. We identify the leakages of the scheme following the work of Curtmola $\etal$ \cite{sse2} and we analyze the security of the protocol in the real ideal framework. Moreover, we demonstrate the practicality of the protocol by searching a one million characters data stream in less than one second within the GPU computing paradigm. The total speedup approximates a factor of $4$x, compared with naive CPU implementation.

Metadata
Available format(s)
-- withdrawn --
Publication info
Preprint. MINOR revision.
Keywords
substring searchable encryptionsuffix array
Contact author(s)
leontiad @ email arizona edu
History
2016-07-11: withdrawn
2016-06-02: received
See all versions
Short URL
https://ia.cr/2016/553
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.