Anonymous RAM

详细信息    查看全文

• 关键词：Anonymity ; Access privacy ; Oblivious RAM ; Out ; sourced data ; (Universal) Re ; randomizable encryption ; Oblivious PRF
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9878
• 期：1
• 页码：344-362
• 全文大小：773 KB
• 参考文献：1.Backes, M., Herzberg, A., Kate, A., Pryvalov, I.: Anonymous RAM (extended version). Cryptology ePrint Archive, Report 2016/678 (2016)
  2.Bindschaedler, V., Naveed, M., Pan, X., Wang, X., Huang, Y.: Practicing oblivious access on cloud storage: the gap, the fallacy, and the new way forward. In: CCS, pp. 837–849 (2015)
  3.Boneh, D.: The decision Diffie-Hellman problem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 48–63. Springer, Heidelberg (1998)CrossRef
  4.Boyle, E., Chung, K.-M., Pass, R.: Oblivious parallel RAM and applications. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016-A. LNCS, vol. 9563, pp. 175–204. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49099-0_​7 CrossRef
  5.Camenisch, J., Stadler, M.: Proof systems for general statements about discrete logarithms. Technical report, TR260. Dept. of Computer Science, ETH Zürich, March 1997
  6.Catalano, D., Gennaro, R.: New efficient and secure protocols for verifiable signature sharing and other applications. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 105–120. Springer, Heidelberg (1998)CrossRef
  7.Chaum, D.: Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM 4(2), 84–88 (1981)CrossRef
  8.Chaum, D.: The dining cryptographers problem: unconditional sender and recipient untraceability. J. Cryptology 1(1), 65–75 (1988)MathSciNet CrossRef MATH
  9.Chaum, D., Pedersen, T.P.: Wallet databases with observers. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 89–105. Springer, Heidelberg (1993)CrossRef
  10.Chen, B., Lin, H., Tessaro, S.: Oblivious parallel RAM: improved efficiency and generic constructions. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016-A. LNCS, vol. 9563, pp. 205–234. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49099-0_​8 CrossRef
  11.Chung, K.-M., Liu, Z., Pass, R.: Statistically-secure ORAM with \(\tilde{O}(\log ^2 n)\) overhead. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 62–81. Springer, Heidelberg (2014)
  12.Cramer, R., Damgård, I.B., Schoenmakers, B.: Proof of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994)
  13.Danezis, G., Dingledine, R., Mathewson, N.: Mixminion: design of a type III anonymous remailer protocol. In: Security and Privacy (S&P), pp. 2–15 (2003)
  14.De Santis, A., Di Crescenzo, G., Persiano, G., Yung, M.: On monotone formula closure of SZK. In: FOCS, pp. 454–465 (1994)
  15.Dingledine, R., Mathewson, N., Syverson, P.: Tor: the second-generation onion router. In: Usenix Security, pp. 303–320 (2004)
  16.Dodis, Y., Yampolskiy, A.: A verifiable random function with short proofs and keys. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 416–431. Springer, Heidelberg (2005)CrossRef
  17.Franz, M., Williams, P., Carbunar, B., Katzenbeisser, S., Peter, A., Sion, R., Sotakova, M.: Oblivious outsourced storage with delegation. In: Danezis, G. (ed.) FC 2011. LNCS, vol. 7035, pp. 127–140. Springer, Heidelberg (2012)CrossRef
  18.Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 303–324. Springer, Heidelberg (2005)CrossRef
  19.Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM (JACM) 43(3), 431–473 (1996)MathSciNet CrossRef MATH
  20.Golle, P., Jakobsson, M., Juels, A., Syverson, P.: Universal re-encryption for mixnets. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 163–178. Springer, Heidelberg (2004)CrossRef
  21.Goodrich, M.T.: Randomized shellsort: a simple data-oblivious sorting algorithm. J. ACM (JACM) 58(6), 27 (2011)MathSciNet CrossRef MATH
  22.Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Oblivious RAM simulation with efficient worst-case access overhead. In: ACM CCSW, pp. 95–100 (2011)
  23.Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Privacy-preserving group data access via stateless oblivious RAM simulation. In: SODA, pp. 157–167 (2012)
  24.Jarecki, S., Liu, X.: Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 577–594. Springer, Heidelberg (2009)CrossRef
  25.Jinsheng, Z., Wensheng, Z., Qiao, D.: A Multi-user Oblivious RAM for outsourced data (2014). http://​lib.​dr.​iastate.​edu/​cs_​techreports/​262/​
  26.Kushilevitz, E., Lu, S., Ostrovsky, R.: On the (in) security of hash-based oblivious RAM and a new balancing scheme. In: SODA, pp. 143–156 (2012)
  27.Lu, S., Ostrovsky, R.: Distributed oblivious RAM for secure two-party computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 377–396. Springer, Heidelberg (2013)CrossRef
  28.Maffei, M., Malavolta, G., Reinert, M., Schröder, D.: Privacy and access control for outsourced personal records. In: Security and Privacy (S&P), pp. 341–358 (2015)
  29.Ostrovsky, R.: Efficient computation on oblivious RAMs. In: STOC, pp. 514–523 (1990)
  30.Pinkas, B., Reinman, T.: Oblivious RAM revisited. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 502–519. Springer, Heidelberg (2010)CrossRef
  31.Prabhakaran, M., Rosulek, M.: Rerandomizable RCCA encryption. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 517–534. Springer, Heidelberg (2007)CrossRef
  32.Sahin, C., Zakhary, V., El Abbadi, A., Lin, H.R., Tessaro, S.: Taostore: Overcoming asynchronicity in oblivious data storage. In: Security and Privacy (S&P) (2016)
  33.Schnorr, C.P.: Efficient signature generation by smart cards. J. Cryptology 4(3), 161–174 (1991)MathSciNet CrossRef MATH
  34.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, vol. 7073, pp. 197–214. Springer, Heidelberg (2011)CrossRef
  35.Stefanov, E., Shi, E.: ObliviStore: High performance oblivious cloud storage. In: Security and Privacy (S&P), pp. 253–267 (2013)
  36.Stefanov, E., Van Dijk, M., Shi, E., Fletcher, C., Ren, L., Yu, X., Devadas, S.: Path oram: an extremely simple oblivious ram protocol. In: CCS, pp. 299–310 (2013)
  37.The Tor project (2003). https://​www.​torproject.​org/​ . Accessed Feb 2016
  38.Wang, X., Chan, T.H., Shi, E.: Circuit ORAM: on tightness of the goldreich-ostrovsky lower bound. In: CCS, pp. 850–861 (2015)
  39.Williams, P., Sion, R., Tomescu, A.: PrivateFS: a parallel oblivious file system. In: CCS, pp. 977–988 (2012)
  
• 作者单位：Michael Backes (17) (18)
  Amir Herzberg (19)
  Aniket Kate (20)
  Ivan Pryvalov (17)
  
  17. CISPA, Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
  18. MPI-SWS, Saarland Informatics Campus, Saarbrücken, Germany
  19. Bar-Ilan University, Ramat Gan, Israel
  20. Purdue University, West Lafayette, USA
  
• 丛书名：Computer Security – ESORICS 2016
• ISBN：978-3-319-45744-4
• 刊物类别：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
• 卷排序：9878

文摘

We define the concept of and present provably secure constructions for Anonymous RAM (AnonRAM), a novel multi-user storage primitive that offers strong privacy and integrity guarantees. AnonRAM combines privacy features of anonymous communication and oblivious RAM (ORAM) schemes, allowing it to protect, simultaneously, the privacy of content, access patterns and user’s identity, from curious servers and from other (even adversarial) users. AnonRAM further protects integrity, i.e., it prevents malicious users from corrupting data of other users. We present two secure AnonRAM schemes, differing in design and time complexity. The first scheme has a simpler design; like efficient ORAM schemes, its time complexity is poly-logarithmic in the number of cells (per user); however, it is linear in the number of users. The second AnonRAM scheme reduces the overall complexity to poly-logarithmic in the total number of cells (of all users) at the cost of requiring two (non-colluding) servers.