{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T19:16:49Z","timestamp":1774725409527,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T00:00:00Z","timestamp":1556236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Priv. Secur."],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"<jats:p>Private record linkage protocols allow multiple parties to exchange matching records, which refer to the same entities or have similar values, while keeping the non-matching ones secret. Conventional protocols are based on computationally expensive cryptographic primitives and therefore do not scale. To address these scalability issues, hybrid protocols have been proposed that combine differential privacy techniques with secure multiparty computation techniques. However, a drawback of such protocols is that they disclose to the parties both the matching records and the differentially private synopses of the datasets involved in the linkage. Consequently, differential privacy is no longer always satisfied. To address this issue, we propose a novel framework that separates the private synopses from the matching records. The two parties do not access the synopses directly, but still use them to efficiently link records. We theoretically prove the security of our framework under the state-of-the-art privacy notion of differential privacy for record linkage (DPRL). In addition, we develop a simple but effective strategy for releasing private synopses. Extensive experimental results show that our framework is superior to the existing methods in terms of efficiency.<\/jats:p>","DOI":"10.1145\/3318462","type":"journal-article","created":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T17:12:14Z","timestamp":1556557934000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Hybrid Private Record Linkage"],"prefix":"10.1145","volume":"22","author":[{"given":"Fang-Yu","family":"Rao","sequence":"first","affiliation":[{"name":"Department of Computer Science, Purdue University, West Lafayette, IN, USA"}]},{"given":"Jianneng","family":"Cao","sequence":"additional","affiliation":[{"name":"DBS Bank, Singapore, Singapore"}]},{"given":"Elisa","family":"Bertino","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Purdue University, West Lafayette, IN, USA"}]},{"given":"Murat","family":"Kantarcioglu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,4,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872771"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077501.1077513"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398480"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113352"},{"key":"e_1_2_1_6_1","unstructured":"Census. 1996. Retrieved from http:\/\/archive.ics.uci.edu\/ml\/datasets\/Census+Income.  Census. 1996. Retrieved from http:\/\/archive.ics.uci.edu\/ml\/datasets\/Census+Income."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.16"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the PKC","author":"Damg\u00e5rd Ivan","year":"2001","unstructured":"Ivan Damg\u00e5rd and Mads Jurik . 2001 . A generalisation, a simplification, and some applications of Paillier\u2019s probabilistic public-key system . In Proceedings of the PKC 2001. 119--136. Ivan Damg\u00e5rd and Mads Jurik. 2001. A generalisation, a simplification, and some applications of Paillier\u2019s probabilistic public-key system. In Proceedings of the PKC 2001. 119--136."},{"key":"e_1_2_1_9_1","unstructured":"Frederick Douglas. 2012. Advanced crypto software collection. Retrieved from http:\/\/hms.isi.jhu.edu\/acsc\/damgard-jurik\/.  Frederick Douglas. 2012. Advanced crypto software collection. Retrieved from http:\/\/hms.isi.jhu.edu\/acsc\/damgard-jurik\/."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1969.10501049"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"e_1_2_1_13_1","volume-title":"Basic Techniques","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2001. The Foundations of Cryptography\u2014Volume 1 , Basic Techniques . Cambridge University Press . Oded Goldreich. 2001. The Foundations of Cryptography\u2014Volume 1, Basic Techniques. Cambridge University Press."},{"key":"e_1_2_1_14_1","volume-title":"Basic Applications","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2004. The Foundations of Cryptography\u2014Volume 2 , Basic Applications . Cambridge University Press . Oded Goldreich. 2004. The Foundations of Cryptography\u2014Volume 2, Basic Applications. Cambridge University Press."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the PSD","author":"Hall Rob","year":"2010","unstructured":"Rob Hall and Stephen E. Fienberg . 2010. Privacy-preserving record linkage . In Proceedings of the PSD 2010 . 269--283. Rob Hall and Stephen E. Fienberg. 2010. Privacy-preserving record linkage. In Proceedings of the PSD 2010. 269--283."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134030"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2014.2369034"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the USENIX Security","author":"Huang Yan","year":"2011","unstructured":"Yan Huang , David Evans , Jonathan Katz , and Lior Malka . 2011 . Faster secure two-party computation using garbled circuits . In Proceedings of the USENIX Security 2011. Yan Huang, David Evans, Jonathan Katz, and Lior Malka. 2011. Faster secure two-party computation using garbled circuits. In Proceedings of the USENIX Security 2011."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739059"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/BCI.2009.29"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535218_15"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10433-6_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_40"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452398"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243851"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2013.22"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756123.1756146"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544872"},{"key":"e_1_2_1_30_1","unstructured":"Fang-Yu Rao Jianneng Cao Elisa Bertino and Murat Kantarcioglu. 2018. A hybrid private record linkage scheme: Separating differentially private synopses from matching records. Retrieved from https:\/\/www.cs.purdue.edu\/homes\/raof\/DPLinkage_full_version.pdf.  Fang-Yu Rao Jianneng Cao Elisa Bertino and Murat Kantarcioglu. 2018. A hybrid private record linkage scheme: Separating differentially private synopses from matching records. Retrieved from https:\/\/www.cs.purdue.edu\/homes\/raof\/DPLinkage_full_version.pdf."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247553"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1186\/1472-6947-9-41"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.221"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.25"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882928"}],"container-title":["ACM Transactions on Privacy and Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3318462","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3318462","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:01:51Z","timestamp":1750208511000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3318462"}},"subtitle":["Separating Differentially Private Synopses from Matching Records"],"short-title":[],"issued":{"date-parts":[[2019,4,26]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3318462"],"URL":"https:\/\/doi.org\/10.1145\/3318462","relation":{},"ISSN":["2471-2566","2471-2574"],"issn-type":[{"value":"2471-2566","type":"print"},{"value":"2471-2574","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,26]]},"assertion":[{"value":"2018-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}