Hiding Access Patterns in Range Queries Using Private Information Retrieval and ORAM

详细信息    查看全文

• 关键词：Privacy preserving range queries ; Private information retrieval ; Oblivious RAM ; Data privacy ; Parallel computing
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9604
• 期：1
• 页码：253-270
• 全文大小：632 KB
• 参考文献：1.Boldyreva, A., Chenette, N., Lee, Y., O’Neill, A.: Order-preserving symmetric encryption. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 224–241. Springer, Heidelberg (2009). http://​dx.​doi.​org/​10.​1007/​978-3-642-01001-9_​13 CrossRef
  2.Boneh, D., Waters, B.: Conjunctive, subset, and range queries on encrypted data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 535–554. Springer, Heidelberg (2007). http://​dl.​acm.​org/​citation.​cfm?​id=​1760749.​1760788 CrossRef
  3.Damgård, I., Jurik, M.: A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001). http://​dl.​acm.​org/​citation.​cfm?​id=​648118.​746742 CrossRef
  4.Hacıgümüş, H., Iyer, B., Li, C., Mehrotra, S.: Executing SQL over encrypted data in the database-service-provider model. In: Proceedings of 2002 ACM SIGMOD International Conference on Management of Data, SIGMOD 2002, Madison, Wisconsin, 3–6 June 2002, pp. 216–227. ACM (2002). http://​doi.​acm.​org/​10.​1145/​564691.​564717
  5.Hore, B., Mehrotra, S., Canım, M., Kantarcıoğlu, M.: Secure multidimensional range queries over outsourced data. VLDB J. 21(3), 333–358 (2012). http://​dx.​doi.​org/​10.​1007/​s00778-011-0245-7 CrossRef
  6.Lipmaa, H.: First CPIR protocol with data-dependent computation. In: Lee, D., Hong, S. (eds.) ICISC 2009. LNCS, vol. 5984, pp. 193–210. Springer, Heidelberg (2010). http://​dl.​acm.​org/​citation.​cfm?​id=​1883749.​1883769 CrossRef
  7.Stefanov, E., van Dijk, M., Shi, E., Fletcher, C., Ren, L., Yu, X., Devadas, S.: Path ORAM: an extremely simple oblivious RAM protocol. In: Proceedings of 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS 2013, Berlin, Germany, 4–8 November 2013. pp. 299–310. ACM (2013). http://​doi.​acm.​org/​10.​1145/​2508859.​2516660
  8.TPC-H: Decision Support Benchmark. http://​www.​tpc.​org/​tpch
  9.Ünal, E., Savaş, E.: On acceleration and scalability of number theoretic private information retrieval. IEEE Trans. Parallel Distrib. Syst. 27(6), 1727–1741 (2016). doi:10.​1109/​TPDS.​2015.​2456021 CrossRef
  10.Capitani, D., di Vimercati, S., Foresti, S., Paraboschi, S., Pelosi, G., Samarati, P.: Efficient and private access to outsourced data. In: Proceedings of 2011 31st International Conference on Distributed Computing Systems, ICDCS 2011, pp. 710–719 (2011). http://​dx.​doi.​org/​10.​1109/​ICDCS.​2011.​37
  
• 作者单位：Gamze Tillem (19)
  Ömer Mert Candan (19)
  Erkay Savaş (19)
  Kamer Kaya (19)
  
  19. Sabancı University, İstanbul, Turkey
  
• 丛书名：Financial Cryptography and Data Security
• ISBN：978-3-662-53357-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
• 卷排序：9604

文摘

We study the problem of privacy preserving range search that provides data, query, and response confidentiality to the users for range queries. We propose two methods based on Private Information Retrieval (PIR) and Oblivious RAM (ORAM) techniques. For PIR-based queries, Lipmaa’s computationally-private information retrieval (CPIR) scheme is employed. For the ORAM-based method, Stefanov et al.’s Path ORAM scheme is adapted to enable privacy preserving range search. Our analyses show that from the computational point of view, the ORAM-based method performs much better due to cheap server operations. However, CPIR utilizes the bandwidth better especially for large databases, its security definitions are more formal, and it is more flexible for various settings with multiple clients and/or bandwidth limitations. In this work, to make CPIR a practical alternative for large databases, we improve its performance via shared memory OpenMP and distributed memory OpenMP-MPI parallelization with a scalable data/task partitioning.