×

Privacy-preserving access of outsourced data via oblivious RAM simulation. (English) Zbl 1333.68100

Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-22011-1/pbk). Lecture Notes in Computer Science 6756, 576-587 (2011).
Summary: We describe schemes for the oblivious RAM simulation problem with a small logarithmic or polylogarithmic amortized increase in access times, with a very high probability of success, while keeping the external storage to be of size \(O(n)\).
For the entire collection see [Zbl 1217.68004].

MSC:

68P20 Information storage and retrieval of data
68P25 Data encryption (aspects in computer science)
94A60 Cryptography

Software:

BSGP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ajtai, M.: Oblivious RAMs without cryptographic assumptions. In: Proc. of the 42nd ACM Symp. on Theory of Computing (STOC), pp. 181–190. ACM, New York (2010) · Zbl 1293.68120
[2] Damgård, I., Meldgaard, S., Nielsen, J.B.: Perfectly secure oblivious RAM without random oracles. Cryptology ePrint Archive, Report 2010/108 (2010), http://eprint.iacr.org/ · Zbl 1295.94046
[3] Drmota, M., Kutzelnigg, R.: A precise analysis of cuckoo hashing (2008) (preprint), http://www.dmg.tuwien.ac.at/drmota/cuckoohash.pdf · Zbl 1295.68234
[4] Feldman, J., Muthukrishnan, S., Sidiropoulos, A., Stein, C., Svitkina, Z.: On distributing symmetric streaming computations. In: ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 710–719 (2008) · Zbl 1192.68856
[5] Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM 43(3), 431–473 (1996) · Zbl 0885.68041 · doi:10.1145/233551.233553
[6] Goodrich, M., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Privacy-preserving group data access via stateless oblivious RAM simulation (unpublished manuscript)
[7] Goodrich, M.T., Mitzenmacher, M.: MapReduce Parallel Cuckoo Hashing and Oblivious RAM Simulations. ArXiv e-prints, Eprint 1007.1259v1 (July 2010)
[8] Goodrich, M.T., Mitzenmacher, M.: Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation. ArXiv e-prints, Eprint 1007.1259v2 (April 2011)
[9] Karloff, H., Suri, S., Vassilvitskii, S.: A model of computation for MapReduce. In: Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA), pp. 938–948 (2010) · Zbl 1288.68247 · doi:10.1137/1.9781611973075.76
[10] Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: cuckoo hashing with a stash. SIAM J. Comput. 39, 1543–1561 (2009) · Zbl 1205.68253 · doi:10.1137/080728743
[11] Lee, D.-L., Batcher, K.E.: A multiway merge sorting network. IEEE Trans. on Parallel and Distributed Systems 6(2), 211–215 (1995) · Zbl 05106709 · doi:10.1109/71.342136
[12] McDiarmid, C.: Concentration. In: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.) Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 195–248. Springer, Berlin (1998) · Zbl 0927.60027 · doi:10.1007/978-3-662-12788-9_6
[13] Pagh, R., Rodler, F.: Cuckoo hashing. Journal of Algorithms 52, 122–144 (2004) · Zbl 1091.68036 · doi:10.1016/j.jalgor.2003.12.002
[14] Pinkas, B., Reinman, T.: Oblivious RAM revisited. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 502–519. Springer, Heidelberg (2010) · Zbl 1283.94102 · doi:10.1007/978-3-642-14623-7_27
[15] Williams, P., Sion, R.: Usable pir. In: NDSS. The Internet Society, San Diego (2008)
[16] Williams, P., Sion, R., Carbunar, B.: Building castles out of mud: practical access pattern privacy and correctness on untrusted storage. In: 15th ACM Conf. on Computer and Communications Security (CCS), pp. 139–148 (2008) · doi:10.1145/1455770.1455790
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.