Paper 2015/722

Oblivious Substring Search with Updates

Tarik Moataz and Erik-Oliver Blass

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
oblivious ram
Contact author(s)
tmoataz @ cs colostate edu
History
2015-07-21: received
Short URL
https://ia.cr/2015/722
License
Creative Commons Attribution
CC BY

BibTeX

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