{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T20:32:30Z","timestamp":1764102750083,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,10,16]],"date-time":"2015-10-16T00:00:00Z","timestamp":1444953600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Italian MIUR within project \u201cGenData 2020.\u201d"},{"name":"EC","award":["312797 (ABC4EU) and 644579 (ESCUDO-CLOUD)"],"award-info":[{"award-number":["312797 (ABC4EU) and 644579 (ESCUDO-CLOUD)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2015,11,21]]},"abstract":"<jats:p>Data outsourcing and cloud computing have been emerging at an ever-growing rate as successful approaches for allowing users and companies to rely on external services for storing and managing data. As data and access to them are not under the control of the data owner, there is a clear need to provide proper confidentiality protection. Such requirements concern the confidentiality not only of the stored data (content) but also of the specific accesses (or patterns of them) that users make on such data.<\/jats:p>\n          <jats:p>\n            In this article, we address these issues and propose an approach for guaranteeing content, access, and pattern confidentiality in a data outsourcing scenario. The proposed solution is based on the definition of a\n            <jats:italic>shuffle index<\/jats:italic>\n            structure, which adapts traditional\n            <jats:italic>B<\/jats:italic>\n            +-trees and, by applying a combination of techniques (covers, caches, and shuffling), ensures confidentiality of the data and of queries over them, protecting each single access as well as sequences thereof. The proposed solution also supports update operations over the data, while making reads and writes not recognizable as such by the server. We show that the shuffle index exhibits a limited performance cost, thus resulting effectively usable in practice.\n          <\/jats:p>","DOI":"10.1145\/2747878","type":"journal-article","created":{"date-parts":[[2015,10,20]],"date-time":"2015-10-20T09:28:08Z","timestamp":1445333288000},"page":"1-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Shuffle Index"],"prefix":"10.1145","volume":"11","author":[{"given":"Sabrina De Capitani Di","family":"Vimercati","sequence":"first","affiliation":[{"name":"Universit\u00e0 degli Studi di Milano, Crema CR, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sara","family":"Foresti","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Milano, Crema CR, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Paraboschi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Bergamo, Dalmine BG, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3812-5429","authenticated-orcid":false,"given":"Gerardo","family":"Pelosi","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Milano (MI), Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierangela","family":"Samarati","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Milano, Crema CR, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,10,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544921"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007632"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2037556.2037611"},{"volume-title":"Proc. of the 38th Annual Symposium on Foundations of Computer Science (FOCS\u201997)","author":"Bellare M.","key":"e_1_2_1_4_1","unstructured":"M. Bellare , A. Desai , E. Jokipii , and P. Rogaway . 1997. A concrete security treatment of symmetric encryption . In Proc. of the 38th Annual Symposium on Foundations of Computer Science (FOCS\u201997) . M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. 1997. A concrete security treatment of symmetric encryption. In Proc. of the 38th Annual Symposium on Foundations of Computer Science (FOCS\u201997)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-008-9026-x"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1966445.1966449"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653662.1653686"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1053283.1053289"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11496137_30"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180417"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/948109.948124"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1456403.1456417"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.37"},{"volume-title":"Proc. of the 16th European Symposium On Research In Computer Security (ESORICS\u201911)","author":"di Vimercati S. De Capitani","key":"e_1_2_1_14_1","unstructured":"S. De Capitani di Vimercati , S. Foresti , S. Paraboschi , G. Pelosi , and P. Samarati . 2011b. Supporting concurrency in private data outsourcing . In Proc. of the 16th European Symposium On Research In Computer Security (ESORICS\u201911) . S. De Capitani di Vimercati, S. Foresti, S. Paraboschi, G. Pelosi, and P. Samarati. 2011b. Supporting concurrency in private data outsourcing. In Proc. of the 16th European Symposium On Research In Computer Security (ESORICS\u201911)."},{"volume-title":"Proc. of the 18th European Symposium On Research In Computer Security (ESORICS\u201913)","author":"di Vimercati S. De Capitani","key":"e_1_2_1_15_1","unstructured":"S. De Capitani di Vimercati , S. Foresti , S. Paraboschi , G. Pelosi , and P. Samarati . 2013a. Distributed shuffling for preserving access confidentiality . In Proc. of the 18th European Symposium On Research In Computer Security (ESORICS\u201913) . S. De Capitani di Vimercati, S. Foresti, S. Paraboschi, G. Pelosi, and P. Samarati. 2013a. Distributed shuffling for preserving access confidentiality. In Proc. of the 18th European Symposium On Research In Computer Security (ESORICS\u201913)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2590618.2590623"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CRISIS.2012.6378956"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2010.2101062"},{"volume-title":"Preserving Privacy in Data Outsourcing","author":"Foresti S.","key":"e_1_2_1_19_1","unstructured":"S. Foresti . 2011. Preserving Privacy in Data Outsourcing . Springer . S. Foresti. 2011. Preserving Privacy in Data Outsourcing. Springer."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191886"},{"volume-title":"Proc. of the 18th International Conference on Data Engineering (ICDE\u201902)","author":"Hacig\u00fcm\u00fcs H.","key":"e_1_2_1_22_1","unstructured":"H. Hacig\u00fcm\u00fcs , B. Iyer , and S. Mehrotra . 2002a. Providing database as a service . In Proc. of the 18th International Conference on Data Engineering (ICDE\u201902) . H. Hacig\u00fcm\u00fcs, B. Iyer, and S. Mehrotra. 2002a. Providing database as a service. In Proc. of the 18th International Conference on Data Engineering (ICDE\u201902)."},{"volume-title":"Proc. of the 9th International Conference on Database Systems for Advances Applications (DASFAA\u201904)","author":"Hacig\u00fcm\u00fcs H.","key":"e_1_2_1_23_1","unstructured":"H. Hacig\u00fcm\u00fcs , B. Iyer , and S. Mehrotra . 2004. Efficient execution of aggregation queries over encrypted relational databases . In Proc. of the 9th International Conference on Database Systems for Advances Applications (DASFAA\u201904) . H. Hacig\u00fcm\u00fcs, B. Iyer, and S. Mehrotra. 2004. Efficient execution of aggregation queries over encrypted relational databases. In Proc. of the 9th International Conference on Database Systems for Advances Applications (DASFAA\u201904)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564717"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0245-7"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2557547.2557561"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCSE.2012.32"},{"volume-title":"Proc. of the 6th Conference on Critical Information Infrastructures Security (CRITIS\u201911)","author":"Kandias M.","key":"e_1_2_1_28_1","unstructured":"M. Kandias , N. Virvilis , and D. Gritzalis . 2011. The insider threat in cloud computing . In Proc. of the 6th Conference on Critical Information Infrastructures Security (CRITIS\u201911) . M. Kandias, N. Virvilis, and D. Gritzalis. 2011. The insider threat in cloud computing. In Proc. of the 6th Conference on Critical Information Infrastructures Security (CRITIS\u201911)."},{"volume-title":"Proc. of the 2nd International Workshop on Security in Information Systems (WOSIS\u201904)","author":"Lin P.","key":"e_1_2_1_29_1","unstructured":"P. Lin and K. S. Candan . 2004a. Hiding traversal of tree structured data from untrusted data stores . In Proc. of the 2nd International Workshop on Security in Information Systems (WOSIS\u201904) . P. Lin and K. S. Candan. 2004a. Hiding traversal of tree structured data from untrusted data stores. In Proc. of the 2nd International Workshop on Security in Information Systems (WOSIS\u201904)."},{"volume-title":"Proc. of the 1st International Conference on Secure Data Management (SDM\u201904)","author":"Lin P.","key":"e_1_2_1_30_1","unstructured":"P. Lin and K. S. Candan . 2004b. Secure and privacy preserving outsourcing of tree structured data . In Proc. of the 1st International Conference on Secure Data Management (SDM\u201904) . P. Lin and K. S. Candan. 2004b. Secure and privacy preserving outsourcing of tree structured data. In Proc. of the 1st International Conference on Secure Data Management (SDM\u201904)."},{"volume-title":"Proc. of the 10th International Conference on Practice and Theory in Public-Key Cryptography (PKC\u201907)","author":"Ostrovsky R.","key":"e_1_2_1_31_1","unstructured":"R. Ostrovsky and W. E. Skeith , III. 2007. A survey of single-database private information retrieval: Techniques and applications . In Proc. of the 10th International Conference on Practice and Theory in Public-Key Cryptography (PKC\u201907) . R. Ostrovsky and W. E. Skeith, III. 2007. A survey of single-database private information retrieval: Techniques and applications. In Proc. of the 10th International Conference on Practice and Theory in Public-Key Cryptography (PKC\u201907)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.77"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2012.14"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535706_5"},{"key":"e_1_2_1_35_1","volume-title":"Density Estimation for Statistics and Data Analysis","author":"Silverman B. W.","unstructured":"B. W. Silverman . 1986. Density Estimation for Statistics and Data Analysis ( 1 st ed.). Chapman & Hall Monographs on Statistics & Applied Probability. B. W. Silverman. 1986. Density Estimation for Statistics and Data Analysis (1st ed.). Chapman & Hall Monographs on Statistics & Applied Probability.","edition":"1"},{"volume-title":"Proc. of the 14th Annual Network & Distributed System Security Conference (NDSS&rsquo;\u201907)","author":"Sion R.","key":"e_1_2_1_36_1","unstructured":"R. Sion and B. Carbunar . 2007. On the computational practicality of private information retrieval . In Proc. of the 14th Annual Network & Distributed System Security Conference (NDSS&rsquo;\u201907) . R. Sion and B. Carbunar. 2007. On the computational practicality of private information retrieval. In Proc. of the 14th Annual Network & Distributed System Security Conference (NDSS&rsquo;\u201907)."},{"volume-title":"Proc. of the 21st IEEE Symposium on Security and Privacy (S&P&rsquo;\u201900)","author":"Song D. X.","key":"e_1_2_1_37_1","unstructured":"D. X. Song , D. Wagner , and A. Perrig . 2000. Practical techniques for searches on encrypted data . In Proc. of the 21st IEEE Symposium on Security and Privacy (S&P&rsquo;\u201900) . D. X. Song, D. Wagner, and A. Perrig. 2000. Practical techniques for searches on encrypted data. In Proc. of the 21st IEEE Symposium on Security and Privacy (S&P&rsquo;\u201900)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.25"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516660"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484313.2484322"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2010.34"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2011.282"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164140"},{"volume-title":"Proc. of the 8th International Conference on Secure Data Management (SDM\u201911)","author":"Wang S.","key":"e_1_2_1_44_1","unstructured":"S. Wang , D. Agrawal , and A. El Abbadi . 2011. A comprehensive framework for secure query processing on relational data in the cloud . In Proc. of the 8th International Conference on Secure Data Management (SDM\u201911) . S. Wang, D. Agrawal, and A. El Abbadi. 2011. A comprehensive framework for secure query processing on relational data in the cloud. In Proc. of the 8th International Conference on Secure Data Management (SDM\u201911)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/CIT.2005.174"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455770.1455790"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382299"},{"volume-title":"Proc. of the 16th European Symposium on Research in Computer Security (ESORICS\u201911)","author":"Yang K.","key":"e_1_2_1_48_1","unstructured":"K. Yang , J. Zhang , W. Zhang , and D. Qiao . 2011. A light-weight solution to preservation of access pattern privacy in un-trusted clouds . In Proc. of the 16th European Symposium on Research in Computer Security (ESORICS\u201911) . K. Yang, J. Zhang, W. Zhang, and D. Qiao. 2011. A light-weight solution to preservation of access pattern privacy in un-trusted clouds. In Proc. of the 16th European Symposium on Research in Computer Security (ESORICS\u201911)."}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2747878","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2747878","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:17:01Z","timestamp":1750227421000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2747878"}},"subtitle":["Efficient and Private Access to Outsourced Data"],"short-title":[],"issued":{"date-parts":[[2015,10,16]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,11,21]]}},"alternative-id":["10.1145\/2747878"],"URL":"https:\/\/doi.org\/10.1145\/2747878","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2015,10,16]]},"assertion":[{"value":"2013-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}