A Range Query Method for Data Access Pattern Protection Based on Uniform Access Frequency Distribution

Zhao Chang

¹ School of Computer Science and Technology, Xidian University, Xi’an, Shaanxi, 710071, China

² Shandong Institute of Standardization, Jinan, Shandong, 250013, China

Data encryption is necessary to keep user information secure and private on the cloud. However, adversaries can still learn valuable information about the encrypted data by observing data access patterns. To solve this issue, Oblivious RAMs (ORAMs) are proposed to hide access patterns. However, ORAMs are expensive and not suitable for deployment in a large database. In this work, we propose a range query algorithm while providing data access pattern protection based on uniform access frequency. In the preprocessing, multiple key-value pairs in the database are grouped and stored in each storage module, and we make copies for frequently accessed key-value pairs and also add some dummy key-value pairs on each storage module. In the online query processing, according to the range query length of the received query access request, we visit the specific storage module for the query and obtain the query result. Based on the techniques above, our method makes the uniform distribution of access frequency of data blocks in the database and achieves a security guarantee as strong as the state-of-the-art method. Compared with data queries that do not provide data access pattern protection, the ratio of network communication overhead is constant rather than logarithmic in ORAMs.

Data access pattern, data security, range query

Jing Yan, Zhao Chang, Ke Cheng, and Shuguang Wang (2023). A Range Query Method for Data Access Pattern Protection Based on Uniform Access Frequency Distribution. Journal of Networking and Network Applications, Volume 3, Issue 1, pp. 11–18. https://doi.org/10.33969/J-NaNA.2023.030102.

[1] A. Arasu, K. Eguro, M. Joglekar, R. Kaushik, D. Kossmann, and R. Ramamurthy, “Transaction processing on confidential data using Cipherbase,” in ICDE, 2015, pp. 435–446.

[2] A. Arasu, S. Blanas, K. Eguro, M. Joglekar, R. Kaushik, D. Kossmann, R. Ramamurthy, P. Upadhyaya, and R. Venkatesan, “Secure database-as-a-service with Cipherbase,” in SIGMOD, 2013, pp. 1033–1036.

[3] R. A. Popa, C. M. S. Redfield, N. Zeldovich, and H. Balakrishnan, “CryptDB: Protecting confidentiality with encrypted query processing,” in SOSP, 2011, pp. 85–100.

[4] S. Bajaj and R. Sion, “TrustedDB: A trusted hardware-based database with privacy and data confidentiality,” TKDE, vol. 26, no. 3, pp. 752–765, 2014.

[5] Z. He, W. K. Wong, B. Kao, D. W. Cheung, R. Li, S. Yiu, and E. Lo, “SDB: A secure query processing system with data interoperability,” PVLDB, vol. 8, no. 12, pp. 1876–1879, 2015.

[6] S. Tu, M. F. Kaashoek, S. Madden, and N. Zeldovich, “Processing analytical queries over encrypted data,” PVLDB, vol. 6, no. 5, pp. 289–300, 2013.

[7] A. Arasu, K. Eguro, R. Kaushik, and R. Ramamurthy, “Querying encrypted data,” in SIGMOD, 2014, pp. 1259–1261.

[8] H. Hacig¨um¨us, B. R. Iyer, C. Li, and S. Mehrotra, “Executing SQL over encrypted data in the database-service-provider model,” in SIGMOD, 2002, pp. 216–227.

[9] B. Yao, F. Li, and X. Xiao, “Secure nearest neighbor revisited,” in ICDE, 2013, pp. 733–744.

[10] W. K. Wong, B. Kao, D. W. Cheung, R. Li, and S. Yiu, “Secure query processing with data interoperability in a cloud database environment,” in SIGMOD, 2014, pp. 1395–1406.

[11] Z. Chang, D. Xie, and F. Li, “Oblivious RAM: A dissection and experimental evaluation,” PVLDB, vol. 9, no. 12, pp. 1113–1124, 2016.

[12] W. Zheng, A. Dave, J. G. Beekman, R. A. Popa, J. E. Gonzalez, and I. Stoica, “Opaque: An oblivious and encrypted distributed analytics platform,” in NSDI, 2017, pp. 283–298.

[13] A. Arasu and R. Kaushik, “Oblivious query processing,” in ICDT, 2014, pp. 26–37.

[14] T. Hoang, C. D. Ozkaptan, G. Hackebeil, and A. A. Yavuz, “Efficient oblivious data structures for database services on the cloud,” IEEE Trans. Cloud Computing, 2018.

[15] Z. Chang, D. Xie, F. Li, J. M. Phillips, and R. Balasubramonian, “Efficient oblivious query processing for range and knn queries,” IEEE Trans. Knowl. Data Eng., vol. 34, no. 12, pp. 5741–5754, 2022.

[16] O. Goldreich, “Towards a theory of software protection and simulation by oblivious RAMs,” in STOC, 1987, pp. 182–194.

[17] R. Ostrovsky, “Efficient computation on oblivious RAMs,” in STOC, 1990, pp. 514–523.

[18] P. Grubbs, A. Khandelwal, M. Lacharit´e, L. Brown, L. Li, R. Agarwal, and T. Ristenpart, “Pancake: Frequency smoothing for encrypted data stores,” in 29th USENIX Security Symposium, USENIX Security 2020, August 12-14, 2020, S. Capkun and F. Roesner, Eds., 2020, pp. 2451–2468.

[19] A. Nadeem and M. Y. Javed, “A performance comparison of data encryption algorithms,” in 2005 international Conference on information and communication technologies. IEEE, 2005, pp. 84–89.

[20] L. Bouganim et al., “Database encryption,” 2009.

[21] E. Stefanov, M. van Dijk, E. Shi, C. W. Fletcher, L. Ren, X. Yu, and S. Devadas, “Path ORAM: An extremely simple oblivious RAM protocol,” in CCS, 2013, pp. 299–310.

[22] P. Williams, R. Sion, and A. Tomescu, “PrivateFS: A parallel oblivious file system,” in CCS, 2012, pp. 977–988.

[23] J. R. Lorch, B. Parno, J. W. Mickens, M. Raykova, and J. Schiffman, “Shroud: Ensuring private access to large-scale data in the data center,” in FAST, 2013, pp. 199–214.

[24] E. Stefanov and E. Shi, “ObliviStore: High performance oblivious cloud storage,” in S&P, 2013, pp. 253–267.

[25] E. Stefanov, E. Shi, and D. X. Song, “Towards practical oblivious RAM,” in NDSS, 2012.

[26] V. Bindschaedler, M. Naveed, X. Pan, X. Wang, and Y. Huang, “Practicing oblivious access on cloud storage: the gap, the fallacy, and the new way forward,” in CCS, 2015, pp. 837–849.

[27] C. Sahin, V. Zakhary, A. E. Abbadi, H. Lin, and S. Tessaro, “TaoStore: Overcoming asynchronicity in oblivious data storage,” in S&P, 2016, pp. 198–217.

[28] A. Shafiee, R. Balasubramonian, M. Tiwari, and F. Li, “Secure DIMM: moving ORAM primitives closer to memory,” in HPCA, 2018, pp. 428–440.

[29] Y. Li and M. Chen, “Privacy preserving joins,” in ICDE, 2008, pp. 1352–1354.

[30] D. Xie, G. Li, B. Yao, X. Wei, X. Xiao, Y. Gao, and M. Guo, “Practical private shortest path computation based on oblivious storage,” in ICDE, 2016, pp. 361–372.

[31] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private information retrieval,” J. ACM, vol. 45, no. 6, pp. 965–981, 1998.

[32] P. Williams and R. Sion, “Usable PIR,” in NDSS, 2008.

[33] S. Sasy, S. Gorbunov, and C. W. Fletcher, “ZeroTrace: Oblivious memory primitives from intel SGX,” in NDSS, 2018.

[34] N. Crooks, M. Burke, E. Cecchetti, S. Harel, R. Agarwal, and L. Alvisi, “Obladi: Oblivious serializable transactions in the cloud,” in OSDI, 2018, pp. 727–743.

[35] X. S. Wang, Y. Huang, T.-H. H. Chan, A. Shelat, and E. Shi, “SCORAM: Oblivious RAM for secure computation,” in CCS, 2014, pp. 191–202. 

[36] C. Liu, X. S. Wang, K. Nayak, Y. Huang, and E. Shi, “ObliVM: A programming framework for secure computation,” in S&P, 2015, pp. 359–376.

[37] J. Bater, G. Elliott, C. Eggen, S. Goel, A. N. Kho, and J. Rogers, “SMCQL: secure query processing for private data networks,” PVLDB, vol. 10, no. 6, pp. 673–684, 2017.

[38] N. Volgushev, M. Schwarzkopf, B. Getchell, M. Varia, A. Lapets, and A. Bestavros, “Conclave: Secure multi-party computation on big data,” in EuroSys, 2019, pp. 3:1–3:18.

[39] Q. Ye, H. Hu, X. Meng, and H. Zheng, “PrivKV: Key-value data collection with local differential privacy,” in S&P, 2019.

[40] C. Sahin, T. Allard, R. Akbarinia, A. E. Abbadi, and E. Pacitti, “A differentially private index for range query processing in clouds,” in ICDE, 2018, pp. 857–868.

[41] N. M. Johnson, J. P. Near, and D. Song, “Towards practical differential privacy for SQL queries,” PVLDB, vol. 11, no. 5, pp. 526–539, 2018.

[42] J. Bater, X. He, W. Ehrich, A. Machanavajjhala, and J. Rogers, “Shrinkwrap: Efficient SQL query processing in differentially private data federations,” PVLDB, vol. 12, no. 3, pp. 307–320, 2018.

[43] G. Cormode, S. Jha, T. Kulkarni, N. Li, D. Srivastava, and T. Wang, “Privacy at scale: Local differential privacy in practice,” in SIGMOD, 2018, pp. 1655–1658.

[44] T. Wang, J. Blocki, N. Li, and S. Jha, “Locally differentially private protocols for frequency estimation,” in USENIX Security, 2017, pp. 729–745.

[45] R. Chen, H. Li, A. K. Qin, S. P. Kasiviswanathan, and H. Jin, “Private spatial data aggregation in the local setting,” in ICDE, 2016, pp. 289–300.

[46] N. Wang, X. Xiao, Y. Yang, J. Zhao, S. C. Hui, H. Shin, J. Shin, and G. Yu, “Collecting and analyzing multidimensional data with local differential privacy,” in ICDE, 2019, pp. 638–649.

[47] T. Wang, B. Ding, J. Zhou, C. Hong, Z. Huang, N. Li, and S. Jha, “Answering multi-dimensional analytical queries under local differential privacy,” in SIGMOD, 2019, pp. 159–176.

[48] F. X. Standaert, “Introduction to side-channel attacks,” in Secure inte-grated circuits and systems. Springer, 2010, pp. 27–42.