Building castles out of mud: Practical access pattern privacy and correctness on untrusted storage

Peter Williams; Radu Sion; Bogdan Carbunar

doi:10.1145/1455770.1455790

Building castles out of mud: Practical access pattern privacy and correctness on untrusted storage

Peter Williams
, Radu Sion
, Bogdan Carbunar

Computer Science

Stony Brook University
Motorola

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

185 Scopus citations

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.

Original language	English
Title of host publication	Proceedings of the 15th ACM Conference on Computer and Communications Security, CCS'08
Pages	139-148
Number of pages	10
DOIs	https://doi.org/10.1145/1455770.1455790
State	Published - 2008
Event	15th ACM conference on Computer and Communications Security, CCS'08 - Alexandria, VA, United States Duration: Oct 27 2008 → Oct 31 2008

Publication series

Name	Proceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)	1543-7221

Conference

Conference	15th ACM conference on Computer and Communications Security, CCS'08
Country/Territory	United States
City	Alexandria, VA
Period	10/27/08 → 10/31/08

Keywords

Data outsourcing, Private information retrieval

Access to Document

10.1145/1455770.1455790

Cite this

@inproceedings{cdad8fac932a43ff98c1dc2adc5b08e9,

title = "Building castles out of mud: Practical access pattern privacy and correctness on untrusted storage",

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.",

keywords = "Data outsourcing, Private information retrieval",

author = "Peter Williams and Radu Sion and Bogdan Carbunar",

year = "2008",

doi = "10.1145/1455770.1455790",

language = "English",

isbn = "9781595938107",

series = "Proceedings of the ACM Conference on Computer and Communications Security",

pages = "139--148",

booktitle = "Proceedings of the 15th ACM Conference on Computer and Communications Security, CCS'08",

note = "15th ACM conference on Computer and Communications Security, CCS'08 ; Conference date: 27-10-2008 Through 31-10-2008",

}

Williams, P, Sion, R & Carbunar, B 2008, Building castles out of mud: Practical access pattern privacy and correctness on untrusted storage. in Proceedings of the 15th ACM Conference on Computer and Communications Security, CCS'08. Proceedings of the ACM Conference on Computer and Communications Security, pp. 139-148, 15th ACM conference on Computer and Communications Security, CCS'08, Alexandria, VA, United States, 10/27/08. https://doi.org/10.1145/1455770.1455790

Building castles out of mud: Practical access pattern privacy and correctness on untrusted storage. / Williams, Peter; Sion, Radu; Carbunar, Bogdan.
Proceedings of the 15th ACM Conference on Computer and Communications Security, CCS'08. 2008. p. 139-148 (Proceedings of the ACM Conference on Computer and Communications Security).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Building castles out of mud

T2 - 15th ACM conference on Computer and Communications Security, CCS'08

AU - Williams, Peter

AU - Sion, Radu

AU - Carbunar, Bogdan

PY - 2008

Y1 - 2008

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

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

KW - Data outsourcing, Private information retrieval

UR - https://www.scopus.com/pages/publications/70349278621

U2 - 10.1145/1455770.1455790

DO - 10.1145/1455770.1455790

M3 - Conference contribution

AN - SCOPUS:70349278621

SN - 9781595938107

T3 - Proceedings of the ACM Conference on Computer and Communications Security

SP - 139

EP - 148

BT - Proceedings of the 15th ACM Conference on Computer and Communications Security, CCS'08

Y2 - 27 October 2008 through 31 October 2008

ER -

Building castles out of mud: Practical access pattern privacy and correctness on untrusted storage

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this