{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:33:00Z","timestamp":1767339180326,"version":"build-2065373602"},"reference-count":55,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2018,10,29]],"date-time":"2018-10-29T00:00:00Z","timestamp":1540771200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004919","name":"King Abdulaziz City for Science and Technology","doi-asserted-by":"publisher","award":["1-17-00-001-0004"],"award-info":[{"award-number":["1-17-00-001-0004"]}],"id":[{"id":"10.13039\/501100004919","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computers"],"abstract":"<jats:p>In this paper, we propose an advanced implementation of Path ORAM to hide the access pattern to outsourced data into the cloud. This implementation takes advantage of eventual data locality and popularity by introducing a small amount of extra storage at the client side. Two replacement strategies are used to manage this extra storage (cache): the Least Recently Used (LRU) and the Least Frequently Used (LFU). Using the same test bed, conducted experiments clearly show the superiority of the advanced implementation compared to the traditional Path ORAM implementation, even for a small cache size and reduced data locality. We then present a mathematical model that provides closed form solutions when data requests follow a Zipf distribution with non-null parameter. This model is showed to have a small and acceptable relative error and is then well validated by the conducted experimental results.<\/jats:p>","DOI":"10.3390\/computers7040056","type":"journal-article","created":{"date-parts":[[2018,10,29]],"date-time":"2018-10-29T11:10:41Z","timestamp":1540811441000},"page":"56","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Locality Aware Path ORAM: Implementation, Experimentation and Analytical Modeling"],"prefix":"10.3390","volume":"7","author":[{"given":"Kholoud","family":"Al-Saleh","sequence":"first","affiliation":[{"name":"College of Computer and Information Sciences, King Saud University, Riyadh 11451, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4937-7453","authenticated-orcid":false,"given":"Abdelfettah","family":"Belghith","sequence":"additional","affiliation":[{"name":"College of Computer and Information Sciences, King Saud University, Riyadh 11451, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,10,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Gao, C.Z., Cheng, Q., Li, X., and Xia, S.B. (2018). Cloud-assisted privacy-preserving profile-matching scheme under multiple keys in mobile social network. Cluster Comput., 1\u20139.","DOI":"10.1007\/s10586-017-1649-y"},{"key":"ref_2","unstructured":"Islam, M.S., Kuzu, M., and Kantarcioglu, M. (2012). Access Pattern Disclosure on Searchable Encryption: Ramification, Attack and Mitigation, NDSS."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R. (1990, January 13\u201317). Efficient Computation on Oblivious RAMs. Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA.","DOI":"10.1145\/100216.100289"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Goldreich, O. (1987, January 25\u201327). Towards a theory of software protection and simulation by oblivious RAMs. Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, New York, NY, USA.","DOI":"10.1145\/28395.28416"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1145\/233551.233553","article-title":"Software protection and simulation on oblivious RAMs","volume":"43","author":"Goldreich","year":"1996","journal-title":"J. ACM"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Rabin, T. (2010). Oblivious RAM Revisited. Advances in Cryptology\u2014CRYPTO 2010, Springer.","DOI":"10.1007\/978-3-642-14623-7"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., and Mitzenmacher, M. (2011). Privacy-preserving access of outsourced data via oblivious RAM simulation. International Colloquium on Automata, Languages, and Programming, Springer.","DOI":"10.1007\/978-3-642-22012-8_46"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., and Tamassia, R. (2012, January 17\u201319). Privacy-Preserving Group Data Access via Stateless Oblivious RAM Simulation. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan.","DOI":"10.1137\/1.9781611973099.14"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Lee, D.H., and Wang, X. (2011). Oblivious RAM with O((logN)3) Worst-Case Cost. Advances in Cryptology\u2014ASIACRYPT 2011, Springer.","DOI":"10.1007\/978-3-642-25385-0"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Lu, S., and Ostrovsky, R. (2012, January 17\u201319). On the (in)Security of Hash-based Oblivious RAM and a New Balancing Scheme. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan.","DOI":"10.1137\/1.9781611973099.13"},{"key":"ref_11","unstructured":"Stefanov, E., Shi, E., and Song, D. (arXiv preprint, 2011). Towards Practical Oblivious RAM, arXiv preprint."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Stefanov, E., van Dijk, M., Shi, E., Fletcher, C., Ren, L., Yu, X., and Devadas, S. (2013, January 4\u20138). Path ORAM: An Extremely Simple Oblivious RAM Protocol. Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, Berlin, Germany.","DOI":"10.1145\/2508859.2516660"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Wang, X.S., Huang, Y., Chan, T.H.H., Shelat, A., and Shi, E. (2014, January 3\u20137). SCORAM: Oblivious RAM for Secure Computation. Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA.","DOI":"10.1145\/2660267.2660365"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Liu, C., Wang, X.S., Nayak, K., Huang, Y., and Shi, E. (2015, January 17\u201321). Oblivm: A programming framework for secure computation. Proceedings of the 2015 IEEE Symposium on Security and Privacy, San Jose, CA, USA.","DOI":"10.1109\/SP.2015.29"},{"key":"ref_15","unstructured":"Ren, L., Fletcher, C., Kwon, A., Stefanov, E., Shi, E., van Dijk, M., and Devadas, S. (2015, January 12\u201314). Constants Count: Practical Improvements to Oblivious RAM. Proceedings of the 24th USENIX Security Symposium (USENIX Security \u201915), Washington, DC, USA."},{"key":"ref_16","unstructured":"Devadas, S., van Dijk, M., Fletcher, C.W., Ren, L., Shi, E., and Wichs, D. (2016). Onion ORAM: A constant bandwidth blowup oblivious RAM. Theory of Cryptography: Proceedings of the 13th International Conference, TCC 2016-A, Tel Aviv, Israel, 10\u201313 January 2016, Part II, Springer."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Xie, D., Li, G., Yao, B., Wei, X., Xiao, X., Gao, Y., and Guo, M. (2016, January 16\u201320). Practical private shortest path computation based on oblivious storage. Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering (ICDE), Helsinki, Finland.","DOI":"10.1109\/ICDE.2016.7498254"},{"key":"ref_18","unstructured":"Asharov, G., Chan, T.H.H., Nayak, K., Pass, R., Ren, L., and Shi, E. (2018, May 12). Oblivious Computation with Data Locality. Available online: https:\/\/eprint.iacr.org\/2017\/772."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"18:1","DOI":"10.1145\/3177872","article-title":"Path ORAM: An Extremely Simple Oblivious RAM Protocol","volume":"65","author":"Stefanov","year":"2018","journal-title":"J. ACM"},{"key":"ref_20","first-page":"997","article-title":"Ring ORAM: Closing the Gap Between Small and Large Client Storage Oblivious RAM","volume":"2014","author":"Ren","year":"2014","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Bao, C., and Srivastava, A. (2017, January 1\u20135). Exploring timing side-channel attacks on path-ORAMs. Proceedings of the 2017 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), McLean, VA, USA.","DOI":"10.1109\/HST.2017.7951800"},{"key":"ref_22","unstructured":"Gao, W., Iyengar, A.K., and Srivatsa, M. (2013). Caching Provenance Information. (8,577,993), US Patent."},{"key":"ref_23","unstructured":"Pirk, H., Grund, M., Krueger, J., Leser, U., and Zeier, A. (2010). Cache Conscious Data Layouting for in-Memory Databases, Hasso-Plattner-Institute."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Chang, Z.H. (2016, January 25\u201328). Real-time distributed video transcoding on a heterogeneous computing platform. Proceedings of the 2016 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS), Jeju, Korea.","DOI":"10.1109\/APCCAS.2016.7803998"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Ubarhande, V. (2014). Performance Based Data-Distribution Methodology In Heterogeneous Hadoop Environment. [Ph.D. Thesis, National College of Ireland].","DOI":"10.1109\/CISIS.2015.37"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1113","DOI":"10.14778\/2994509.2994528","article-title":"Oblivious RAM: A Dissection and Experimental Evaluation","volume":"9","author":"Chang","year":"2016","journal-title":"Proc. VLDB Endow."},{"key":"ref_27","unstructured":"Teeuwen, P. (2015). Evolution of Oblivious RAM Schemes. [Master\u2019s Thesis, Technische Universiteit Eindhoven]."},{"key":"ref_28","unstructured":"Fletcher, C.W. (2016). Oblivious RAM: From Theory to Practice. [Ph.D. Thesis, Massachusetts Institute of Technology]."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1145\/2508148.2485971","article-title":"Design Space Exploration and Optimization of Path Oblivious RAM in Secure Processors","volume":"41","author":"Ren","year":"2013","journal-title":"SIGARCH Comput. Archit. News"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Fletcher, C.W., Ren, L., Yu, X., Van Dijk, M., Khan, O., and Devadas, S. (2014, January 15\u201319). Suppressing the oblivious ram timing channel while making information leakage and program efficiency trade-offs. Proceedings of the 2014 IEEE 20th International Symposium onHigh Performance Computer Architecture (HPCA), Orlando, FL, USA.","DOI":"10.1109\/HPCA.2014.6835932"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Maas, M., Love, E., Stefanov, E., Tiwari, M., Shi, E., Asanovic, K., Kubiatowicz, J., and Song, D. (2013, January 4\u20138). PHANTOM: Practical Oblivious Computation in a Secure Processor. Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, Berlin, Germany.","DOI":"10.1145\/2508859.2516692"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Yu, X., Haider, S.K., Ren, L., Fletcher, C., Kwon, A., van Dijk, M., and Devadas, S. (2015, January 13\u201317). PrORAM: Dynamic Prefetcher for Oblivious RAM. Proceedings of the 42nd Annual International Symposium on Computer Architecture, Portland, OR, USA.","DOI":"10.1145\/2749469.2750413"},{"key":"ref_33","unstructured":"Ren, L., Fletcher, C., Yu, X., Kwon, A., van Dijk, M., and Devadas, S. (2018, May 12). Unified Oblivious-RAM: Improving Recursive ORAM with Locality and Pseudorandomness. Available online: https:\/\/eprint.iacr.org\/2014\/205."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Fletcher, C.W., Ren, L., Kwon, A., van Dijk, M., and Devadas, S. (2015, January 14\u201318). Freecursive ORAM: [Nearly] Free Recursion and Integrity Verification for Position-based Oblivious RAM. Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems, Istanbul, Turkey.","DOI":"10.1145\/2694344.2694353"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Zhang, X., Sun, G., Zhang, C., Zhang, W., Liang, Y., Wang, T., Chen, Y., and Di, J. (2015, January 5\u20139). Fork Path: Improving Efficiency of ORAM by Removing Redundant Memory Accesses. Proceedings of the 48th International Symposium on Microarchitecture, Waikiki, HI, USA.","DOI":"10.1145\/2830772.2830787"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1109\/TIFS.2017.2762824","article-title":"Enhancing Tree-Based ORAM Using Batched Request Reordering","volume":"13","year":"2018","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_37","unstructured":"Chakraborti, A., and Sion, R. (arXiv Preprint, 2017). SeqORAM: A Locality-Preserving Write-Only Oblivious RAM, arXiv Preprint."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s10207-016-0329-x","article-title":"Write-only oblivious RAM-based privacy-preserved access of outsourced data","volume":"16","author":"Li","year":"2017","journal-title":"Int. J. Inf. Secur."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1109\/MNET.2006.1580916","article-title":"Web cache replacement policies: A pragmatic approach","volume":"20","author":"Wong","year":"2006","journal-title":"IEEE Netw."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1504\/IJWET.2015.072349","article-title":"Impact of traffic distribution on web cache performance","volume":"10","author":"Zotano","year":"2015","journal-title":"Int. J. Web Eng. Technol."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1352","DOI":"10.1109\/TC.2001.970573","article-title":"LRFU: A Spectrum of Policies That Subsumes the Least Recently Used and Least Frequently Used Policies","volume":"50","author":"Lee","year":"2001","journal-title":"IEEE Trans. Comput."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1016\/j.ins.2016.06.038","article-title":"Anomalous query access detection in RBAC-administered databases with random forest and PCA","volume":"369","author":"Ronao","year":"2016","journal-title":"Inf. Sci."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Takatsuka, Y., Nagao, H., Yaguchi, T., Hanai, M., and Shudo, K. (2016, January 18\u201320). A caching mechanism based on data freshness. Proceedings of the 2016 International Conference on Big Data and Smart Computing (BigComp), Hong Kong, China.","DOI":"10.1109\/BIGCOMP.2016.7425940"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.1007\/s00778-007-0051-4","article-title":"Detecting Anomalous Access Patterns in Relational Databases","volume":"17","author":"Kamra","year":"2008","journal-title":"VLDB J."},{"key":"ref_45","unstructured":"Fischbach, K., and Krieger, U.R. (2014). Evaluation of Caching Strategies Based on Access Statistics of Past Requests. Measurement, Modelling, and Evaluation of Computing Systems and Dependability and Fault Tolerance, Springer International Publishing."},{"key":"ref_46","unstructured":"Zipf, G.K. (2014). Selected Studies of the Principle of Relative Frequency in Language, Harvard University Press."},{"key":"ref_47","unstructured":"Zipf, G.K. (1950). Human Behavior and the Principle of Least Effort, Addision-Wesley."},{"key":"ref_48","unstructured":"Fischbach, K., and Krieger, U.R. (2014). PH and MAP Fitting with Aggregated Traffic Traces. Measurement, Modelling, and Evaluation of Computing Systems and Dependability and Fault Tolerance, Springer International Publishing."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Breslau, L., Cao, P., Fan, L., Phillips, G., and Shenker, S. (1999, January 21\u201325). Web caching and Zipf-like distributions: Evidence and implications. Proceedings of the IEEE INFOCOM \u201999. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No.99CH36320), New York, NY, USA.","DOI":"10.1109\/INFCOM.1999.749260"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Pan, Y., Chen, D., Guo, M., Cao, J., and Dongarra, J. (2005). Quantitative Analysis of Zipf\u2019s Law on Web Cache. Parallel and Distributed Processing and Applications, Springer.","DOI":"10.1007\/11576235"},{"key":"ref_51","unstructured":"Nair, T.R.G., and Jayarekha, P. (arXiv Preprint, 2010). A Rank Based Replacement Policy for Multimedia Server Cache Using Zipf-Like Law, arXiv Preprint."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Zotano, M. (2015, January 3\u20135). Analysis of web objects distribution. Proceedings of the 12th International Conference on Distributed Computing and Artificial Intelligence, Salamanca, Spain.","DOI":"10.1007\/978-3-319-19638-1_12"},{"key":"ref_53","unstructured":"Tom\u00e9, C.G., and Garc\u0131a, C.J. (2017). Adaptive Fragment Designs to Reduce the Latency of Web Caching in Content Aggregation Systems. [Ph.D. Thesis, Universitat de les Illes Balears]."},{"key":"ref_54","unstructured":"Gradshteyn, I., and Ryzhik, I. (1980). Table of Integrals, Series, and Products, Academic Press."},{"key":"ref_55","unstructured":"Naldi, M. (arXiv preprint, 2015). Approximation of the truncated Zeta distribution and Zipf\u2019s law, arXiv preprint."}],"container-title":["Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-431X\/7\/4\/56\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:26:45Z","timestamp":1760196405000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-431X\/7\/4\/56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,29]]},"references-count":55,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,12]]}},"alternative-id":["computers7040056"],"URL":"https:\/\/doi.org\/10.3390\/computers7040056","relation":{},"ISSN":["2073-431X"],"issn-type":[{"type":"electronic","value":"2073-431X"}],"subject":[],"published":{"date-parts":[[2018,10,29]]}}}