International Association
for Cryptologic Research

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.