Paper 2015/722

Oblivious Substring Search with Updates

Tarik Moataz and Erik-Oliver Blass


We are the first to address the problem of efficient oblivious substring search over encrypted data supporting updates. Our two new protocols SA-ORAM and ST-ORAM obliviously search for substrings in an outsourced set of n encrypted strings. Both protocols are efficient, requiring communication complexity that is only poly-logarithmic in n. Compared to a straightforward solution for substring search using recent “oblivious data structures” [30], we demonstrate that our tailored solutions improve communication complexity by a factor of logn. The idea behind SA-ORAM and ST-ORAM is to employ a new, hierarchical ORAM tree structure that takes advantage of data dependency and optimizes the size of ORAM blocks and tree height. Based on oblivious suffix arrays, SA-ORAM targets efficiency, yet does not allow updates to the outsourced set of strings. ST-ORAM, based on oblivious suffix trees, allows updates at the additional communications cost of a factor of loglogn. We implement and benchmark SA-ORAM to show its feasibility for practical deployments: even for huge datasets of 2^40 strings, an oblivious substring search can be performed with only hundreds of KBytes communication cost.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
oblivious ram
Contact author(s)
tmoataz @ cs colostate edu
2015-07-21: received
Short URL
Creative Commons Attribution


      author = {Tarik Moataz and Erik-Oliver Blass},
      title = {Oblivious Substring Search with Updates},
      howpublished = {Cryptology ePrint Archive, Paper 2015/722},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.