Building castles out of mud: Practical access pattern privacy and correctness on untrusted storage
Conference
Williams, P, Sion, R, Carbunar, B. (2008). Building castles out of mud: Practical access pattern privacy and correctness on untrusted storage
. 139-148. 10.1145/1455770.1455790
Williams, P, Sion, R, Carbunar, B. (2008). Building castles out of mud: Practical access pattern privacy and correctness on untrusted storage
. 139-148. 10.1145/1455770.1455790
We introduce a new practical mechanism for remote data storage with efficient access pattern privacy and correctness, A storage client can deploy this mechanism to issue encrypted reads, writes, and inserts to a potentially curious and malicious storage service provider, without revealing information or access patterns. The provider is unable to establish any correlation between successive accesses, or even to distinguish between a read and a write. Moreover, the client is provided with strong correctness assurances for its operations - illicit provider behavior does not go undetected. We built a first practical system - orders of magnitude faster than existing implementations - that can execute over several queries per second on lTbyte+ databases with full computational privacy and correctness. Copyright 2008 ACM.
