International Association
for Cryptologic Research

We present RASP, a new protocol for privacy-preserving range

search and sort queries on encrypted data in the face of an

untrusted data store. The contribution of RASP over related work

is twofold: first, RASP improves privacy guarantees by ensuring

that 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]. Second, RASP is highly

practical, abstaining from expensive asymmetric cryptography and

bilinear pairings. Instead, RASP only relies on hash and block

cipher operations. The main idea of RASP is to build upon 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 using

Amazon Dynamo.