Paper 2013/715

Practical Forward-Secure Range and Sort Queries with Update-Oblivious Linked Lists

Erik-Oliver Blass, Travis Mayberry, and Guevara Noubir


We revisit the problem of privacy-preserving range search and sort queries on encrypted data in the face of an untrusted data store. Our new protocol RASP has several advantages over existing work. First, RASP strengthens privacy by ensuring {forward security}: after a query for range $[a,b]$, any new record added to the data store is indistinguishable from random, even if the new record falls within range $[a,b]$. We are able to accomplish this using only traditional hash and block cipher operations, abstaining from expensive asymmetric cryptography and bilinear pairings. Consequently, RASP is highly practical, even for large database sizes. Additionally, we require only cloud {storage} and not a computational cloud like related works, which can reduce monetary costs significantly. At the heart of RASP, we develop a new {update-oblivious} bucket-based data structure. We allow for data to be added to buckets without leaking into which bucket it has been added. As long as a bucket is not explicitly queried, the data store does not learn anything about bucket contents. Furthermore, no information is leaked about data additions following a query. Besides formally proving RASP's privacy, we also present a practical evaluation of RASP on Amazon Dynamo, demonstrating its efficiency and real world applicability.

Available format(s)
Publication info
Preprint. MINOR revision.
ApplicationsPrivacyCloud ComputingUpdate-Oblivious Data Structures
Contact author(s)
blass @ ccs neu edu
2015-02-16: last of 3 revisions
2013-11-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Erik-Oliver Blass and Travis Mayberry and Guevara Noubir},
      title = {Practical Forward-Secure Range and Sort Queries with Update-Oblivious Linked Lists},
      howpublished = {Cryptology ePrint Archive, Paper 2013/715},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.