{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:15:13Z","timestamp":1760242513598,"version":"build-2065373602"},"reference-count":34,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T00:00:00Z","timestamp":1506470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Future Internet"],"abstract":"<jats:p>This paper proposes TSKT-oblivious RAM (ORAM), an efficient multi-server ORAM construction, to protect a client\u2019s access pattern to outsourced data. TSKT-ORAM organizes each of the server storages as a k-ary tree and adopts XOR-based private information retrieval (PIR) and a novel delayed eviction technique to optimize both the data query and data eviction process. TSKT-ORAM is proven to protect the data access pattern privacy with a failure probability of     2  - 80      when system parameter     k \u2265 128    . Meanwhile, given a constant-size local storage, when N (i.e., the total number of outsourced data blocks) ranges from     2 16    \u2013    2 34    , the communication cost of TSKT-ORAM is only 22\u201346 data blocks. Asymptotic analysis and practical comparisons are conducted to show that TSKT-ORAM incurs lower communication cost, storage cost and access delay in practical scenarios than the compared state-of-the-art ORAM schemes.<\/jats:p>","DOI":"10.3390\/fi9040057","type":"journal-article","created":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T10:52:25Z","timestamp":1506509545000},"page":"57","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["TSKT-ORAM: A Two-Server k-ary Tree Oblivious RAM without Homomorphic Encryption"],"prefix":"10.3390","volume":"9","author":[{"given":"Jinsheng","family":"Zhang","sequence":"first","affiliation":[{"name":"Department of Computer Science, Iowa State University, Ames, IA 50011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiumao","family":"Ma","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Iowa State University, Ames, IA 50011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wensheng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Iowa State University, Ames, IA 50011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daji","family":"Qiao","sequence":"additional","affiliation":[{"name":"Department of Electric and Computer Engineering, Iowa State University, Ames, IA 50011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,9,27]]},"reference":[{"key":"ref_1","unstructured":"Islam, M.S., Kuzu, M., and Kantarcioglu, M.K. (2012, January 5\u20138). Access pattern disclosure on searchable encryption: Ramification, attack and mitigation. Proceedings of the NDSS Symposium, San Diego, CA, USA."},{"key":"ref_2","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., and Sudan, M. (1995, January 23\u201325). Private information retrieval. Proceedings of the 36th FOCS 1995, Milwaukee, WI, USA."},{"key":"ref_3","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., and Raymond, J.F. (2002, January 16\u201319). Breaking the \n                    \n                      \n\t\t\t\t\t  \n\t\t\t\t\t  O\n\t\t\t\t\t  (\n                        \n                          n\n                          \n\t\t\t\t\t\t  \n\t\t\t\t\t\t\t1\n\t\t\t\t\t\t  \n                            2\n                            k\n\t\t\t\t\t\t\t\u2212\n\t\t\t\t\t\t\t1\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\n                          \n                        \n\t\t\t\t\t\t)\n\t\t\t\t\t\t\n                      \n                    \n                   barrier for information-theoretic private information retrieval. Proceedings of the 43rd FOCS 2002, Vancouver, BC, Canada."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Chor, B., and Gilboa, N. (1997, January 4\u20136). Computationally private information retrieval. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, TX, USA.","DOI":"10.1145\/258533.258609"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Gertner, Y., Ishai, Y., Kushilevitz, E., and Malkin, T. (1998, January 24\u201326). Protecting data privacy in private information retrieval schemes. Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Dallas, TX, USA.","DOI":"10.1145\/276698.276723"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Goldberg, I. (2007, January 20\u201323). Improving the robustness of private information retrieval. Proceedings of the IEEE Symposium on Security and Privacy, Berkeley, CA, USA.","DOI":"10.1109\/SP.2007.23"},{"key":"ref_7","unstructured":"Kushilevitz, E., and Ostrovsky, R. (1997, January 19\u201322). Replication is not needed: Single database, computationally-private information retrieval (extended abstract). Proceedings of the FOCS 1997, Miami, FL, USA."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Cachin, C., Micali, S., and Stadler, M. (1999, January 2\u20136). Computationally private information retrieval with polylogarithmic communication. Proceedings of the Eurocrypt 1999, Prague, Czech Republic.","DOI":"10.1007\/3-540-48910-X_28"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Lipmaa, H. (2005, January 9\u201311). An oblivious transfer protocol with log-squared communication. Proceedings of the ISC 2005, Berlin, Germany.","DOI":"10.1007\/11556992_23"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/978-3-642-18178-8_10","article-title":"Efficient computationally private information retrieval from anonymity or trapdoor groups","volume":"Volume 6531","author":"Trostle","year":"2011","journal-title":"Information Security"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/BFb0054868","article-title":"NTRU: A ring-based public key cryptosystem","volume":"Volume 1423","author":"Hoffstein","year":"1998","journal-title":"Algorithmic Number Theory"},{"key":"ref_12","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_13","unstructured":"Goodrich, M.T., and Mitzenmacher, M. (arXiv, 2010). Mapreduce parallel cuckoo hashing and oblivious RAM simulations, arXiv."},{"key":"ref_14","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 SODA 2012, Kyoto, Japan.","DOI":"10.1137\/1.9781611973099.14"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., and Mitzenmacher, M. (2011, January 4\u20138). Privacy-preserving access of outsourced data via oblivious RAM simulation. Proceedings of the ICALP 2011, Zurich, Switzerland.","DOI":"10.1007\/978-3-642-22012-8_46"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., and Tamassia, R. (2011, January 21). Oblivious RAM simulation with efficient worst-case access overhead. Proceedings of the CCSW 2011, Chicago, IL, USA.","DOI":"10.1145\/2046660.2046680"},{"key":"ref_17","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_18","doi-asserted-by":"crossref","unstructured":"Pinkas, B., and Reinman, T. (2010, January 15\u201319). Oblivious RAM revisited. Proceedings of the CRYPTO 2010, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-642-14623-7_27"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Williams, P., and Sion, R. (2008, January 27\u201331). Building castles out of mud: Practical access pattern privacy and correctness on untrusted storage. Proceedings of the CCS 2008, Alexandria, VA, USA.","DOI":"10.1145\/1455770.1455790"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Williams, P., Sion, R., and Tomescu, A. (2012, January 16\u201318). PrivateFS: A parallel oblivious file system. Proceedings of the CCS 2012, Releigh, NC, USA.","DOI":"10.1145\/2382196.2382299"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Williams, P., Sion, R., and Tomescu, A. (2012, January 16\u201318). Single round access privacy on outsourced storage. Proceedings of the CCS 2012, Releigh, NC, USA.","DOI":"10.1145\/2382196.2382229"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Shi, E., Chan, T.H.H., Stefanov, E., and Li, M. (2011, January 4\u20138). Oblivious RAM with O((logN)3) worst-case cost. Proceedings of the ASIACRYPT 2011, Seoul, Korea.","DOI":"10.1007\/978-3-642-25385-0_11"},{"key":"ref_23","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 CCS 2013, Berlin, Germany.","DOI":"10.1145\/2508859.2516660"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Stefanov, E., and Shi, E. (2013, January 19\u201323). ObliviStore: High performance oblivious cloud storage. Proceedings of the IEEE Symposium on Security and Privacy, San Francisco, CA, USA.","DOI":"10.1109\/SP.2013.25"},{"key":"ref_25","unstructured":"Stefanov, E., Shi, E., and Song, D. (2011, January 6\u20139). Towards practical oblivious RAM. Proceedings of the NDSS 2011, San Diego, CA, USA."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Gentry, C., Goldman, K., Halevi, S., Julta, C., Raykova, M., and Wichs, D. (2013, January 10\u201323). Optimizing ORAM and using it efficiently for secure computation. Proceedings of the PETS 2013, Bloomington, IN, USA.","DOI":"10.1007\/978-3-642-39077-7_1"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Stefanov, E., and Shi, E. (2013, January 4\u20138). Multi-Cloud Oblivious Storage. Proceedings of the CCS 2013, Berlin, Germany.","DOI":"10.1145\/2508859.2516673"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Wang, X., Huang, Y., Chan, T.H.H., Shelat, A., and Shi, E. (2014, January 3\u20137). SCORAM: Oblivious RAM for secure computations. Proceedings of the CCS 2014, Scotsdale, AZ, USA.","DOI":"10.1145\/2660267.2660365"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Moataz, T., Mayberry, T., and Blass, E.O. (2015, January 12\u201316). Constant communication ORAM with small blocksize. Proceedings of the CCS 2015, Denver, CO, USA.","DOI":"10.1145\/2810103.2813701"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Moataz, T., Blass, E.O., and Mayberry, T. (2015). Constant Communication ORAM without Encryption. IACR Cryptology ePrint Archive, International Association for Cryptologic Research.","DOI":"10.1145\/2810103.2813701"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Lipmaa, H., and Zhang, B. (2010, January 22\u201325). Two new efficient PIR-writing protocols. Proceedings of the ACNS 2010, Beijing, China.","DOI":"10.1007\/978-3-642-13708-2_26"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Mayberry, T., Blass, E.O., and Chan, A.H. (2014, January 23\u201326). Efficient private file retrieval by combining ORAM and PIR. Proceedings of the NDSS 2014, San Diego, CA, USA.","DOI":"10.14722\/ndss.2014.23033"},{"key":"ref_33","unstructured":"Lu, S., and Ostrovsky, R. (2011). Distributed Oblivious RAM for Secure Two-Party Computation. IACR Cryptology ePrint Archive 2011\/384, International Association for Cryptologic Research."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Freier, A., Karlton, P., and Kocher, P. (2011). The Secure Sockets Layer (SSL) Protocol Version 3.0, Internet Engineering Task Force (IETF). RFC 6101.","DOI":"10.17487\/rfc6101"}],"container-title":["Future Internet"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-5903\/9\/4\/57\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:46:06Z","timestamp":1760208366000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-5903\/9\/4\/57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,27]]},"references-count":34,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2017,12]]}},"alternative-id":["fi9040057"],"URL":"https:\/\/doi.org\/10.3390\/fi9040057","relation":{},"ISSN":["1999-5903"],"issn-type":[{"type":"electronic","value":"1999-5903"}],"subject":[],"published":{"date-parts":[[2017,9,27]]}}}