TY - GEN
T1 - Single round access privacy on outsourced storage
AU - Williams, Peter
AU - Sion, Radu
PY - 2012
Y1 - 2012
N2 - We present SR-ORAM,1 the first single-round-trip polylogaithmic time Oblivious RAM that requires only logarithmic client storage. Taking only a single round trip to perform a query, SR-ORAM has an online communication/ computation cost of O(log n log log n), and an offline, overall amortized per-query communication cost of O(log2 n log log n), requiring under 2 round trips. The client folds an entire interactive sequence of Oblivious RAM requests into a single query object that the server can unlock incrementally, to satisfy a query without learning its result. This results in an Oblivious RAM secure against an actively malicious adversary, with unprecedented speeds in accessing large data sets over high-latency links. We show this to be the most efficient storage-free-client Oblivious RAM to date for today's Internet-scale network latencies.
AB - We present SR-ORAM,1 the first single-round-trip polylogaithmic time Oblivious RAM that requires only logarithmic client storage. Taking only a single round trip to perform a query, SR-ORAM has an online communication/ computation cost of O(log n log log n), and an offline, overall amortized per-query communication cost of O(log2 n log log n), requiring under 2 round trips. The client folds an entire interactive sequence of Oblivious RAM requests into a single query object that the server can unlock incrementally, to satisfy a query without learning its result. This results in an Oblivious RAM secure against an actively malicious adversary, with unprecedented speeds in accessing large data sets over high-latency links. We show this to be the most efficient storage-free-client Oblivious RAM to date for today's Internet-scale network latencies.
KW - Access privacy
KW - Cloud computing
KW - Oblivious RAM
UR - https://www.scopus.com/pages/publications/84869381921
U2 - 10.1145/2382196.2382229
DO - 10.1145/2382196.2382229
M3 - Conference contribution
AN - SCOPUS:84869381921
SN - 9781450316507
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 293
EP - 304
BT - CCS'12 - Proceedings of the 2012 ACM Conference on Computer and Communications Security
T2 - 2012 ACM Conference on Computer and Communications Security, CCS 2012
Y2 - 16 October 2012 through 18 October 2012
ER -