{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T12:53:00Z","timestamp":1773838380793,"version":"3.50.1"},"reference-count":63,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"4","license":[{"start":{"date-parts":[[2017,10,1]],"date-time":"2017-10-01T00:00:00Z","timestamp":1506816000000},"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":[[2017,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Private set intersection (PSI) is a cryptographic technique that is applicable to many privacy-sensitive scenarios. For decades, researchers have been focusing on improving its efficiency in both communication and computation. However, most of the existing solutions are inefficient for an unequal number of inputs, which is common in conventional client-server settings. In this paper, we analyze and optimize the efficiency of existing PSI protocols to support precomputation so that they can efficiently deal with such input sets. We transform four existing PSI protocols into the precomputation form such that in the setup phase the communication is linear only in the size of the larger input set, while in the online phase the communication is linear in the size of the smaller input set. We implement all four protocols and run experiments between two PCs and between a PC and a smartphone and give a systematic comparison of their performance. Our experiments show that a protocol based on securely evaluating a garbled AES circuit achieves the fastest setup time by several orders of magnitudes, and the fastest online time in the PC setting where AES-NI acceleration is available. In the mobile setting, the fastest online time is achieved by a protocol based on the Diffie-Hellman assumption.<\/jats:p>","DOI":"10.1515\/popets-2017-0044","type":"journal-article","created":{"date-parts":[[2017,10,17]],"date-time":"2017-10-17T10:01:46Z","timestamp":1508234506000},"page":"177-197","source":"Crossref","is-referenced-by-count":85,"title":["Private Set Intersection for Unequal Set Sizes with Mobile Applications"],"prefix":"10.56553","volume":"2017","author":[{"given":"\u00c1gnes","family":"Kiss","sequence":"first","affiliation":[{"name":"TU Darmstadt"}]},{"given":"Jian","family":"Liu","sequence":"additional","affiliation":[{"name":"Aalto University"}]},{"given":"Thomas","family":"Schneider","sequence":"additional","affiliation":[{"name":"TU Darmstadt"}]},{"given":"N.","family":"Asokan","sequence":"additional","affiliation":[{"name":"Aalto University and University of Helsinki"}]},{"given":"Benny","family":"Pinkas","sequence":"additional","affiliation":[{"name":"Bar Ilan University"}]}],"member":"35752","published-online":{"date-parts":[[2017,10,10]]},"reference":[{"key":"2021040805135714625_j_popets-2017-0044_ref_001_w2aab3b7b9b1b6b1ab1ab1Aa","unstructured":"[1] M. R. Albrecht, C. Rechberger, T. Schneider, T. Tiessen, and M. Zohner, \u201cCiphers for MPC and FHE,\u201d in Advances in Cryptology \u2013 EUROCRYPT\u201915, ser. LNCS, vol. 9056. Springer, 2015, pp. 430\u2013454."},{"key":"2021040805135714625_j_popets-2017-0044_ref_002_w2aab3b7b9b1b6b1ab1ab2Aa","doi-asserted-by":"crossref","unstructured":"[2] G. Asharov, Y. Lindell, T. Schneider, and M. Zohner, \u201cMore efficient oblivious transfer and extensions for faster secure computation,\u201d in ACM Computer and Communications Security (CCS\u201913). ACM, 2013, pp. 535\u2013548.","DOI":"10.1145\/2508859.2516738"},{"key":"2021040805135714625_j_popets-2017-0044_ref_003_w2aab3b7b9b1b6b1ab1ab3Aa","unstructured":"[3] \u2014\u2014, \u201cMore efficient oblivious transfer extensions with security for malicious adversaries,\u201d in Advances in Cryptology \u2013 EUROCRYPT\u201915, ser. LNCS, vol. 9056. Springer, 2015, pp. 673\u2013701."},{"key":"2021040805135714625_j_popets-2017-0044_ref_004_w2aab3b7b9b1b6b1ab1ab4Aa","unstructured":"[4] N. Asokan, A. Dmitrienko, M. Nagy, E. Reshetova, A. Sadeghi, T. Schneider, and S. Stelle, \u201cCrowdShare: Secure mobile resource sharing,\u201d in Applied Cryptography and Network Security (ACNS\u201913), ser. LNCS, vol. 7954. Springer, 2013, pp. 432\u2013440."},{"key":"2021040805135714625_j_popets-2017-0044_ref_005_w2aab3b7b9b1b6b1ab1ab5Aa","doi-asserted-by":"crossref","unstructured":"[5] P. Baldi, R. Baronio, E. De Cristofaro, P. Gasti, and G. Tsudik, \u201cCountering GATTACA: efficient and secure testing of fully-sequenced human genomes,\u201d in ACM Computer and Communications Security (CCS\u201911). ACM, 2011, pp. 691\u2013702.","DOI":"10.1145\/2046707.2046785"},{"key":"2021040805135714625_j_popets-2017-0044_ref_006_w2aab3b7b9b1b6b1ab1ab6Aa","doi-asserted-by":"crossref","unstructured":"[6] D. Beaver, \u201cPrecomputing oblivious transfer,\u201d in Advances in Cryptology \u2013 CRYPTO\u201995, ser. LNCS, vol. 963. Springer, 1995, pp. 97\u2013109.","DOI":"10.1007\/3-540-44750-4_8"},{"key":"2021040805135714625_j_popets-2017-0044_ref_007_w2aab3b7b9b1b6b1ab1ab7Aa","doi-asserted-by":"crossref","unstructured":"[7] M. Bellare, V. T. Hoang, S. Keelveedhi, and P. Rogaway, \u201cEfficient garbling from a fixed-key blockcipher,\u201d in IEEE Symposium on Security and Privacy (S&P\u201913). IEEE, 2013, pp. 478\u2013492.","DOI":"10.1109\/SP.2013.39"},{"key":"2021040805135714625_j_popets-2017-0044_ref_008_w2aab3b7b9b1b6b1ab1ab8Aa","unstructured":"[8] L. Bouncy Castle Inc., \u201cBouncy Castle crypto APIs,\u201d https:\/\/www.bouncycastle.org\/, 2017, accessed: 2017-03-10."},{"key":"2021040805135714625_j_popets-2017-0044_ref_009_w2aab3b7b9b1b6b1ab1ab9Aa","unstructured":"[9] J. Boyar and R. Peralta, \u201cA new combinational logic minimization technique with applications to cryptology,\u201d in Symposium on Experimental Algorithms (SEA\u201910), ser. LNCS, vol. 6049. Springer, 2010, pp. 178\u2013189."},{"key":"2021040805135714625_j_popets-2017-0044_ref_010_w2aab3b7b9b1b6b1ab1ac10Aa","unstructured":"[10] H. Carter, C. Amrutkar, I. Dacosta, and P. Traynor, \u201cFor your phone only: custom protocols for efficient secure function evaluation on mobile devices,\u201d Security and Communication Networks, vol. 7, no. 7, pp. 1165\u20131176, 2014."},{"key":"2021040805135714625_j_popets-2017-0044_ref_011_w2aab3b7b9b1b6b1ab1ac11Aa","unstructured":"[11] E. D. Cristofaro and G. Tsudik, \u201cPractical private set intersection protocols with linear complexity,\u201d in Financial Cryptography and Data Security (FC\u201910), ser. LNCS, vol. 6052. Springer, 2010, pp. 143\u2013159."},{"key":"2021040805135714625_j_popets-2017-0044_ref_012_w2aab3b7b9b1b6b1ab1ac12Aa","unstructured":"[12] \u2014\u2014, \u201cExperimenting with fast private set intersection,\u201d in Trust and Trustworthy Computing (TRUST\u201912), ser. LNCS, vol. 7344. Springer, 2012, pp. 55\u201373."},{"key":"2021040805135714625_j_popets-2017-0044_ref_013_w2aab3b7b9b1b6b1ab1ac13Aa","unstructured":"[13] D. Demmler, T. Schneider, and M. Zohner, \u201cAd-hoc secure two-party computation on mobile devices using hardware tokens,\u201d in USENIX Security Symposium\u201914. USENIX, 2014, pp. 893\u2013908."},{"key":"2021040805135714625_j_popets-2017-0044_ref_014_w2aab3b7b9b1b6b1ab1ac14Aa","unstructured":"[14] \u2014\u2014, \u201cABY - A framework for efficient mixed-protocol secure two-party computation,\u201d in Network and Distributed System Security Symposium (NDSS\u201915). The Internet Society, 2015."},{"key":"2021040805135714625_j_popets-2017-0044_ref_015_w2aab3b7b9b1b6b1ab1ac15Aa","doi-asserted-by":"crossref","unstructured":"[15] W. Diffie and M. E. Hellman, \u201cNew directions in cryptography,\u201d IEEE Trans. Information Theory, vol. 22, no. 6, pp. 644\u2013654, 1976.10.1109\/TIT.1976.1055638","DOI":"10.1109\/TIT.1976.1055638"},{"key":"2021040805135714625_j_popets-2017-0044_ref_016_w2aab3b7b9b1b6b1ab1ac16Aa","unstructured":"[16] I. Dinur, Y. Liu, W. Meier, and Q. Wang, \u201cOptimized interpolation attacks on LowMC,\u201d in Advances in Cryptology \u2013 ASIACRYPT\u201915, ser. LNCS, vol. 9453. Springer, 2015, pp. 535\u2013560."},{"key":"2021040805135714625_j_popets-2017-0044_ref_017_w2aab3b7b9b1b6b1ab1ac17Aa","unstructured":"[17] C. Dobraunig, M. Eichlseder, and F. Mendel, \u201cHigher-order cryptanalysis of LowMC,\u201d in Information Security and Cryptology (ICISC\u201915), ser. LNCS, vol. 9558. Springer, 2015, pp. 87\u2013101."},{"key":"2021040805135714625_j_popets-2017-0044_ref_018_w2aab3b7b9b1b6b1ab1ac18Aa","doi-asserted-by":"crossref","unstructured":"[18] C. Dong, L. Chen, and Z. Wen, \u201cWhen private set intersection meets big data: an efficient and scalable protocol,\u201d in ACM Computer and Communications Security (CCS\u201913). ACM, 2013, pp. 789\u2013800.","DOI":"10.1145\/2508859.2516701"},{"key":"2021040805135714625_j_popets-2017-0044_ref_019_w2aab3b7b9b1b6b1ab1ac19Aa","doi-asserted-by":"crossref","unstructured":"[19] L. Fan, P. Cao, J. M. Almeida, and A. Z. Broder, \u201cSummary cache: A scalable wide-area web cache sharing protocol,\u201d in SIGCOMM\u201998. ACM, 1998, pp. 254\u2013265.","DOI":"10.1145\/285243.285287"},{"key":"2021040805135714625_j_popets-2017-0044_ref_020_w2aab3b7b9b1b6b1ab1ac20Aa","unstructured":"[20] M. Fischlin, B. Pinkas, A. Sadeghi, T. Schneider, and I. Visconti, \u201cSecure set intersection with untrusted hardware tokens,\u201d in Topics in Cryptology \u2013 CT-RSA\u201911, ser. LNCS, vol. 6558. Springer, 2011, pp. 1\u201316."},{"key":"2021040805135714625_j_popets-2017-0044_ref_021_w2aab3b7b9b1b6b1ab1ac21Aa","unstructured":"[21] F. S. Foundation, \u201cThe GNU multiple precision arithmetic library,\u201d https:\/\/gmplib.org, 2017, accessed: 2017-03-10."},{"key":"2021040805135714625_j_popets-2017-0044_ref_022_w2aab3b7b9b1b6b1ab1ac22Aa","unstructured":"[22] M. J. Freedman, Y. Ishai, B. Pinkas, and O. Reingold, \u201cKeyword search and oblivious pseudorandom functions,\u201d in Theory of Cryptography Conference (TCC\u201905), ser. LNCS, vol. 3378. Springer, 2005, pp. 303\u2013324."},{"key":"2021040805135714625_j_popets-2017-0044_ref_023_w2aab3b7b9b1b6b1ab1ac23Aa","unstructured":"[23] M. J. Freedman, K. Nissim, and B. Pinkas, \u201cEfficient private matching and set intersection,\u201d in Advances in Cryptology \u2013 EUROCRYPT\u201904, ser. LNCS, vol. 3027. Springer, 2004, pp. 1\u201319."},{"key":"2021040805135714625_j_popets-2017-0044_ref_024_w2aab3b7b9b1b6b1ab1ac24Aa","doi-asserted-by":"crossref","unstructured":"[24] P. Gasti and K. B. Rasmussen, \u201cPrivacy-preserving user matching,\u201d in ACM Workshop on Privacy in the Electronic Society (WPES\u201915). ACM, 2015, pp. 111\u2013120.","DOI":"10.1145\/2808138.2808148"},{"key":"2021040805135714625_j_popets-2017-0044_ref_025_w2aab3b7b9b1b6b1ab1ac25Aa","doi-asserted-by":"crossref","unstructured":"[25] C. Gentry, \u201cFully homomorphic encryption using ideal lattices,\u201d in ACM Symposium on Theory of Computing (STOC\u201909). ACM, 2009, pp. 169\u2013178.","DOI":"10.1145\/1536414.1536440"},{"key":"2021040805135714625_j_popets-2017-0044_ref_026_w2aab3b7b9b1b6b1ab1ac26Aa","unstructured":"[26] N. Gilboa and Y. Ishai, \u201cDistributed point functions and their applications,\u201d in Advances in Cryptology \u2013 EUROCRYPT\u2019 14, ser. LNCS, vol. 8441. Springer, 2014, pp. 640\u2013658."},{"key":"2021040805135714625_j_popets-2017-0044_ref_027_w2aab3b7b9b1b6b1ab1ac27Aa","unstructured":"[27] D. Giry, \u201cBlueKrypt cryptogrphic key length recommendation,\u201d http:\/\/www.keylength.com, 2017, accessed: 2017-02-28."},{"key":"2021040805135714625_j_popets-2017-0044_ref_028_w2aab3b7b9b1b6b1ab1ac28Aa","doi-asserted-by":"crossref","unstructured":"[28] S. D. Gordon, J. Katz, V. Kolesnikov, F. Krell, T. Malkin, M. Raykova, and Y. Vahlis, \u201cSecure two-party computation in sublinear (amortized) time,\u201d in ACM Conference on Computer and Communications Security (CCS\u201912). ACM, 2012, pp. 513\u2013524.","DOI":"10.1145\/2382196.2382251"},{"key":"2021040805135714625_j_popets-2017-0044_ref_029_w2aab3b7b9b1b6b1ab1ac29Aa","doi-asserted-by":"crossref","unstructured":"[29] L. Grassi, C. Rechberger, D. Rotaru, P. Scholl, and N. P. Smart, \u201cMPC-friendly symmetric key primitives,\u201d in ACM Computer and Communications Security (CCS\u201916). ACM, 2016, pp. 430\u2013443.","DOI":"10.1145\/2976749.2978332"},{"key":"2021040805135714625_j_popets-2017-0044_ref_030_w2aab3b7b9b1b6b1ab1ac30Aa","doi-asserted-by":"crossref","unstructured":"[30] C. Hazay and Y. Lindell, \u201cConstructions of truly practical secure protocols using standard smartcards,\u201d in ACM Computer and Communications Security (CCS\u201908). ACM, 2008, pp. 491\u2013500.","DOI":"10.1145\/1455770.1455832"},{"key":"2021040805135714625_j_popets-2017-0044_ref_031_w2aab3b7b9b1b6b1ab1ac31Aa","unstructured":"[31] \u2014\u2014, \u201cEfficient protocols for set intersection and pattern matching with security against malicious and covert adversaries,\u201d in Theory of Cryptography Conference (TCC\u201908), ser. LNCS, vol. 4948. Springer, 2008, pp. 155\u2013175."},{"key":"2021040805135714625_j_popets-2017-0044_ref_032_w2aab3b7b9b1b6b1ab1ac32Aa","doi-asserted-by":"crossref","unstructured":"[32] W. Henecka and T. Schneider, \u201cFaster secure two-party computation with less memory,\u201d in Computer and Communications Security (ASIACCS\u201913). ACM, 2013, pp. 437\u2013446.","DOI":"10.1145\/2484313.2484369"},{"key":"2021040805135714625_j_popets-2017-0044_ref_033_w2aab3b7b9b1b6b1ab1ac33Aa","unstructured":"[33] Y. Huang, P. Chapman, and D. Evans, \u201cPrivacy-preserving applications on smartphones,\u201d in USENIX Workshop on Hot Topics in Security (HotSec\u201911). USENIX, 2011."},{"key":"2021040805135714625_j_popets-2017-0044_ref_034_w2aab3b7b9b1b6b1ab1ac34Aa","unstructured":"[34] Y. Huang, D. Evans, and J. Katz, \u201cPrivate set intersection: Are garbled circuits better than custom protocols?\u201d in Network and Distributed System Security Symposium (NDSS\u201912). The Internet Society, 2012."},{"key":"2021040805135714625_j_popets-2017-0044_ref_035_w2aab3b7b9b1b6b1ab1ac35Aa","doi-asserted-by":"crossref","unstructured":"[35] B. A. Huberman, M. K. Franklin, and T. Hogg, \u201cEnhancing privacy and trust in electronic communities,\u201d in ACM Conference on Electronic Commerce (EC\u201999), 1999, pp. 78\u201386.","DOI":"10.1145\/336992.337012"},{"key":"2021040805135714625_j_popets-2017-0044_ref_036_w2aab3b7b9b1b6b1ab1ac36Aa","unstructured":"[36] Y. Ishai, J. Kilian, K. Nissim, and E. Petrank, \u201cExtending oblivious transfers efficiently,\u201d in Advances in Cryptology \u2013 CRYPTO\u201903, ser. LNCS, vol. 2729. Springer, 2003, pp. 145\u2013161."},{"key":"2021040805135714625_j_popets-2017-0044_ref_037_w2aab3b7b9b1b6b1ab1ac37Aa","unstructured":"[37] S. Jarecki and X. Liu, \u201cEfficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection,\u201d in Theory of Cryptography Conference (TCC\u201909), ser. LNCS, vol. 5444. Springer, 2009, pp. 577\u2013594."},{"key":"2021040805135714625_j_popets-2017-0044_ref_038_w2aab3b7b9b1b6b1ab1ac38Aa","unstructured":"[38] M. Keller, E. Orsini, and P. Scholl, \u201cActively secure OT extension with optimal overhead,\u201d in Advances in Cryptology \u2013 CRYPTO\u201915, ser. LNCS, vol. 9215. Springer, 2015, pp. 724\u2013741."},{"key":"2021040805135714625_j_popets-2017-0044_ref_039_w2aab3b7b9b1b6b1ab1ac39Aa","doi-asserted-by":"crossref","unstructured":"[39] V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu, \u201cEfficient batched oblivious PRF with applications to private set intersection,\u201d in ACM Computer and Communications Security (CCS\u201916). ACM, 2016, pp. 818\u2013829.","DOI":"10.1145\/2976749.2978381"},{"key":"2021040805135714625_j_popets-2017-0044_ref_040_w2aab3b7b9b1b6b1ab1ac40Aa","unstructured":"[40] V. Kolesnikov and T. Schneider, \u201cImproved garbled circuit: Free XOR gates and applications,\u201d in International Colloquium on Automata, Languages and Programming (ICALP\u201908), ser. LNCS, vol. 5126. Springer, 2008, pp. 486\u2013498."},{"key":"2021040805135714625_j_popets-2017-0044_ref_041_w2aab3b7b9b1b6b1ab1ac41Aa","doi-asserted-by":"crossref","unstructured":"[41] E. Kushilevitz and R. Ostrovsky, \u201cReplication is NOT needed: SINGLE database, computationally-private information retrieval,\u201d in Foundations of Computer Science (FOCS \u201997). IEEE Computer Society, 1997, pp. 364\u2013373.","DOI":"10.1109\/SFCS.1997.646125"},{"key":"2021040805135714625_j_popets-2017-0044_ref_042_w2aab3b7b9b1b6b1ab1ac42Aa","doi-asserted-by":"crossref","unstructured":"[42] Y. Lindell and B. Pinkas, \u201cA proof of security of Yao\u2019s protocol for two-party computation,\u201d Journal of Cryptology, vol. 22, no. 2, pp. 161\u2013188, 2009.10.1007\/s00145-008-9036-8","DOI":"10.1007\/s00145-008-9036-8"},{"key":"2021040805135714625_j_popets-2017-0044_ref_043_w2aab3b7b9b1b6b1ab1ac43Aa","doi-asserted-by":"crossref","unstructured":"[43] C. Liu, X. S. Wang, K. Nayak, Y. Huang, and E. Shi, \u201cObliVM: A programming framework for secure computation,\u201d in Symposium on Security and Privacy (S&P\u201915). IEEE Computer Society, 2015, pp. 359\u2013376, implementation available at: https:\/\/github.com\/oblivm\/ObliVMGC.","DOI":"10.1109\/SP.2015.29"},{"key":"2021040805135714625_j_popets-2017-0044_ref_044_w2aab3b7b9b1b6b1ab1ac44Aa","doi-asserted-by":"crossref","unstructured":"[44] C. A. Meadows, \u201cA more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party,\u201d in IEEE Symposium on Security and Privacy (S&P\u201986). IEEE, 1986, pp. 134\u2013137.","DOI":"10.1109\/SP.1986.10022"},{"key":"2021040805135714625_j_popets-2017-0044_ref_045_w2aab3b7b9b1b6b1ab1ac45Aa","doi-asserted-by":"crossref","unstructured":"[45] T. Meskanen, J. Liu, S. Ramezanian, and V. Niemi, \u201cPrivate membership test for Bloom filters,\u201d in International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom\u201915). IEEE, 2015, pp. 515\u2013522.","DOI":"10.1109\/Trustcom.2015.414"},{"key":"2021040805135714625_j_popets-2017-0044_ref_046_w2aab3b7b9b1b6b1ab1ac46Aa","unstructured":"[46] S. Nagaraja, P. Mittal, C. Hong, M. Caesar, and N. Borisov, \u201cBotgrep: Finding P2P bots with structured graph analysis,\u201d in USENIX Security Symposium\u201910. USENIX, 2010, pp. 95\u2013110."},{"key":"2021040805135714625_j_popets-2017-0044_ref_047_w2aab3b7b9b1b6b1ab1ac47Aa","doi-asserted-by":"crossref","unstructured":"[47] M. Nagy, E. D. Cristofaro, A. Dmitrienko, N. Asokan, and A. Sadeghi, \u201cDo I know you?: efficient and privacy-preserving common friend-finder protocols and applications,\u201d in Annual Computer Security Applications Conference (ACSAC\u2019 13), 2013, pp. 159\u2013168.","DOI":"10.1145\/2523649.2523668"},{"key":"2021040805135714625_j_popets-2017-0044_ref_048_w2aab3b7b9b1b6b1ab1ac48Aa","doi-asserted-by":"crossref","unstructured":"[48] M. Naor and O. Reingold, \u201cNumber-theoretic constructions of efficient pseudo-random functions,\u201d J. ACM, vol. 51, no. 2, pp. 231\u2013262, 2004.","DOI":"10.1145\/972639.972643"},{"key":"2021040805135714625_j_popets-2017-0044_ref_049_w2aab3b7b9b1b6b1ab1ac49Aa","unstructured":"[49] A. Narayanan, N. Thiagarajan, M. Lakhani, M. Hamburg, and D. Boneh, \u201cLocation privacy via private proximity testing,\u201d in Network and Distributed System Security Symposium (NDSS\u201911). The Internet Society, 2011."},{"key":"2021040805135714625_j_popets-2017-0044_ref_050_w2aab3b7b9b1b6b1ab1ac50Aa","unstructured":"[50] R. Nojima and Y. Kadobayashi, \u201cCryptographically secure Bloom-filters,\u201d Trans. Data Privacy, vol. 2, no. 2, pp. 131\u2013139, 2009."},{"key":"2021040805135714625_j_popets-2017-0044_ref_051_w2aab3b7b9b1b6b1ab1ac51Aa","unstructured":"[51] A. Pagh, R. Pagh, and S. S. Rao, \u201cAn optimal Bloom filter replacement,\u201d in ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905). SIAM, 2005, pp. 823\u2013829."},{"key":"2021040805135714625_j_popets-2017-0044_ref_052_w2aab3b7b9b1b6b1ab1ac52Aa","unstructured":"[52] A. Partow, \u201cBloom filter implementation,\u201d https:\/\/github.com\/ArashPartow\/bloom, 2017, accessed: 2017-03-10."},{"key":"2021040805135714625_j_popets-2017-0044_ref_053_w2aab3b7b9b1b6b1ab1ac53Aa","unstructured":"[53] B. Pinkas, T. Schneider, G. Segev, and M. Zohner, \u201cPhasing: Private set intersection using permutation-based hashing,\u201d in USENIX Security Symposium\u201915. USENIX, 2015, pp. 515\u2013530."},{"key":"2021040805135714625_j_popets-2017-0044_ref_054_w2aab3b7b9b1b6b1ab1ac54Aa","unstructured":"[54] B. Pinkas, T. Schneider, N. P. Smart, and S. C. Williams, \u201cSecure two-party computation is practical,\u201d in Advances in Cryptology \u2013 ASIACRYPT\u201909, ser. LNCS, vol. 5912. Springer, 2009, pp. 250\u2013267."},{"key":"2021040805135714625_j_popets-2017-0044_ref_055_w2aab3b7b9b1b6b1ab1ac55Aa","unstructured":"[55] B. Pinkas, T. Schneider, and M. Zohner, \u201cFaster private set intersection based on OT extension,\u201d in USENIX Security Symposium\u201914. USENIX, 2014, pp. 797\u2013812."},{"key":"2021040805135714625_j_popets-2017-0044_ref_056_w2aab3b7b9b1b6b1ab1ac56Aa","unstructured":"[56] \u2014\u2014, \u201cScalable private set intersection based on OT extension,\u201d IACR Cryptology ePrint Archive, vol. 2016\/930, 2016, http:\/\/ia.cr\/2016\/930."},{"key":"2021040805135714625_j_popets-2017-0044_ref_057_w2aab3b7b9b1b6b1ab1ac57Aa","unstructured":"[57] S. Ramezanian, \u201cA Study of Privacy Preserving Queries with Bloom Filters,\u201d Master\u2019s thesis, University of Turku, Finland, 2016."},{"key":"2021040805135714625_j_popets-2017-0044_ref_058_w2aab3b7b9b1b6b1ab1ac58Aa","doi-asserted-by":"crossref","unstructured":"[58] K. Shimizu, K. Nuida, H. Arai, S. Mitsunari, N. Attrapadung, M. Hamada, K. Tsuda, T. Hirokawa, J. Sakuma, G. Hanaoka, and K. Asai, \u201cPrivacy-preserving search for chemical compound databases,\u201d BMC Bioinformatics, vol. 16, no. 18, p. S6, 2015.","DOI":"10.1186\/1471-2105-16-S18-S6"},{"key":"2021040805135714625_j_popets-2017-0044_ref_059_w2aab3b7b9b1b6b1ab1ac59Aa","unstructured":"[59] R. Sion and B. Carbunar, \u201cOn the practicality of private information retrieval,\u201d in Network and Distributed System Security Symposium (NDSS\u201907). The Internet Society, 2007."},{"key":"2021040805135714625_j_popets-2017-0044_ref_060_w2aab3b7b9b1b6b1ab1ac60Aa","doi-asserted-by":"crossref","unstructured":"[60] S. Tamrakar, J. Liu, A. Paverd, J. Ekberg, B. Pinkas, and N. Asokan, \u201cThe circle game: Scalable private membership test using trusted hardware,\u201d in ACM Asia Computer and Communications Security (AsiaCCS\u201917). ACM, 2017, pp. 31\u201344.","DOI":"10.1145\/3052973.3053006"},{"key":"2021040805135714625_j_popets-2017-0044_ref_061_w2aab3b7b9b1b6b1ab1ac61Aa","doi-asserted-by":"crossref","unstructured":"[61] A. C.-C. Yao, \u201cHow to generate and exchange secrets,\u201d in Foundations of Computer Science (FOCS\u201986). IEEE, 1986, pp. 162\u2013167.","DOI":"10.1109\/SFCS.1986.25"},{"key":"2021040805135714625_j_popets-2017-0044_ref_062_w2aab3b7b9b1b6b1ab1ac62Aa","unstructured":"[62] A. C. Yao, \u201cProtocols for secure computations (extended abstract),\u201d in Foundations of Computer Science (FOCS\u201982). IEEE, 1982, pp. 160\u2013164."},{"key":"2021040805135714625_j_popets-2017-0044_ref_063_w2aab3b7b9b1b6b1ab1ac63Aa","unstructured":"[63] S. Zahur, M. Rosulek, and D. Evans, \u201cTwo halves make a whole - reducing data transfer in garbled circuits using half gates,\u201d in Advances in Cryptology \u2013 EUROCRYPT\u201915, ser. LNCS, vol. 9057. Springer, 2015, pp. 220\u2013250."}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/popets\/2017\/4\/article-p177.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/article\/10.1515\/popets-2017-0044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T14:50:37Z","timestamp":1750949437000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2017\/popets-2017-0044.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,1]]},"references-count":63,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2017,10,10]]},"published-print":{"date-parts":[[2017,10,1]]}},"alternative-id":["10.1515\/popets-2017-0044"],"URL":"https:\/\/doi.org\/10.1515\/popets-2017-0044","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,1]]}}}