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

cited authors

  • Williams, P; Sion, R; Carbunar, B

abstract

  • 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.

publication date

  • December 1, 2008

Digital Object Identifier (DOI)

start page

  • 139

end page

  • 148