Database access pattern protection without full-shuffles

• المؤلفون الرئيسيون: DING, Xuhua, YANG, Yanjiang, DENG, Robert H.
• التنسيق: text
• اللغة: English
• منشور في: Institutional Knowledge at Singapore Management University 2011
• الموضوعات: Database; data privacy; information security.; Information Security
• الوصول للمادة أونلاين: https://ink.library.smu.edu.sg/sis_research/1362; https://ink.library.smu.edu.sg/context/sis_research/article/2361/viewcontent/Database_access_pattern_protection_without_full_shuffles.pdf

Privacy protection is one of the fundamental security requirements for database outsourcing. A major threat is information leakage from database access patterns generated by query executions. The standard private information retrieval (PIR) schemes, which are widely regarded as theoretical solutions, entail O(n) computational overhead per query for a database with items. Recent works propose to protect access patterns by introducing a trusted component with constant storage size. The resulting privacy assurance is as strong as PIR, though with O(1) online computation cost, they still have O(n) amortized cost per query due to periodically full database shuffles. In this paper, we design a novel scheme in the same model with provable security, which only shuffles a portion of the database. The amortized server computational complexity is reduced to With a secure storage storing thousands of items, our scheme can protect the access pattern privacy of databases of billions of entries, at a lower cost than those using ORAM-based poly-logarithm algorithms.