{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,31]],"date-time":"2026-10-31T21:29:36Z","timestamp":1793482176157,"version":"4.5.0"},"reference-count":54,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"1","license":[{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    In 2-party Circuit-based Private Set Intersection (Circuit-PSI),\n                    <jats:italic>P<\/jats:italic>\n                    <jats:sub>0<\/jats:sub>\n                    and\n                    <jats:italic>P<\/jats:italic>\n                    <jats:sub>1<\/jats:sub>\n                    hold sets S\n                    <jats:sub>0<\/jats:sub>\n                    and S\n                    <jats:sub>1<\/jats:sub>\n                    respectively and wish to securely compute a function\n                    <jats:italic>f<\/jats:italic>\n                    over the set S\n                    <jats:sub>0<\/jats:sub>\n                    \u2229 S\n                    <jats:sub>1<\/jats:sub>\n                    (e.g., cardinality, sum over associated attributes, or threshold intersection). Following a long line of work, Pinkas\n                    <jats:italic>et al.<\/jats:italic>\n                    (PSTY, Eurocrypt 2019) showed how to construct a concretely efficient Circuit-PSI protocol with linear communication complexity. However, their protocol requires super-linear computation.\n                  <\/jats:p>\n                  <jats:p>\n                    In this work, we construct concretely efficient Circuit-PSI protocols with linear computational and communication cost. Further, our protocols are more performant than the state-of-the-art, PSTY \u2013 we are \u2248 2.3\n                    <jats:italic>\u00d7<\/jats:italic>\n                    more communication efficient and are up to 2.8\n                    <jats:italic>\u00d7<\/jats:italic>\n                    faster. We obtain our improvements through a new primitive called\n                    <jats:italic>Relaxed Batch Oblivious Programmable Pseudorandom Functions<\/jats:italic>\n                    (RB-OPPRF) that can be seen as a strict generalization of Batch OPPRFs that were used in PSTY. This primitive could be of independent interest.\n                  <\/jats:p>","DOI":"10.2478\/popets-2022-0018","type":"journal-article","created":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T21:43:35Z","timestamp":1637444615000},"page":"353-372","source":"Crossref","is-referenced-by-count":66,"title":["Circuit-PSI With Linear Complexity via Relaxed Batch OPPRF"],"prefix":"10.56553","volume":"2022","author":[{"given":"Nishanth","family":"Chandran","sequence":"first","affiliation":[{"name":"Microsoft Research ."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Divya","family":"Gupta","sequence":"additional","affiliation":[{"name":"Microsoft Research ."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Akash","family":"Shah","sequence":"additional","affiliation":[{"name":"UCLA. Work done at Microsoft Research ."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"35752","published-online":{"date-parts":[[2021,11,20]]},"reference":[{"key":"2022062314355513878_j_popets-2022-0018_ref_001","doi-asserted-by":"crossref","unstructured":"[1] Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: CCS (2013)10.1145\/2508859.2516738","DOI":"10.1145\/2508859.2516738"},{"key":"2022062314355513878_j_popets-2022-0018_ref_002","doi-asserted-by":"crossref","unstructured":"[2] Badrinarayanan, S., Miao, P., Raghuraman, S., Rindal, P.: Multi-party threshold private set intersection with sublinear communication. In: PKC (2021)10.1007\/978-3-030-75248-4_13","DOI":"10.1007\/978-3-030-75248-4_13"},{"key":"2022062314355513878_j_popets-2022-0018_ref_003","unstructured":"[3] Beaver, D.: Efficient multiparty protocols using circuit randomization. In: CRYPTO (1991)"},{"key":"2022062314355513878_j_popets-2022-0018_ref_004","doi-asserted-by":"crossref","unstructured":"[4] Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: STOC (1988)10.1145\/62212.62213","DOI":"10.1145\/62212.62213"},{"key":"2022062314355513878_j_popets-2022-0018_ref_005","doi-asserted-by":"crossref","unstructured":"[5] Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Efficient pseudorandom correlation generators: Silent OT extension and more. In: CRYPTO (2019)10.1007\/978-3-030-26954-8_16","DOI":"10.1007\/978-3-030-26954-8_16"},{"key":"2022062314355513878_j_popets-2022-0018_ref_006","unstructured":"[6] Brassard, G., Cr\u00e9peau, C., Robert, J.: All-or-nothing disclosure of secrets. In: CRYPTO (1986)"},{"key":"2022062314355513878_j_popets-2022-0018_ref_007","doi-asserted-by":"crossref","unstructured":"[7] Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: FOCS (2001)10.1109\/SFCS.2001.959888","DOI":"10.1109\/SFCS.2001.959888"},{"key":"2022062314355513878_j_popets-2022-0018_ref_008","doi-asserted-by":"crossref","unstructured":"[8] Chase, M., Miao, P.: Private set intersection in the internet setting from lightweight oblivious PRF. In: CRYPTO (2020)10.1007\/978-3-030-56877-1_2","DOI":"10.1007\/978-3-030-56877-1_2"},{"key":"2022062314355513878_j_popets-2022-0018_ref_009","doi-asserted-by":"crossref","unstructured":"[9] Ciampi, M., Orlandi, C.: Combining private set-intersection with secure two-party computation. In: SCN (2018)10.1007\/978-3-319-98113-0_25","DOI":"10.1007\/978-3-319-98113-0_25"},{"key":"2022062314355513878_j_popets-2022-0018_ref_010","doi-asserted-by":"crossref","unstructured":"[10] Couteau, G.: New protocols for secure equality test and comparison. In: ACNS (2018)10.1007\/978-3-319-93387-0_16","DOI":"10.1007\/978-3-319-93387-0_16"},{"key":"2022062314355513878_j_popets-2022-0018_ref_011","doi-asserted-by":"crossref","unstructured":"[11] Cristofaro, E.D., Kim, J., Tsudik, G.: Linear-complexity private set intersection protocols secure in malicious model. In: ASIACRYPT (2010)10.1007\/978-3-642-17373-8_13","DOI":"10.1007\/978-3-642-17373-8_13"},{"key":"2022062314355513878_j_popets-2022-0018_ref_012","doi-asserted-by":"crossref","unstructured":"[12] Demmler, D., Schneider, T., Zohner, M.: ABY - A framework for efficient mixed-protocol secure two-party computation. In: NDSS (2015)10.14722\/ndss.2015.23113","DOI":"10.14722\/ndss.2015.23113"},{"key":"2022062314355513878_j_popets-2022-0018_ref_013","doi-asserted-by":"crossref","unstructured":"[13] Dessouky, G., Koushanfar, F., Sadeghi, A., Schneider, T., Zeitouni, S., Zohner, M.: Pushing the communication barrier in secure computation using lookup tables. In: NDSS (2017)10.14722\/ndss.2017.23097","DOI":"10.14722\/ndss.2017.23097"},{"key":"2022062314355513878_j_popets-2022-0018_ref_014","doi-asserted-by":"crossref","unstructured":"[14] Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: CCS (2013)10.1145\/2508859.2516701","DOI":"10.1145\/2508859.2516701"},{"key":"2022062314355513878_j_popets-2022-0018_ref_015","unstructured":"[15] Encrypto Group: OPPRF-PSI. https:\/\/github.com\/encryptogroup\/OPPRF-PSI, Accessed: 2020-10-07"},{"key":"2022062314355513878_j_popets-2022-0018_ref_016","unstructured":"[16] Falk, B.H., Noble, D., Ostrovsky, R.: Private set intersection with linear communication from general assumptions. In: ACM WPES@CCS (2019)"},{"key":"2022062314355513878_j_popets-2022-0018_ref_017","doi-asserted-by":"crossref","unstructured":"[17] Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: TCC (2005)10.1007\/978-3-540-30576-7_17","DOI":"10.1007\/978-3-540-30576-7_17"},{"key":"2022062314355513878_j_popets-2022-0018_ref_018","doi-asserted-by":"crossref","unstructured":"[18] Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: EUROCRYPT (2004)10.1007\/978-3-540-24676-3_1","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"2022062314355513878_j_popets-2022-0018_ref_019","unstructured":"[19] Garay, J.A., Schoenmakers, B., Villegas, J.: Practical and secure solutions for integer comparison. In: PKC (2007)"},{"key":"2022062314355513878_j_popets-2022-0018_ref_020","doi-asserted-by":"crossref","unstructured":"[20] Ghosh, S., Nilges, T.: An algebraic approach to maliciously secure private set intersection. In: EUROCRYPT (2019)10.1007\/978-3-030-17659-4_6","DOI":"10.1007\/978-3-030-17659-4_6"},{"key":"2022062314355513878_j_popets-2022-0018_ref_021","doi-asserted-by":"crossref","unstructured":"[21] Ghosh, S., Simkin, M.: The communication complexity of threshold private set intersection. In: CRYPTO (2019)10.1007\/978-3-030-26951-7_1","DOI":"10.1007\/978-3-030-26951-7_1"},{"key":"2022062314355513878_j_popets-2022-0018_ref_022","unstructured":"[22] Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions (extended abstract). In: FOCS (1984)"},{"key":"2022062314355513878_j_popets-2022-0018_ref_023","doi-asserted-by":"crossref","unstructured":"[23] Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: STOC (1987)10.1145\/28395.28420","DOI":"10.1145\/28395.28420"},{"key":"2022062314355513878_j_popets-2022-0018_ref_024","doi-asserted-by":"crossref","unstructured":"[24] Hallgren, P.A., Orlandi, C., Sabelfeld, A.: Privatepool: Privacy-preserving ridesharing. In: CSF (2017)10.1109\/CSF.2017.24","DOI":"10.1109\/CSF.2017.24"},{"key":"2022062314355513878_j_popets-2022-0018_ref_025","unstructured":"[25] Huang, Y., Evans, D., Katz, J.: Private set intersection: Are garbled circuits better than custom protocols? In: NDSS (2012)"},{"key":"2022062314355513878_j_popets-2022-0018_ref_026","doi-asserted-by":"crossref","unstructured":"[26] Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: CRYPTO (2003)10.1007\/978-3-540-45146-4_9","DOI":"10.1007\/978-3-540-45146-4_9"},{"key":"2022062314355513878_j_popets-2022-0018_ref_027","doi-asserted-by":"crossref","unstructured":"[27] Karako\u00e7, F., K\u00fcp\u00e7\u00fc, A.: Linear complexity private set intersection for secure two-party protocols. In: CANS (2020)10.1007\/978-3-030-65411-5_20","DOI":"10.1007\/978-3-030-65411-5_20"},{"key":"2022062314355513878_j_popets-2022-0018_ref_028","doi-asserted-by":"crossref","unstructured":"[28] Karako\u00e7, F., Nateghizad, M., Erkin, Z.: SET-OT: A secure equality testing protocol based on oblivious transfer. In: ARES (2019)10.1145\/3339252.3339264","DOI":"10.1145\/3339252.3339264"},{"key":"2022062314355513878_j_popets-2022-0018_ref_029","doi-asserted-by":"crossref","unstructured":"[29] Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: Cuckoo hashing with a stash. SIAM J. Comput. 39(4) (2009)10.1137\/080728743","DOI":"10.1137\/080728743"},{"key":"2022062314355513878_j_popets-2022-0018_ref_030","doi-asserted-by":"crossref","unstructured":"[30] Kolesnikov, V., Kumaresan, R.: Improved OT extension for transferring short secrets. In: CRYPTO (2013)10.1007\/978-3-642-40084-1_4","DOI":"10.1007\/978-3-642-40084-1_4"},{"key":"2022062314355513878_j_popets-2022-0018_ref_031","doi-asserted-by":"crossref","unstructured":"[31] Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched oblivious PRF with applications to private set intersection. In: CCS (2016)10.1145\/2976749.2978381","DOI":"10.1145\/2976749.2978381"},{"key":"2022062314355513878_j_popets-2022-0018_ref_032","doi-asserted-by":"crossref","unstructured":"[32] Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., Trieu, N.: Practical multi-party private set intersection from symmetric-key techniques. In: CCS (2017)10.1145\/3133956.3134065","DOI":"10.1145\/3133956.3134065"},{"key":"2022062314355513878_j_popets-2022-0018_ref_033","unstructured":"[33] Kreuter, B.: Secure multiparty computation at google. In: RWC (2017)"},{"key":"2022062314355513878_j_popets-2022-0018_ref_034","unstructured":"[34] Lindell, Y.: How to simulate it - a tutorial on the simulation proof technique. Cryptology ePrint Archive, Report 2016\/046 (2016)"},{"key":"2022062314355513878_j_popets-2022-0018_ref_035","doi-asserted-by":"crossref","unstructured":"[35] Meadows, C.A.: A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In: IEEE S & P (1986)10.1109\/SP.1986.10022","DOI":"10.1109\/SP.1986.10022"},{"key":"2022062314355513878_j_popets-2022-0018_ref_036","unstructured":"[36] mpc-msri: EzPC. https:\/\/github.com\/mpc-msri\/EzPC, Accessed: 2020-10-07"},{"key":"2022062314355513878_j_popets-2022-0018_ref_037","unstructured":"[37] Oleksandr-Tkachenko: HashingTables. https:\/\/github.com\/Oleksandr-Tkachenko\/HashingTables, Accessed: 2020-10-07"},{"key":"2022062314355513878_j_popets-2022-0018_ref_038","unstructured":"[38] osu-crypto: libOTe. https:\/\/github.com\/osu-crypto\/libOTe, Accessed: 2020-10-07"},{"key":"2022062314355513878_j_popets-2022-0018_ref_039","doi-asserted-by":"crossref","unstructured":"[39] Pagh, R., Rodler, F.F.: Cuckoo hashing. In: Algorithms -ESA (2001)10.7146\/brics.v8i32.21692","DOI":"10.7146\/brics.v8i32.21692"},{"key":"2022062314355513878_j_popets-2022-0018_ref_040","doi-asserted-by":"crossref","unstructured":"[40] Pinkas, B., Rosulek, M., Trieu, N., Yanai, A.: Spot-light: Lightweight private set intersection from sparse OT extension. In: CRYPTO (2019)10.1007\/978-3-030-26954-8_13","DOI":"10.1007\/978-3-030-26954-8_13"},{"key":"2022062314355513878_j_popets-2022-0018_ref_041","doi-asserted-by":"crossref","unstructured":"[41] Pinkas, B., Rosulek, M., Trieu, N., Yanai, A.: PSI from paxos: Fast, malicious private set intersection. In: EURO-CRYPT (2020)10.1145\/3460120.3484778","DOI":"10.1007\/978-3-030-45724-2_25"},{"key":"2022062314355513878_j_popets-2022-0018_ref_042","unstructured":"[42] Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: Private set intersection using permutation-based hashing. In: USENIX Security (2015)"},{"key":"2022062314355513878_j_popets-2022-0018_ref_043","doi-asserted-by":"crossref","unstructured":"[43] Pinkas, B., Schneider, T., Tkachenko, O., Yanai, A.: Efficient circuit-based PSI with linear communication. In: EUROCRYPT (2019)10.1007\/978-3-030-17659-4_5","DOI":"10.1007\/978-3-030-17659-4_5"},{"key":"2022062314355513878_j_popets-2022-0018_ref_044","doi-asserted-by":"crossref","unstructured":"[44] Pinkas, B., Schneider, T., Weinert, C., Wieder, U.: Efficient circuit-based PSI via cuckoo hashing. In: EUROCRYPT (2018)10.1007\/978-3-319-78372-7_5","DOI":"10.1007\/978-3-319-78372-7_5"},{"key":"2022062314355513878_j_popets-2022-0018_ref_045","doi-asserted-by":"crossref","unstructured":"[45] Pinkas, B., Schneider, T., Zohner, M.: Scalable private set intersection based on OT extension. ACM Trans. Priv. Secur. 21(2) (2018)10.1145\/3154794","DOI":"10.1145\/3154794"},{"key":"2022062314355513878_j_popets-2022-0018_ref_046","unstructured":"[46] Rabin, M.O.: How to exchange secrets with oblivious transfer. Cryptology ePrint Archive, Report 2005\/187 (2005)"},{"key":"2022062314355513878_j_popets-2022-0018_ref_047","doi-asserted-by":"crossref","unstructured":"[47] Rathee, D., Rathee, M., Kumar, N., Chandran, N., Gupta, D., Rastogi, A., Sharma, R.: Cryptflow2: Practical 2-party secure inference. In: CCS (2020)10.1145\/3372297.3417274","DOI":"10.1145\/3372297.3417274"},{"key":"2022062314355513878_j_popets-2022-0018_ref_048","doi-asserted-by":"crossref","unstructured":"[48] Rindal, P., Schoppmann, P.: VOLE-PSI: fast OPRF and circuit-psi from vector-ole. In: EUROCRYPT (2021)10.1007\/978-3-030-77886-6_31","DOI":"10.1007\/978-3-030-77886-6_31"},{"key":"2022062314355513878_j_popets-2022-0018_ref_049","doi-asserted-by":"crossref","unstructured":"[49] Shamir, A.: How to share a secret. Commun. ACM 22(11) (1979)10.1145\/359168.359176","DOI":"10.1145\/359168.359176"},{"key":"2022062314355513878_j_popets-2022-0018_ref_050","doi-asserted-by":"crossref","unstructured":"[50] Shamir, A.: On the power of commutativity in cryptography. In: ICALP (1980)10.1007\/3-540-10003-2_100","DOI":"10.1007\/3-540-10003-2_100"},{"key":"2022062314355513878_j_popets-2022-0018_ref_051","doi-asserted-by":"crossref","unstructured":"[51] Yang, K., Weng, C., Lan, X., Zhang, J., Wang, X.: Ferret: Fast extension for correlated OT with small communication. In: CCS (2020)10.1145\/3372297.3417276","DOI":"10.1145\/3372297.3417276"},{"key":"2022062314355513878_j_popets-2022-0018_ref_052","doi-asserted-by":"crossref","unstructured":"[52] Yao, A.C.: How to generate and exchange secrets (extended abstract). In: FOCS (1986)10.1109\/SFCS.1986.25","DOI":"10.1109\/SFCS.1986.25"},{"key":"2022062314355513878_j_popets-2022-0018_ref_053","doi-asserted-by":"crossref","unstructured":"[53] Zhao, Y., Chow, S.S.M.: Are you the one to share? secret transfer with access structure. PoPETs 2017(1), 149\u2013169 (2017)10.1515\/popets-2017-0010","DOI":"10.1515\/popets-2017-0010"},{"key":"2022062314355513878_j_popets-2022-0018_ref_054","doi-asserted-by":"crossref","unstructured":"[54] Zhao, Y., Chow, S.S.M.: Can you find the one for me? In: WPES@CCS (2018)10.1145\/3267323.3268965","DOI":"10.1145\/3267323.3268965"}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/popets-2022-0018","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T12:31:55Z","timestamp":1658320315000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2022\/popets-2022-0018.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,20]]},"references-count":54,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,11,20]]},"published-print":{"date-parts":[[2022,1,1]]}},"alternative-id":["10.2478\/popets-2022-0018"],"URL":"https:\/\/doi.org\/10.2478\/popets-2022-0018","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,20]]}}}