{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:01:06Z","timestamp":1777449666835,"version":"3.51.4"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,10,7]],"date-time":"2014-10-07T00:00:00Z","timestamp":1412640000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100014790","name":"Singapore Management University","doi-asserted-by":"crossref","award":["13-C220-SMU-004"],"award-info":[{"award-number":["13-C220-SMU-004"]}],"id":[{"id":"10.13039\/501100014790","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,10,7]]},"abstract":"<jats:p>In IT outsourcing, a user may delegate the data storage and query processing functions to a third-party server that is not completely trusted. This gives rise to the need to safeguard the privacy of the database as well as the user queries over it. In this article, we address the problem of running ad hoc equi-join queries directly on encrypted data in such a setting. Our contribution is the first solution that achieves constant complexity per pair of records that are evaluated for the join. After formalizing the privacy requirements pertaining to the database and user queries, we introduce a cryptographic construct for securely joining records across relations. The construct protects the database with a strong encryption scheme. Moreover, information disclosure after executing an equi-join is kept to the minimum\u2014that two input records combine to form an output record if and only if they share common join attribute values. There is no disclosure on records that are not part of the join result.<\/jats:p>\n          <jats:p>Building on this construct, we then present join algorithms that optimize the join execution by eliminating the need to match every record pair from the input relations. We provide a detailed analysis of the cost of the algorithms and confirm the analysis through extensive experiments with both synthetic and benchmark workloads. Through this evaluation, we tease out useful insights on how to configure the join algorithms to deliver acceptable execution time in practice.<\/jats:p>","DOI":"10.1145\/2629501","type":"journal-article","created":{"date-parts":[[2014,10,7]],"date-time":"2014-10-07T12:57:47Z","timestamp":1412686667000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Privacy-Preserving Ad-Hoc Equi-Join on Outsourced Data"],"prefix":"10.1145","volume":"39","author":[{"given":"Hweehwa","family":"Pang","sequence":"first","affiliation":[{"name":"Singapore Management University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuhua","family":"Ding","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,10,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007632"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 17th International Conference on Database Theory (ICDT'14)","author":"Arasu Arvind","year":"2014","unstructured":"Arvind Arasu and Raghav Kaushik . 2014 . Oblivious query processing . In Proceedings of the 17th International Conference on Database Theory (ICDT'14) . 26--37. Arvind Arasu and Raghav Kaushik. 2014. Oblivious query processing. In Proceedings of the 17th International Conference on Database Theory (ICDT'14). 26--37."},{"key":"e_1_2_1_3_1","unstructured":"Elaine Barker William Barker William Burr William Polk and Miles Smid. 2012. Recommendation for key management part 1: General (revision 3). http:\/\/csrc.nist.gov\/publications\/nistpubs\/800-57\/SP800-57_Part1_rev3_general.pdf.  Elaine Barker William Barker William Burr William Polk and Miles Smid. 2012. Recommendation for key management part 1: General (revision 3). http:\/\/csrc.nist.gov\/publications\/nistpubs\/800-57\/SP800-57_Part1_rev3_general.pdf."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28628-8_3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_30"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 27th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO'07)","author":"Boneh Dan","unstructured":"Dan Boneh , Eyal Kushilevitz , Rafail Ostrovsky , and William E . Skeith III. 2007. Public key encryption that allows pir queries . In Proceedings of the 27th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO'07) . 50--67. Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, and William E. Skeith III. 2007. Public key encryption that allows pir queries. In Proceedings of the 27th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO'07). 50--67."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_34"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1760749.1760788"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38553-7_2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.142"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180417"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/948109.948124"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"e_1_2_1_15_1","unstructured":"Volker Gaede and Oliver Gunther. 1994. Processing joins with user-defined functions. In Grundlagen von Datenbanken. 46--50.  Volker Gaede and Oliver Gunther. 1994. Processing joins with user-defined functions. In Grundlagen von Datenbanken. 46--50."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24852-1_3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564717"},{"key":"e_1_2_1_18_1","volume-title":"Transactions on","author":"Harrison Owen","unstructured":"Owen Harrison and John Waldron . 2010. GPU accelerated cryptography as an os service . In Transactions on Computational Science XI. Springer , 4--130. Owen Harrison and John Waldron. 2010. GPU accelerated cryptography as an os service. In Transactions on Computational Science XI. Springer, 4--130."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170078"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316752"},{"key":"e_1_2_1_21_1","unstructured":"Yosuke Katoh Yun-Ju Huang Chen-Mou Cheng and Tsuyoshi Takagi. 2011. Efficient implementation of the ETA pairing on GPU. IACR Cryptol. ePrint Arch. 540.  Yosuke Katoh Yun-Ju Huang Chen-Mou Cheng and Tsuyoshi Takagi. 2011. Efficient implementation of the ETA pairing on GPU. IACR Cryptol. ePrint Arch. 540."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788414.1788423"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/3127142.3127149"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043566"},{"key":"e_1_2_1_25_1","unstructured":"Cliff Saran. 2011. Office365 fails bae's legal team. http:\/\/www.computerweekly.com\/news\/2240112018\/Office365-fails-BAes-legal-team.  Cliff Saran. 2011. Office365 fails bae's legal team. http:\/\/www.computerweekly.com\/news\/2240112018\/Office365-fails-BAes-legal-team."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66937"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_27"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the IEEE Symposium on Security and Privacy (SP'00)","author":"Song Dawn Xiaodong","year":"2000","unstructured":"Dawn Xiaodong Song , David Wagner , and Adrian Perrig . 2000 . Practical techniques for searches on encrypted data . In Proceedings of the IEEE Symposium on Security and Privacy (SP'00) . 44--55. Dawn Xiaodong Song, David Wagner, and Adrian Perrig. 2000. Practical techniques for searches on encrypted data. In Proceedings of the IEEE Symposium on Security and Privacy (SP'00). 44--55."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629501","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629501","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:18Z","timestamp":1750230078000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629501"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,7]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,10,7]]}},"alternative-id":["10.1145\/2629501"],"URL":"https:\/\/doi.org\/10.1145\/2629501","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,7]]},"assertion":[{"value":"2013-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}