微信服务号

微信订阅号

2025年3月26日 8:36 星期三
首页 > 过刊浏览>2018年第29卷第9期 >2753-2777. DOI:10.13328/j.cnki.jos.005591
PDF HTML阅读 XML下载 导出引用 引用提醒
不经意随机访问机研究综述
作者:
作者简介:

吴鹏飞(1994-),男,江苏淮安人,博士生,主要研究领域为分布式系统安全,隐私保护,大数据安全;沈晴霓(1970-),女,博士,教授,博士生导师,CCF高级会员,主要研究领域为操作系统与虚拟化安全,云计算,大数据安全与隐私,可信计算;秦嘉(1993-),男,硕士生,主要研究领域为加密共享,隐私保护;钱文君(1994-),女,博士生,主要研究领域为可信计算,系统安全,大数据计算安全,隐私保护;李聪(1990-),男,博士生,CCF学生会员,主要研究领域为公钥密码,区块链,云计算安全;吴中海(1968-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为大数据系统与分析,大数据与云安全,嵌入式系统.

通讯作者:

吴中海,E-mail:wuzh@ss.pku.edu.cn;沈晴霓,E-mail:qingnishen@ss.pku.edu.cn

基金项目:

国家自然科学基金（61672062，61232005）


Survey of Oblivious RAM
Author:
Fund Project:

National Natural Science Foundation of China (61672062, 61232005)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [77]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    随着云计算与大数据技术的发展，隐私保护越来越受到人们的关注.加密是一种常见的保护数据隐私的方法，但是单纯地利用加密手段并不能抵抗所有类型的攻击.攻击者可以通过观察用户对数据的访问模式来推断隐私信息，其中包括数据的重要程度、数据的关联性，甚至是加密数据的内容等.不经意随机访问机是一种重要的保护访问模式的手段，它通过混淆每一次访问过程，使其与随机访问不可区分，从而保护真实访问中的访问操作、访问位置等信息.不经意随机访问机在安全云存储系统以及安全计算领域有着非常重要的作用.利用不经意随机访问机可以降低攻击者通过访问模式推测隐私信息的可能性，减小系统受到的攻击面，从而提供更安全更完整的服务.对不经意随机访问机的研究与应用进行综述，主要介绍了不经意随机访问机的相关概念以及设计方法，重点分析并总结了目前学术界研究的性能优化的常见策略及其优劣性，主要包括针对客户端与服务器的平均带宽与最坏情况带宽优化、存储开销优化以及交互轮数优化等方面.同时讨论了将不经意随机访问机应用于安全存储系统的一般性问题，如数据完整性保护以及支持多用户并发访问等，也讨论了将其应用于安全计算领域的问题，如安全计算协议设计以及不经意数据结构的设计等；最后，对不经意随机访问机未来的研究方向进行了展望.

    Abstract:

    With the development of cloud computing and big data technology, privacy protection draws more people's attention. Data encryption is a common way to protect data privacy, but solely using encryption cannot resist all types of attacks. Adversary can observe the access pattern on how users access to the data, to infer the private information including the importance of the data, the relevance between the data and even the plaintext of encrypted data. Oblivious RAM (ORAM) is an important method to protect the access pattern, including access operations and access locations, by obscuring an actual access, which makes adversary unable to distinguish it from a random one. ORAM makes an important role in designing secure cloud storage systems and secure computation. ORAM can reduce the possibility of the adversary inferring the private information through the access pattern and reduce the attack surface of the system, so as to provide a safer and more complete service. This paper summarizes the researches and application settings of the ORAM, mainly introducing the relevant concepts of the model as well as design methods with focus placed on analyzing and summarizing common strategies to optimize the model and their advantages and disadvantages, as well as optimizations for amortized and worst-case bandwidth between client and server, storage overheads reduction and round-trips reduction. Moreover, this paper discusses general issues of the ORAM used for secure storage system designing including data integrity and concurrent accesses for multi-clients. The paper also discusses some issues of the ORAM used for secure computation, including secure computation protocols designing and oblivious data structure designing, and finally makes a conclusion for the future research directions of the ORAM.

    参考文献
    [1] Wu X, Xu L, Zhang X. Poster:A certificateless proxy re-encryption scheme for cloud-based data sharing. In:Proc. of the 18th ACM Conf. on Computer and Communications Security. ACM Press, 2011. 869-872.[doi:10.1145/2046707.2093514]
    [2] Jung T, Li XY, Wan Z, Wan M. Control cloud data access privilege and anonymity with fully anonymous attribute-based encryption. IEEE Trans. on Information Forensics and Security, 2015,10(1):190-199.[doi:10.1109/tifs.2014.2368352]
    [3] Pinkas B, Reinman T. Oblivious ram revisited. In:Proc. of the 30th Annual Cryptology Conf., Vol.6223. Berlin, Heidelberg:Springer-Verlag, 2010. 502-519.[doi:10.1007/978-3-642-14623-7_27]
    [4] Islam MS, Kuzu M, Kantarcioglu M. Access pattern disclosure on searchable encryption:Ramification, attack and mitigation. In:Proc. of the 18th Network and Distributed System Security Symp., Vol.20. 2012. 1-15.[doi:10.1.1.673.8809]
    [5] Dautrich Jr JL, Ravishankar CV. Compromising privacy in precise query protocols. In:Proc. of the 16th Int'l Conf. on Extending Database Technology. ACM Press, 2013. 155-166.[doi:10.1145/2452376.2452397]
    [6] Zheng W, Dave A, Beekman JG, et al. Opaque:An oblivious and encrypted distributed analytics platform. In:Proc. of the 14th USENIX Symp. on Networked Systems Design and Implementation. USENIX Association, 2017. 283-298.
    [7] Shaon F, Kantarcioglu M, et al. SGX-BigMatrix:A practical encrypted data analytic framework with trusted processors. In:Proc. of the 24st ACM Conf. on Computer and Communications Security. ACM Press, 2017. 1211-1228.[doi:10.1145/3133956. 3134095]
    [8] Gordon SD, Katz J, Kolesnikov V, et al. Secure two-party computation in sublinear (amortized) time. In:Proc. of the 19th ACM Conf. on Computer and Communications Security. ACM Press, 2012. 513-524.[doi:10.1145/2382196.2382251]
    [9] Wang X, Chan H, Shi E. Circuit ORAM:On tightness of the goldreich-ostrovsky lower bound. In:Proc. of the 22nd ACM Conf. on Computer and Communications Security. ACM Press, 2015. 850-861.[doi:10.1145/2810103.2813634]
    [10] Oblivious RAM. https://en.wikipedia.org/wiki/Oblivious_ram
    [11] Ohrimenko O, Costa M, Fournet C, et al. Observing and preventing leakage in MapReduce. In:Proc. of the 22nd ACM Conf. on Computer and Communications Security. ACM Press, 2015. 1570-1581.[doi:10.1145/2810103.2813695]
    [12] Dinh TTA, Saxena P, Chang EC, et al. M2R:Enabling stronger privacy in MapReduce computation. In:Proc. of the 24th Symp. on USENIX Security. USENIX Association, 2015. 447-462.
    [13] Goldreich O, Ostrovsky R. Software protection and simulation on oblivious RAMs. Journal of the ACM (JACM), 1996,43(3):431-473.[doi:10.1145/233551.233553]
    [14] Kushilevitz E, Lu S, Ostrovsky R. On the (in) security of hash-based oblivious RAM and a new balancing scheme. In:Proc. of the 23rd Annual ACM-SIAM Symp. on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2012. 143-156.[doi:10.1137/1.9781611973099.13]
    [15] Gentry C, Halevi S, Jutla C, et al. Private database access with he-over-oram architecture. In:Proc. of the 13th Int'l Conf. on Applied Cryptography and Network Security. Springer-Verlag, 2015. 172-191.[doi:/10.1007/978-3-319-28166-7_9]
    [16] Stefanov E, Shi E, Song D. Towards practical oblivious RAM. In:Proc. of the 17th Network and Distributed System Security Symp. 2011.
    [17] Stefanov E, Dijk MV, Shi E, et al. Path ORAM:An extremely simple oblivious RAM protocol. In:Proc. of the 20th ACM Conf. on Computer and Communications Security. ACM Press, 2013. 299-310.[doi:10.1145/2508859.2516660]
    [18] Garg S, Mohassel P, Papamanthou C. TWORAM:Round-optimal oblivious RAM with applications to searchable encryption. IACR Cryptology ePrint Archive, 2015. 1010.
    [19] Moataz T, Mayberry T, Blass EO. Constant communication ORAM with small blocksize. In:Proc. of the 22nd ACM Conf. on Computer and Communications Security. ACM Press, 2015. 862-873.[doi:10.1145/2810103.2813701]
    [20] Stefanov E, Shi E. Oblivistore:High performance oblivious cloud storage. In:Proc. of the 34th IEEE Symp. on Security and Privacy. IEEE, 2013. 253-267.[doi:10.1109/SP.2013.25]
    [21] Zahur S, Wang X, Raykova M, et al. Revisiting square-root ORAM:Efficient random access in multi-party computation. In:Proc. of the 37th IEEE Symp. on Security and Privacy. IEEE, 2016. 218-234.[doi:10.1109/SP.2016.21]
    [22] Batcher KE. Sorting networks and their applications. In:Proc. of the Spring Joint Computer Conf. ACM Press, 1968. 307-314.[doi:10.1145/1468075.1468121]
    [23] Ajtai M, Komlós J, Szemerédi E. An O(nlogn) sorting network. In:Proc. of the 15th Annual ACM Symp. on Theory of Computing. ACM Press, 1983. 1-9.[doi:10.1145/800061.808726]
    [24] Goodrich MT. Randomized shellsort:A simple oblivious sorting algorithm. In:Proc. of the 21st Annual ACM-SIAM Symp. on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2010. 1262-1277.[doi:10.1137/1.9781611973075.101]
    [25] Ren L, Fletcher CW, Kwon A, et al. Constants count:Practical improvements to oblivious RAM. In:Proc. of the 24th USENIX Conf. on Security Symp. USENIX Association, 2015. 415-430.
    [26] Devadas S, Dijk MV, Fletcher CW, et al. Onion ORAM:A constant bandwidth blowup oblivious RAM. In:Proc. of the 13th Theory of Cryptography Conf. Springer-Verlag, 2016. 145-174.[doi:10.1007/978-3-662-49099-0_6]
    [27] Shi E, Chan THH, Stefanov E, et al. Oblivious RAM with O((logN)3) worst-case cost. In:Proc. of the 17th Int'l Conf. on Theory and Application of Cryptology and Information Security, Vol.7073. 2011. 197-214.[doi:10.1007/978-3-642-25385-0_11]
    [28] Hoang T, Ozkaptan CD, Yavuz AA, et al. S3ORAM:A computation-efficient and constant client bandwidth blowup ORAM with shamir secret sharing. In:Proc. of the 24th ACM Conf. on Computer and Communications Security. ACM Press, 2017. 491-505.[doi:10.1145/3133956.3134090]
    [29] Maffei M, Malavolta G, Reinert M, et al. Privacy and access control for outsourced personal records. In:Proc. of the 36th IEEE Symp. on Security and Privacy. IEEE, 2015. 341-358.[doi:10.1109/sp.2015.28]
    [30] Maffei M, Malavolta G, Reinert M, et al. Maliciously secure multi-client ORAM. IACR Cryptology ePrint Archive, 2017. 329.[doi:10.1007/978-3-319-61204-1_32]
    [31] Williams P, Sion R, Carbunar B. Building castles out of mud:Practical access pattern privacy and correctness on untrusted storage. In:Proc. of the 15th ACM Conf. on Computer and Communications Security. ACM Press, 2008. 139-148.[doi:10.1145/1455770. 1455790]
    [32] Williams P, Sion R. Access privacy and correctness on untrusted storage. ACM Trans. on Information and System Security, 2013, 16(3):12.[doi:10.1145/2535524]
    [33] Williams P, Sion R, Tomescu A. Privatefs:A parallel oblivious file system. In:Proc. of the 19th ACM Conf. on Computer and Communications Security. ACM Press, 2012. 977-988.[doi:10.1145/2382196.2382299]
    [34] Bindschaedler V, Naveed M, Pan X, et al. Practicing oblivious access on cloud storage:The gap, the fallacy, and the new way forward. In:Proc. of the 22nd ACM Conf. on Computer and Communications Security. ACM Press, 2015. 837-849.[doi:10.1145/2810103.2813649]
    [35] Sahin C, Zakhary V, Abbadi ElA, et al. Taostore:Overcoming asynchronicity in oblivious data storage. In:Proc. of the 37th IEEE Symp. on Security and Privacy. IEEE, 2016. 198-217.[doi:10.1109/SP.2016.20]
    [36] Ostrovsky R, Shoup V. Private information storage. In:Proc. of the 29th Annual ACM Symp. on Theory of Computing. ACM Press, 1997. 294-303.
    [37] Lu S, Ostrovsky R. Distributed oblivious RAM for secure two-party computation. In:Proc. of the 10th Conf. on Theory of Cryptography. Springer-Verlag, 2013. 377-396.[doi:10.1007/978-3-642-36594-2_22]
    [38] Keller M, Scholl P. Efficient, oblivious data structures for MPC. In:Proc. of the 21st Int'l Conf. on Theory and Application of Cryptology and Information Security. Springer-Verlag, 2014. 506-525.[doi:10.1007/978-3-662-45608-8_27]
    [39] Wang XS, Nayak K, Liu C, et al. Oblivious data structures. In:Proc. of the 21st ACM Conf. on Computer and Communications Security. ACM Press, 2014. 215-226.[doi:10.1145/2660267.2660314]
    [40] Boyle E, Gilboa N, Ishai Y. Function secret sharing. LNCS, 2015,9057:337-367.[doi:10.1007/978-3-662-46803-6_12]
    [41] Maas M, Love E, Stefanov E, et al. Phantom:Practical oblivious computation in a secure processor. In:Proc. of the 20th ACM Conf. on Computer and Communications Security. ACM Press, 2013. 311-324.[doi:10.1145/2508859.2516692]
    [42] Goodrich MT, Mitzenmacher M. Privacy-Preserving access of outsourced data via oblivious RAM simulation. In:Proc. of the 38th Int'l Colloquium on Automata, Languages, and Programming. Springer-Verlag, 2011. 576-587.[doi:10.1007/978-3-642-22012-8_46]
    [43] Pagh R, Rodler FF. Cuckoo hashing. In:Proc. of the 9th Annual European Symp. on Algorithms, Vol.2161. Springer-Verlag, 2001. 121-133.[doi:10.1007/3-540-44676-1_10]
    [44] Moataz T, Blass EO, Mayberry T. CHf-ORAM:A constant communication ORAM without homomorphic encryption. Technical Report, 2015/1116, Cryptology ePrint Archive, 2015.
    [45] Dautrich J, Stefanov E, Shi E. Burst ORAM:Minimizing ORAM response times for bursty access patterns. In:Proc. of the 23rd Symp. on USENIX Security. USENIX Association, 2014. 749-764.[doi:10.1007/BF02483924]
    [46] Gentry C, Goldman KA, Halevi S, et al. Optimizing ORAM and using it efficiently for secure computation. In:Proc. of the 13th Int'l Symp. on Privacy Enhancing Technologies, Vol.7981. Springer-Verlag, 2013. 1-18.[doi:10.1007/978-3-642-39077-7_1]
    [47] Mayberry T, Blass EO, Chan AH. Efficient private file retrieval by combining ORAM and PIR. In:Proc. of the 20th Network and Distributed System Security Symp. 2014.[doi:10.14722/ndss.2014.23033]
    [48] Dautrich J, Ravishankar C. Combining ORAM with PIR to minimize bandwidth costs. In:Proc. of the 5th ACM Conf. on Data and Application Security and Privacy. ACM Press, 2015. 289-296.[doi:10.1145/2699026.2699117]
    [49] Apon D, Katz J, Shi E, et al. Verifiable oblivious storage. In:Proc. of the 17th Int'l Conf. on Practice and Theory in Public-Key Cryptography. Springer-Verlag, 2014. 131-148.[doi:10.1007/978-3-642-54631-0_8]
    [50] Damgard I, Jurik M. A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. In:Proc. of the 4th Int'l Workshop on Practice and Theory in Public Key Cryptography, Vol.1992. Springer-Verlag, 2001. 119-136.[doi:10.1007/3-540-44586-2_9]
    [51] Goldberg I. Improving the robustness of private information retrieval. In:Proc. of the 28th IEEE Symp. on Security and Privacy. IEEE, 2007. 131-148.[doi:10.1109/SP.2007.23]
    [52] Abraham I, Fletcher CW, Nayak K, et al. Asymptotically tight bounds for composing ORAM with PIR. In:Proc. of the 20th Int'l Conf. on Practice and Theory in Public-Key Cryptography. Springer-Verlag, 2017. 91-120.[doi:10.1007/978-3-662-54365-8_5]
    [53] Boneh D, Mazieres D, Popa RA. Remote oblivious storage:Making oblivious RAM practical. Manuscript, 2011. http://dspace.mit.edu/bitstream/handle/1721.1/62006/MIT-CSAIL-TR-2011-018.pdf
    [54] Fletcher CW, Naveed M, Ren L, et al. Bucket ORAM:Single online roundtrip, constant bandwidth oblivious RAM. IACR Cryptology ePrint Archive, 2015. 1065.
    [55] Chung KM, Pass R. A simple ORAM. IACR Cryptology ePrint Archive, 2013. 243.
    [56] Chung KM, Liu Z, Pass R. Statistically-Secure ORAM with O(log2n) overhead. In:Proc. of the 20th Int'l Conf. on Theory and Application of Cryptology and Information Security. Springer-Verlag, 2014. 62-81.[doi:10.1007/978-3-662-45608-8_4]
    [57] Sanchez AM. Toward efficient data access privacy in the cloud. IEEE Communications Magazine, 2013,51(11):39-45.[doi:10.1109/MCOM.2013.6658650]
    [58] Moataz T, Mayberry T, Blass EO, et al. Resizable tree-based oblivious RAM. In:Proc. of the 19th Int'l Conf. on Financial Cryptography and Data Security. Springer-Verlag, 2015. 147-167.[doi:10.1007/978-3-662-47854-7_9]
    [59] Goodrich MT, Mitzenmacher M, Ohrimenko O, et al. Privacy-Preserving group data access via stateless oblivious RAM simulation. In:Proc. of the 23rd Annual ACM-SIAM Symp. on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2012, 13(Suppl 1):157-167.[doi:10.1137/1.9781611973099.14]
    [60] Williams P, Sion R, Sotakova M. Practical oblivious outsourced storage. ACM Trans. on Information and System Security, 2011, 14(2):20.[doi:10.1145/2019599.2019605]
    [61] Williams P, Sion R. Single round access privacy on outsourced storage. In:Proc. of the 19th ACM Conf. on Computer and Communications Security. ACM Press, 2012. 293-304.[doi:10.1145/2382196.2382229]
    [62] Stefanov E, Shi E. Multi-Cloud oblivious storage. In:Proc. of the 33rd ACM Conf. on Computer and Communications Security. ACM Press, 2013. 247-258.[doi:10.1145/2508859.2516673]
    [63] Sun XN, Jiang H, Xu QL. Multi-User binary tree based ORAM scheme. Ruan Jian Xue Bao/Journal of Software, 2016,27(6):1475-1486(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5002.htm[doi:10.13328/j.cnki.jos.005002]
    [64] Yao AC. Protocols for secure computations. In:Proc. of the 23rd Annual Symp. on Foundations of Computer Science. IEEE, 1982. 160-164.[doi:10.1109/SFCS.1982.88]
    [65] Goldwasser S, Micali S, Wigderson A. How to play any mental game, or a completeness theorem for protocols with an honest majority. In:Proc. of the 19th Annual ACM Symp. on Theory of Computing, Vol.87. ACM Press, 1987. 218-229.[doi:10.1145/28395.28420]
    [66] Faber S, Jarecki S, Kentros S, et al. Three-Party ORAM for secure computation. In:Proc. of the 21st Int'l Conf. on Theory and Application of Cryptology and Information Security. Springer-Verlag, 2015. 360-385.[doi:10.1007/978-3-662-48797-6_16]
    [67] Doerner J. Scaling ORAM for secure computation. In:Proc. of the 24th ACM Conf. on Computer and Communications Security. ACM Press, 2017. 523-535.[doi:10.1145/3133956.3133967]
    [68] Wang XS, Huang Y, Chan THH, et al. SCORAM:Oblivious RAM for secure computation. In:Proc. of the 21st ACM Conf. on Computer and Communications Security. ACM Press, 2014. 191-202.[doi:10.1145/2660267.2660365]
    [69] Xiao W, Dov G, Jonathan K. Simple and efficient two-server ORAM. IACR Cryptology ePrint Archive, 2018. 005.
    [70] Thang H, Ceyhun DO, Gabriel H, Attila AY. Efficient oblivious data structures for database services on the cloud. IACR Cryptology ePrint Archive, 2017. 1238.
    [71] Zhao C, Dong X, Li F. Oblivious ram:A dissection and experimental evaluation. In:Proc. of the 42nd Int'l Conf. on Very Large Databases. ACM Press, 2016. 1113-1124.[doi:10.14778/2994509.2994528]
    [72] Boyle E, Chung KM, Pass R. Oblivious parallel RAM and applications. In:Proc. of the 13th Theory of Cryptography Conf. Springer-Verlag, 2016. 175-204.[doi:10.1007/978-3-662-49099-0_7]
    [73] Malkhi D, Nisan N, Pinkas B, et al. Fairplay-A secure two-party computation system. In:Proc. of the 13th Symp. on USENIX Security. USENIX Association, 2004. 20-20.
    [74] Ben-David A, Nisan N, Pinkas B. FairplayMP:A system for secure multi-party computation. In:Proc. of the 15th ACM Conf. on Computer and Communications Security. ACM Press, 2008. 257-266.[doi:10.1145/1455770.1455804]
    [75] Bogdanov D, Laur S, Willemson J. Sharemind:A framework for fast privacy-preserving computations. In:Proc. of the 13th European Symp. on Research in Computer Security, Vol.5283. Springer-Verlag, 2008. 192-206.[doi:10.1007/978-3-540-88313-5_13]
    附中文参考文献:
    [63] 孙晓妮,蒋瀚,徐秋亮.基于二叉树存储的多用户ORAM方案.软件学报,2016,27(6):1475-1486. http://www.jos.org.cn/1000-9825/5002.htm[doi:10.13328/j.cnki.jos.005002]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

吴鹏飞,沈晴霓,秦嘉,钱文君,李聪,吴中海.不经意随机访问机研究综述.软件学报,2018,29(9):2753-2777

复制
分享
文章指标
  • 点击次数:4937
  • 下载次数: 8742
  • HTML阅读次数: 4884
  • 引用次数: 0
历史
  • 收稿日期:2018-01-03
  • 最后修改日期:2018-03-16
  • 在线发布日期: 2018-09-05
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19733224位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号