{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T07:11:06Z","timestamp":1768547466350,"version":"3.49.0"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,8,21]],"date-time":"2017-08-21T00:00:00Z","timestamp":1503273600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00145-017-9263-y","type":"journal-article","created":{"date-parts":[[2017,8,21]],"date-time":"2017-08-21T19:25:11Z","timestamp":1503343511000},"page":"537-586","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["Oblivious Polynomial Evaluation and Secure Set-Intersection from Algebraic PRFs"],"prefix":"10.1007","volume":"31","author":[{"given":"Carmit","family":"Hazay","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,21]]},"reference":[{"key":"9263_CR1","doi-asserted-by":"crossref","unstructured":"Y. Azar, A.Z. Broder, A.R. Karlin, E. Upfal, Balanced allocations. SIAM J. Comput. 29(1), 180\u2013200 (1999)","DOI":"10.1137\/S0097539795288490"},{"key":"9263_CR2","doi-asserted-by":"crossref","unstructured":"G. Ateniese, E. De Cristofaro, G. Tsudik, (if) size matters: Size-hiding private set intersection, in IACR Cryptology ePrint Archive, 2010:220 (2010)","DOI":"10.1007\/978-3-642-19379-8_10"},{"key":"9263_CR3","unstructured":"G. Ateniese, \u00d6. Dagdelen, I. Damg\u00e5rd, D. Venturi, Entangled cloud storage, in IACR Cryptology ePrint Archive, 2012:511 (2012)"},{"key":"9263_CR4","unstructured":"G. Aggarwal, N. Mishra, B. Pinkas, Secure computation of the kth-ranked element, in EUROCRYPT (2004), pp. 40\u201355"},{"key":"9263_CR5","unstructured":"R. Bendlin, I. Damg\u00e5rd, C. Orlandi, S. Zakarias, Semi-homomorphic encryption and multiparty computation, in EUROCRYPT (2011), pp. 169\u2013188"},{"key":"9263_CR6","unstructured":"D. Beaver, Foundations of secure interactive computing, in CRYPTO (1991), pp. 377\u2013391"},{"key":"9263_CR7","unstructured":"S. Benabbas, R. Gennaro, Y. Vahlis, Verifiable delegation of computation over large datasets, in CRYPTO (2011), pp. 111\u2013131"},{"key":"9263_CR8","unstructured":"A.Z. Broder, M. Mitzenmacher, Using multiple hash functions to improve IP lookups, in INFOCOM (2001), pp. 1454\u20131463"},{"key":"9263_CR9","doi-asserted-by":"crossref","unstructured":"R. Canetti, Security and composition of multi-party cryptographic protocols. Journal of Cryptology 13, 143\u2013202 (2000)","DOI":"10.1007\/s001459910006"},{"key":"9263_CR10","unstructured":"E. De Cristofaro, J. Kim, G. Tsudik, Linear-complexity private set intersection protocols secure in malicious model, in ASIACRYPT (2010), pp. 213\u2013231"},{"key":"9263_CR11","doi-asserted-by":"crossref","unstructured":"Y.C. Chang, C.J. Lu, Oblivious polynomial evaluation and oblivious neural learning. Theor. Comput. Sci. 341(1-3), 39\u201354 (2005)","DOI":"10.1016\/j.tcs.2005.03.049"},{"key":"9263_CR12","unstructured":"D. Chaum, T.P. Pedersen, Wallet databases with observers, in CRYPTO (1992), pp. 89\u2013105"},{"key":"9263_CR13","unstructured":"E. De Cristofaro, G. Tsudik, Practical private set intersection protocols with linear complexity, in Financial Cryptography (2010), pp. 143\u2013159"},{"key":"9263_CR14","doi-asserted-by":"crossref","unstructured":"C. Dong, L. Chen, Z. Wen, When private set intersection meets big data: an effcient and scalable protocol, in IACR Cryptology ePrint Archive, 2013:515 (2013)","DOI":"10.1145\/2508859.2516701"},{"key":"9263_CR15","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, M. Jurik, J.B. Nielsen, A generalization of paillier\u2019s public-key system with applications to electronic voting. Int. J. Inf. Sec. 9(6), 371\u2013385 (2010)","DOI":"10.1007\/s10207-010-0119-9"},{"key":"9263_CR16","unstructured":"I. Damg\u00e5rd, M. Keller, E. Larraia, V. Pastro, P. Scholl, N.P. Smart, Practical covertly secure MPC for dishonest majority - or: Breaking the SPDZ limits, in Computer Security - ESORICS 2013 - 18th European Symposium on Research in Computer Security, Egham, UK, September 9-13, 2013. Proceedings (2013), pp. 1\u201318"},{"key":"9263_CR17","unstructured":"I. Damg\u00e5rd, V. Pastro, N.P. Smart, S. Zakarias, Multiparty computation from somewhat homomorphic encryption, in CRYPTO (2012), pp. 643\u2013662"},{"key":"9263_CR18","unstructured":"D. Dachman-Soled, T. Malkin, M. Raykova, Moti Yung, Efficient robust private set intersection, in ACNS (2009), pp. 125\u2013142"},{"key":"9263_CR19","unstructured":"Y. Dodis, A. Yampolskiy, A verifiable random function with short proofs and keys, in Public Key Cryptography - PKC 2005, 8th International Workshop on Theory and Practice in Public Key Cryptography, Les Diablerets, Switzerland, January 23-26, 2005, Proceedings (2005), pp. 416\u2013431"},{"key":"9263_CR20","doi-asserted-by":"crossref","unstructured":"S. Faust, C. Hazay, D. Venturi, Outsourced pattern matching, in ICALP (2013)","DOI":"10.1007\/978-3-642-39212-2_48"},{"key":"9263_CR21","unstructured":"M.J. Freedman, Y. Ishai, B. Pinkas, O. Reingold, Keyword search and oblivious pseudorandom functions, in TCC (2005), pp. 303\u2013324"},{"key":"9263_CR22","unstructured":"M.J. Freedman, K. Nissim, B. Pinkas, Efficient private matching and set intersection, in EUROCRYPT (2004), pp. 1\u201319"},{"key":"9263_CR23","doi-asserted-by":"crossref","unstructured":"T. El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31(4), 469\u2013472 (1985)","DOI":"10.1109\/TIT.1985.1057074"},{"key":"9263_CR24","unstructured":"N. Gilboa, Two party rsa key generation, in CRYPTO (1999), pp. 116\u2013129"},{"key":"9263_CR25","unstructured":"O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in STOC (1987), pp. 218\u2013229"},{"key":"9263_CR26","unstructured":"O. Goldreich, Foundations of Cryptography: Volume 2, Basic Applications (Cambridge University Press, New York, NY, USA, 2004)"},{"key":"9263_CR27","unstructured":"C. Hazay, Oblivious polynomial evaluation and secure set-intersection from algebraic prfs, in Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part II (2015), pp. 90\u2013120"},{"key":"9263_CR28","unstructured":"C. Hazay, Y. Lindell, Efficient oblivious polynomial evaluation with simulation-based security. IACR Cryptology ePrint Archive, 2009:459 (2009)"},{"key":"9263_CR29","doi-asserted-by":"crossref","unstructured":"C. Hazay, Y. Lindell, Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. J. Cryptology 23(3), 422\u2013456 (2010)","DOI":"10.1007\/s00145-008-9034-x"},{"key":"9263_CR30","doi-asserted-by":"crossref","unstructured":"C. Hazay, Y. Lindell, Efficient Secure Two-Party Protocols \u2013 Techniques and Constructions (Springer-Verlag, 2010)","DOI":"10.1007\/978-3-642-14303-8"},{"key":"9263_CR31","unstructured":"C. Hazay, G.L. Mikkelsen, T. Rabin, T. Toft, Efficient RSA key generation and threshold paillier in the two-party setting, in CT-RSA (2012), pp. 313\u2013331"},{"key":"9263_CR32","doi-asserted-by":"crossref","unstructured":"C. Hazay, K. Nissim, Efficient set operations in the presence of malicious adversaries. J. Cryptology 25(3), 383\u2013433 (2012)","DOI":"10.1007\/s00145-011-9098-x"},{"key":"9263_CR33","unstructured":"C. Hazay, T. Toft, Computationally secure pattern matching in the presence of malicious adversaries, in ASIACRYPT (2010), pp. 195\u2013212"},{"key":"9263_CR34","unstructured":"Y. Ishai, M. Prabhakaran, A. Sahai, Founding cryptography on oblivious transfer\u2014efficiently, in CRYPTO (2008), pp. 572\u2013591"},{"key":"9263_CR35","unstructured":"S. Jarecki, X. Liu, Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection, in TCC (2009), pp. 577\u2013594"},{"key":"9263_CR36","unstructured":"S. Jarecki, X. Liu, Fast secure computation of set intersection, in SCN (2010), pp. 418\u2013435"},{"key":"9263_CR37","unstructured":"A. Kirsch, M. Mitzenmacher, U. Wieder, More robust hashing: Cuckoo hashing with a stash, in Algorithms\u2014ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15\u201317, 2008. Proceedings (2008), pp. 611\u2013622"},{"key":"9263_CR38","unstructured":"L. Kissner, D. Xiaodong Song, Privacy-preserving set operations, in CRYPTO (2005), pp. 241\u2013257"},{"key":"9263_CR39","unstructured":"Y. Lindell, Fast cut-and-choose based protocols for malicious and covert adversaries, in CRYPTO (2) (2013), pp. 1\u201317"},{"key":"9263_CR40","doi-asserted-by":"crossref","unstructured":"Y. Lindell, E. Oxman, B. Pinkas, The IPS compiler: optimizations, variants and concrete efficiency, in CRYPTO, pp. 259\u2013276","DOI":"10.1007\/978-3-642-22792-9_15"},{"key":"9263_CR41","doi-asserted-by":"crossref","unstructured":"Y. Lindell, B. Pinkas, Privacy preserving data mining. J. Cryptology 15(3), 177\u2013206 (2002)","DOI":"10.1007\/s00145-001-0019-2"},{"key":"9263_CR42","unstructured":"Y. Lindell, B. Pinkas, Secure two-party computation via cut-and-choose oblivious transfer, in TCC (2011), pp. 329\u2013346"},{"key":"9263_CR43","unstructured":"S. Micali, P. Rogaway, Secure computation (abstract), in CRYPTO (1991), pp. 392\u2013404"},{"key":"9263_CR44","unstructured":"J.B. Nielsen, P.S. Nordholt, C. Orlandi, S.S. Burra, A new approach to practical active-secure two-party computation, in CRYPTO (2012), pp. 681\u2013700"},{"key":"9263_CR45","unstructured":"J.B. Nielsen, C. Orlandi, Lego for two-party secure computation, in TCC (2009), pp. 368\u2013386"},{"key":"9263_CR46","unstructured":"M. Naor, B. Pinkas, Oblivious transfer and polynomial evaluation, in STOC (1999), pp. 245\u2013254"},{"key":"9263_CR47","doi-asserted-by":"crossref","unstructured":"M. Naor, B. Pinkas, Oblivious polynomial evaluation. SIAM J. Comput. 35(5), 1254\u20131281 (2006)","DOI":"10.1137\/S0097539704383633"},{"key":"9263_CR48","unstructured":"M. Naor, O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, in FOCS, (1997), pp. 458\u2013467"},{"key":"9263_CR49","unstructured":"T. Okamoto, Provably secure and practical identification schemes and corresponding signature schemes, in CRYPTO (1992), pp. 31\u201353"},{"key":"9263_CR50","unstructured":"P. Paillier, Public-key cryptosystems based on composite degree residuosity classes, in EUROCRYPT, (1999), pp. 223\u2013238"},{"key":"9263_CR51","unstructured":"B. Pinkas, T. Schneider, G. Segev, M. Zohner, Phasing: private set intersection using permutation-based hashing, in USENIX (2015), pp. 515\u2013530"},{"key":"9263_CR52","unstructured":"B. Pinkas, T. Schneider, M. Zohner, Faster private set intersection based on OT extension, in Proceedings of the 23rd USENIX Security Symposium, San Diego, CA, USA, August 20\u201322, 2014 (2014), pp. 797\u2013812"},{"key":"9263_CR53","unstructured":"C.P. Schnorr, Efficient identification and signatures for smart cards, in CRYPTO (1989), pp. 239\u2013252"},{"key":"9263_CR54","unstructured":"B. Schoenmakers, P. Tuyls, Practical two-party computation based on the conditional gate, in ASIACRYPT (2004), pp. 119\u2013136"},{"key":"9263_CR55","unstructured":"D. Vergnaud, Efficient and secure generalized pattern matching via fast fourier transform, in AFRICACRYPT (2011), pp. 41\u201358"},{"key":"9263_CR56","unstructured":"A.C.C. Yao, How to generate and exchange secrets (extended abstract), in FOCS (1986), pp. 162\u2013167"},{"key":"9263_CR57","unstructured":"H. Zhu, F. Bao, Augmented oblivious polynomial evaluation protocol and its applications, in ESORICS (2005), pp. 222\u2013230"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-017-9263-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-017-9263-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-017-9263-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T15:21:58Z","timestamp":1659367318000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-017-9263-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,21]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["9263"],"URL":"https:\/\/doi.org\/10.1007\/s00145-017-9263-y","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,21]]},"assertion":[{"value":"15 April 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2017","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}