{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T17:30:50Z","timestamp":1783791050432,"version":"3.55.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,10]]},"abstract":"<jats:p>\n            Privacy has been the key road block to cloud computing as clouds may not be fully trusted. This paper concerns the problem of privacy preserving range query processing on clouds. Prior schemes are weak in privacy protection as they cannot achieve index indistinguishability, and therefore allow the cloud to statistically estimate the values of data and queries using domain knowledge and history query results. In this paper, we propose the first range query processing scheme that achieves index indistinguishability under the\n            <jats:italic>indistinguishability against chosen keyword attack<\/jats:italic>\n            (IND-CKA). Our key idea is to organize indexing elements in a complete binary tree called PBtree, which satisfies\n            <jats:italic>structure indistinguishability<\/jats:italic>\n            (\n            <jats:italic>i.e.<\/jats:italic>\n            , two sets of data items have the same PBtree structure if and only if the two sets have the same number of data items) and\n            <jats:italic>node indistinguishability<\/jats:italic>\n            (\n            <jats:italic>i.e.<\/jats:italic>\n            , the values of PBtree nodes are completely random and have no statistical meaning). We prove that our scheme is secure under the widely adopted IND-CKA security model. We propose two algorithms, namely PBtree traversal width minimization and PBtree traversal depth minimization, to improve query processing efficiency. We prove that the worse case complexity of our query processing algorithm using PBtree is\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>R<\/jats:italic>\n            | log\n            <jats:italic>n<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            is the total number of data items and\n            <jats:italic>R<\/jats:italic>\n            is the set of data items in the query result. We implemented and evaluated our scheme on a real world data set with 5 million items. For example, for a query whose results contain ten data items, it takes only 0.17 milliseconds.\n          <\/jats:p>","DOI":"10.14778\/2733085.2733100","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"1953-1964","source":"Crossref","is-referenced-by-count":84,"title":["Fast range query processing with strong privacy protection for cloud computing"],"prefix":"10.14778","volume":"7","author":[{"given":"Rui","family":"Li","sequence":"first","affiliation":[{"name":"Hunan university, ChangSha, China and Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex X.","family":"Liu","sequence":"additional","affiliation":[{"name":"Michigan State University, East Lansing, MI and Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ann L.","family":"Wang","sequence":"additional","affiliation":[{"name":"Michigan State University, East Lansing, MI"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bezawada","family":"Bruhadeshwar","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Amazon web services aws.amazon.com.  Amazon web services aws.amazon.com."},{"key":"e_1_2_1_2_1","unstructured":"Google app engine code.google.com\/appengine.  Google app engine code.google.com\/appengine."},{"key":"e_1_2_1_3_1","unstructured":"Microsoft azure www.microsoft.com\/azure.  Microsoft azure www.microsoft.com\/azure."},{"key":"e_1_2_1_4_1","volume-title":"http:\/\/www.cnet.com\/news\/google fired engineer for privacy breach\/","year":"2010"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007632"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335438"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11602897_35"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1777777.1777820"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3088723.3088749"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033036.2033080"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_30"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_17"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.238015"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2011.5935306"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11496137_30"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180417"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2590701.2590705"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/948109.948124"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_22_1","volume-title":"Applied Cryptography and Network Security.","author":"Golle P.","year":"2004"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.912717"},{"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.5555\/1316689.1316752"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382298"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535706_24"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1206501"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-48533-1_5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535706_6"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367856"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400766"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1149976.1149977"},{"issue":"1","key":"e_1_2_1_35_1","first-page":"37","article-title":"Privacy preserving clustering by data transformation","volume":"1","author":"Oliveira S. R. M.","year":"2010","journal-title":"JIDM"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31815-6_7"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/19478.19483"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2007.29"},{"key":"e_1_2_1_39_1","volume-title":"Practical techniques for searches on encrypted data","author":"Song D.","year":"2000"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218488502001648"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559862"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2381913.2381927"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2733085.2733100","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:17:06Z","timestamp":1672226226000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2733085.2733100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10]]},"references-count":41,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["10.14778\/2733085.2733100"],"URL":"https:\/\/doi.org\/10.14778\/2733085.2733100","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,10]]}}}