Name
Abstract | ||
|---|---|---|
In (22) we showed that existing single-server computa- tional private information retrieval (PIR) protocols for the purpose of preserving client access patterns leakage are or- ders of magnitude slower than trivially transferring the en- tire data sets to the inquiring clients. We thus raised the issue of designing efficient PIR mechanisms in practical set- tings. In this paper we introduce exactly such a technique, guaranteeing access pattern privacy against a computa- tionally bounded adversary, in outsourced data storage, with communication and computation overheads orders of magnitude better than existing approaches. In the pres- ence of a small amount (O( p n), where n is the size of the database) of temporary storage, clients can achieve access pattern privacy with communication and computa- tional complexities of less than O(log 2 n) per query (as compared to e.g., O(log 4 n) for existing approaches). We achieve these novel results by applying new insights based on probabilistic analyses of data shuffling algorithms to Oblivious RAM (17), allowing us to significantly improve its asymptotic complexity. This results in a protocol cross- ing the boundary between theory and practice and becom- ing generally applicable for access pattern privacy. We show that on off the shelf hardware, large data sets can be queried obliviously orders of magnitude faster than in exist- ing work. |
Year | Venue | DocType |
|---|---|---|
2008 | NDSS | Conference |
Citations | PageRank | References |
5 | 0.54 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Williams | 1 | 689 | 81.07 |
| Radu Sion | 2 | 1252 | 81.36 |