Oblivious Substring Search with Updates.

Abstract

We are the first to address the problem of efficient obliv-ious substring search over encrypted data supporting up-dates. 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 commu-nication 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 depen-dency and optimizes the size of ORAM blocks and tree height. Based on oblivious suffix arrays, SA-ORAM tar-gets 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 240 strings, an oblivious substring search can be performed with only hundreds of KBytes communication cost. 1