DF-ORAM: A Practical Dummy Free Oblivious RAM to Protect Outsourced Data Access Pattern

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9955
• 期：1
• 页码：415-432
• 全文大小：802 KB
• 参考文献：1.Gentry, C., Goldman, K.A., Halevi, S., Julta, C., Raykova, M., Wichs, D.: Optimizing ORAM and using it efficiently for secure computation. In: De Cristofaro, E., Wright, M. (eds.) PETS 2013. LNCS, vol. 7981, pp. 1–18. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-39077-7_​1 CrossRef
  2.Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM 43(3), 431–473 (1996)CrossRef MATH MathSciNet
  3.Goodrich, M.T., Mitzenmacher, M.: Mapreduce parallel cuckoo hashing and oblivious RAM simulations. In: Proceedings of the CoRR (2010)
  4.Goodrich, M.T., Mitzenmacher, M.: Privacy-preserving access of outsourced data via oblivious RAM simulation. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, pp. 576–587. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-22012-8_​46 CrossRef
  5.Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Oblivious RAM simulation with efficient worst-case access overhead. In: Proceedings of the CCSW (2011)
  6.Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Privacy-preserving group data access via stateless oblivious RAM simulation. In: Proceedings of the SODA (2012)
  7.Islam, M., Kuzu, M., Kantarcioglu, M.: Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In: Proceedings of the NDSS (2012)
  8.Kushilevitz, E., Lu, S., Ostrovsky, R.: On the (in)security of hash-based oblivious RAM and a new balancing scheme. In: Proceedings of the SODA (2012)
  9.Ma, Q., Zhang, J., Zhang, W., Qiao, D.: SE-ORAM: a storage-efficient oblivious RAM for privacy-preserving access to cloud storage. In: Proceedings of the 3rd IEEE International Conference on Cyber Security and Cloud Computing, Bejing, China (2016)
  10.Moataz, T., Mayberry, T., Blass, E.O.: Constant communication ORAM with small blocksize. In: Proceedings of the CCS (2015)
  11.Pinkas, B., Reinman, T.: Oblivious RAM revisited. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 502–519. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-14623-7_​27 CrossRef
  12.Shi, E., Chan, T.-H.H., Stefanov, E., Li, M.: Oblivious RAM with \(O((\log N)^3)\) worst-case cost. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, pp. 197–214. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-25385-0_​11 CrossRef
  13.Stefanov, E., Dijk, M.V., Shi, E., Fletcher, C., Ren, L., Yu, X., Devadas, S.: Path ORAM: an extremely simple oblivious RAM protocol. In: Proceedings of the CCS (2013)
  14.Stefanov, E., Shi, E.: Multi-cloud oblivious storage. In: Proceedings of the CCS (2013)
  15.Stefanov, E., Shi, E.: ObliviStore: high performance oblivious cloud storage. In: Proceedings of the S&P (2013)
  16.Stefanov, E., Shi, E., Song, D.: Towards practical oblivious RAM. In: Proceedings of the NDSS (2011)
  17.Wang, X.S., Huang, Y., Chan, T.H.H., Shelat, A., Shi, E.: SCORAM: oblivious RAM for secure computation. In: Proceedings of the CCS (2014)
  18.Williams, P., Sion, R.: Single round access privacy on outsourced storage. In: Proceedings of the CCS (2012)
  19.Williams, P., Sion, R., Carbunar, B.: Building castles out of mud: practical access pattern privacy and correctness on untrusted storage. In: Proceedings of the CCS (2008)
  20.Williams, P., Sion, R., Tomescu, A.: PrivateFS: a parallel oblivious file system. In: Proceedings of the CCS (2012)
  
• 作者单位：Qiumao Ma (17)
  Wensheng Zhang (17)
  Jinsheng Zhang (17)
  
  17. Department of Computer Science, Iowa State University, Ames, USA
  
• 丛书名：Network and System Security
• ISBN：978-3-319-46298-1
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9955

文摘

Oblivious RAM (ORAM) is a security-provable model that can be used to protect a client’s access pattern to remote storage. Existing ORAM constructions were designed mainly for communication efficiency, but the server-side storage efficiency was generally neglected. This paper proposes DF-ORAM, which has the following features when N blocks each of B bits are outsourced: (i) server-side storage overhead is 3N bits (i.e., no dummy blocks); (ii) no server-side computational cost; (iii) server-client communication cost is \(O(\log N\cdot B)\) bit per query; and (iv) client-side storage cost is \(O(\lambda \cdot B)\) bits where \(\lambda \) is a security parameter. Asymptotical and implementation-based evaluation demonstrate DF-ORAM to be the most communication-efficient and storage-efficient one among the existing ORAMs that do not require server-side computation.