{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T11:02:58Z","timestamp":1777806178568,"version":"3.51.4"},"reference-count":23,"publisher":"SAGE Publications","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JCS"],"published-print":{"date-parts":[[2022,1,20]]},"abstract":"<jats:p>Private set intersection and related functionalities are among the most prominent real-world applications of secure multiparty computation. While such protocols have attracted significant attention from the research community, other functionalities are often required to support a PSI application in practice. For example, in order for two parties to run a PSI over the unique users contained in their databases, they might first invoke a support functionality to agree on the primary keys to represent their users. This paper studies a secure approach to agreeing on primary keys. We introduce and realize a functionality that computes a common set of identifiers based on incomplete information held by two parties, which we refer to as private identity agreement, and we prove the security of our protocol in the honest-but-curious model. We explain the subtleties in designing such a functionality that arise from privacy requirements when intending to compose securely with PSI protocols. We also argue that the cost of invoking this functionality can be amortized over a large number of PSI sessions, and that for applications that require many repeated PSI executions, this represents an improvement over a PSI protocol that directly uses incomplete or fuzzy matches.<\/jats:p>","DOI":"10.3233\/jcs-200115","type":"journal-article","created":{"date-parts":[[2021,12,3]],"date-time":"2021-12-03T10:55:01Z","timestamp":1638528901000},"page":"79-107","source":"Crossref","is-referenced-by-count":0,"title":["Private identity agreement for private set functionalities1"],"prefix":"10.1177","volume":"30","author":[{"given":"Ben","family":"Kreuter","sequence":"first","affiliation":[{"name":"Google, New York, NY, USA. E-mails:\u00a0benkreuter@google.com,\u00a0sarvar@google.com"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sarvar","family":"Patel","sequence":"additional","affiliation":[{"name":"Google, New York, NY, USA. E-mails:\u00a0benkreuter@google.com,\u00a0sarvar@google.com"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ben","family":"Terner","sequence":"additional","affiliation":[{"name":"University of California, Irvine, CA, USA. E-mail:\u00a0bterner@uci.edu"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"key":"10.3233\/JCS-200115_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872771"},{"key":"10.3233\/JCS-200115_ref3","doi-asserted-by":"crossref","unstructured":"K.E.\u00a0Batcher, Sorting networks and their applications, in: Proceedings of the April 30\u2013May 2, 1968, Spring Joint Computer Conference, ACM, 1968, pp.\u00a0307\u2013314.","DOI":"10.1145\/1468075.1468121"},{"issue":"03n04","key":"10.3233\/JCS-200115_ref4","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1142\/S0129626402000999","article-title":"On arbitrary size waksman networks and their vulnerability","volume":"12","author":"Beauquier","year":"2002","journal-title":"Parallel Processing Letters"},{"key":"10.3233\/JCS-200115_ref7","doi-asserted-by":"publisher","DOI":"10.1109\/ARES.2008.170"},{"key":"10.3233\/JCS-200115_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-98113-0_25"},{"key":"10.3233\/JCS-200115_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01957-9_8"},{"key":"10.3233\/JCS-200115_ref10","doi-asserted-by":"crossref","unstructured":"E.\u00a0De Cristofaro, J.\u00a0Kim and G.\u00a0Tsudik, Linear-complexity private set intersection protocols secure in malicious model, in: International Conference on the Theory and Application of Cryptology and Information Security, Springer, 2010, pp.\u00a0213\u2013231.","DOI":"10.1007\/978-3-642-17373-8_13"},{"key":"10.3233\/JCS-200115_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516701"},{"key":"10.3233\/JCS-200115_ref14","doi-asserted-by":"crossref","unstructured":"M.J.\u00a0Freedman, K.\u00a0Nissim and B.\u00a0Pinkas, Efficient private matching and set intersection, in: EUROCRYPT, Lecture Notes in Computer Science, Vol.\u00a03027, Springer, 2004, pp.\u00a01\u201319.","DOI":"10.1007\/978-3-540-24676-3_1"},{"issue":"4","key":"10.3233\/JCS-200115_ref15","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A public key cryptosystem and a signature scheme based on discrete logarithms","volume":"31","author":"Gamal","year":"1985","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.3233\/JCS-200115_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134030"},{"key":"10.3233\/JCS-200115_ref18","unstructured":"Y.\u00a0Huang, D.\u00a0Evans and J.\u00a0Katz, Private set intersection: Are garbled circuits better than custom protocols? in: 19th Annual Network and Distributed System Security Symposium, NDSS 2012, San Diego, California, USA, February 5\u20138, 2012, 2012, pp.\u00a05\u20138, http:\/\/www.internetsociety.org\/private-set-intersection-are-garbled-circuits-better-custom-protocols."},{"key":"10.3233\/JCS-200115_ref19","doi-asserted-by":"publisher","DOI":"10.1145\/336992.337012"},{"key":"10.3233\/JCS-200115_ref20","doi-asserted-by":"crossref","unstructured":"P.\u00a0Indyk and R.\u00a0Motwani, Approximate nearest neighbors: Towards removing the curse of dimensionality, in: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, ACM, 1998, pp.\u00a0604\u2013613.","DOI":"10.1145\/276698.276876"},{"key":"10.3233\/JCS-200115_ref23","doi-asserted-by":"crossref","unstructured":"K.G.\u00a0Larsen and J.B.\u00a0Nielsen, Yes, there is an oblivious ram lower bound! in: Annual International Cryptology Conference, Springer, 2018, pp.\u00a0523\u2013542.","DOI":"10.1007\/978-3-319-96881-0_18"},{"issue":"2","key":"10.3233\/JCS-200115_ref24","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00145-008-9036-8","article-title":"A proof of security of Yao\u2019s protocol for two-party computation","volume":"22","author":"Lindell","year":"2009","journal-title":"J. Cryptol."},{"key":"10.3233\/JCS-200115_ref26","unstructured":"B.\u00a0Pinkas, T.\u00a0Schneider, G.\u00a0Segev and M.\u00a0Zohner, Phasing: Private set intersection using permutation-based hashing, in: 24th USENIX Security Symposium (USENIX Security 15), USENIX Association, Washington, D.C., 2015, pp.\u00a0515\u2013530, https:\/\/www.usenix.org\/conference\/usenixsecurity15\/technical-sessions\/presentation\/pinkas."},{"key":"10.3233\/JCS-200115_ref29","unstructured":"B.\u00a0Pinkas, T.\u00a0Schneider and M.\u00a0Zohner, Faster private set intersection based on ot extension, in: Usenix Security, Vol.\u00a014, 2014, pp.\u00a0797\u2013812."},{"key":"10.3233\/JCS-200115_ref31","unstructured":"A.\u00a0Segal, B.\u00a0Ford and J.\u00a0Feigenbaum, Catching bandits and only bandits: Privacy-preserving intersection warrants for lawful surveillance, in: FOCI, 2014."},{"issue":"1","key":"10.3233\/JCS-200115_ref32","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1145\/321439.321449","article-title":"A permutation network","volume":"15","author":"Waksman","year":"1968","journal-title":"Journal of the ACM (JACM)"},{"key":"10.3233\/JCS-200115_ref33","doi-asserted-by":"publisher","DOI":"10.1145\/2554850.2555001"},{"key":"10.3233\/JCS-200115_ref34","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.88"},{"key":"10.3233\/JCS-200115_ref35","unstructured":"S.\u00a0Zahur and D.\u00a0Evans, Obliv-c: A language for extensible data-oblivious computation, IACR Cryptology ePrint Archive 2015 (2015), 1153."}],"container-title":["Journal of Computer Security"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/JCS-200115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T20:45:35Z","timestamp":1777495535000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.medra.org\/servlet\/aliasResolver?alias=iospress&doi=10.3233\/JCS-200115"}},"subtitle":[],"editor":[{"given":"Clemente","family":"Galdi","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Kolesnikov","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2022,1,20]]},"references-count":23,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.3233\/jcs-200115","relation":{},"ISSN":["1875-8924","0926-227X"],"issn-type":[{"value":"1875-8924","type":"electronic"},{"value":"0926-227X","type":"print"}],"subject":[],"published":{"date-parts":[[2022,1,20]]}}}