{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T10:58:42Z","timestamp":1777805922075,"version":"3.51.4"},"reference-count":58,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2014,3,20]],"date-time":"2014-03-20T00:00:00Z","timestamp":1395273600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer Security"],"published-print":{"date-parts":[[2014,3,20]]},"abstract":"<jats:p>Electronic information is increasingly often shared among entities without complete mutual trust. To address related security and privacy issues, a few cryptographic techniques have emerged that support privacy-preserving information sharing and retrieval. One interesting open problem in this context involves two parties that need to assess the similarity of their datasets, but are reluctant to disclose their actual content. This paper presents an efficient and provably-secure construction supporting the privacy-preserving evaluation of sample set similarity, where similarity is measured as the Jaccard index. We present two protocols: the first securely computes the (Jaccard) similarity of two sets, and the second approximates it, using MinHash techniques, with lower complexities. We show that our novel protocols are attractive in many compelling applications, including document\/multimedia similarity, biometric authentication and genetic tests. In the process, we demonstrate that our constructions are appreciably more efficient than prior work.<\/jats:p>","DOI":"10.3233\/jcs-130482","type":"journal-article","created":{"date-parts":[[2016,5,18]],"date-time":"2016-05-18T03:46:42Z","timestamp":1463543202000},"page":"355-381","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":25,"title":["EsPRESSO: Efficient privacy-preserving evaluation of\u00a0sample set similarity"],"prefix":"10.1177","volume":"22","author":[{"given":"Carlo","family":"Blundo","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Salerno, Fisciano, Italy. E-mail:\u00a0"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emiliano","family":"De Cristofaro","sequence":"additional","affiliation":[{"name":"PARC, Palo Alto, CA, USA. E-mail:\u00a0"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Gasti","sequence":"additional","affiliation":[{"name":"New York Institute of Technology, Broadway, NY, USA. E-mail:\u00a0"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2014,3,20]]},"reference":[{"key":"ref001","doi-asserted-by":"crossref","unstructured":"M.J.\u00a0Atallah, M.\u00a0Bykova, J.\u00a0Li, K.B.\u00a0Frikken and M.\u00a0Topkara, Private collaborative forecasting and benchmarking, in: WPES, 2004.","DOI":"10.1145\/1029179.1029204"},{"key":"ref002","unstructured":"G.\u00a0Ateniese, M.\u00a0Blanton and J.\u00a0Kirsch, Secret handshakes with dynamic and fuzzy matching, in: NDSS, 2007."},{"key":"ref003","doi-asserted-by":"crossref","unstructured":"G.\u00a0Ateniese, E.\u00a0De Cristofaro and G.\u00a0Tsudik, (If) size matters: size-hiding private set intersection, in: PKC, 2011.","DOI":"10.1007\/978-3-642-19379-8_10"},{"key":"ref004","doi-asserted-by":"crossref","unstructured":"E.\u00a0Baglioni, L.\u00a0Becchetti, L.\u00a0Bergamini, U.\u00a0Colesanti, L.\u00a0Filipponi, A.\u00a0Vitaletti and G.\u00a0Persiano, A lightweight privacy preserving sms-based recommendation system for mobile users, in: RecSys, 2010.","DOI":"10.1145\/1864708.1864745"},{"key":"ref005","doi-asserted-by":"crossref","unstructured":"P.\u00a0Baldi, R.\u00a0Baronio, E.\u00a0De Cristofaro, P.\u00a0Gasti and G.\u00a0Tsudik, Countering gattaca: efficient and secure testing of fully-sequenced human genomes, in: CCS, 2011.","DOI":"10.1145\/2046707.2046785"},{"key":"ref006","doi-asserted-by":"crossref","unstructured":"M.\u00a0Barni, T.\u00a0Bianchi, D.\u00a0Catalano, M.\u00a0Di Raimondo, R.\u00a0Labati, P.\u00a0Failla, D.\u00a0Fiore, R.\u00a0Lazzeretti, V.\u00a0Piuri, F.\u00a0Scotti and A.\u00a0Piva, Privacy-preserving fingercode authentication, in: MM&Sec, 2010.","DOI":"10.1145\/1854229.1854270"},{"key":"ref007","doi-asserted-by":"crossref","unstructured":"M.\u00a0Blanton and P.\u00a0Gasti, Secure and efficient protocols for iris and fingerprint identification, in: ESORICS, 2011.","DOI":"10.1007\/978-3-642-23822-2_11"},{"key":"ref008","doi-asserted-by":"crossref","unstructured":"A.\u00a0Boldyreva, N.\u00a0Chenette, Y.\u00a0Lee and A.\u00a0O\u2019Neill, Order-preserving symmetric encryption, in: EUROCRYPT, 2009.","DOI":"10.1007\/978-3-642-01001-9_13"},{"key":"ref009","unstructured":"A.\u00a0Broder, On the resemblance and containment of documents, in: Compression and Complexity of Sequences, 1997."},{"key":"ref010","doi-asserted-by":"crossref","unstructured":"A.\u00a0Broder, M.\u00a0Charikar, A.\u00a0Frieze and M.\u00a0Mitzenmacher, Min-wise independent permutations, in: STOC, 1998.","DOI":"10.1007\/3-540-49543-6_2"},{"key":"ref011","doi-asserted-by":"crossref","unstructured":"P.\u00a0Bunn and R.\u00a0Ostrovsky, Secure two-party k-means clustering, in: CCS, 2007.","DOI":"10.1145\/1315245.1315306"},{"key":"ref012","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"ref013","unstructured":"S.\u00a0Cimato, M.\u00a0Gamassi, V.\u00a0Piuri, R.\u00a0Sassi and F.\u00a0Scotti, Privacy in Biometrics, Wiley\u2013IEEE Press, 2009."},{"key":"ref014","unstructured":"S.D.\u00a0Cohen and L.J.\u00a0Guibas, Shape-based image retrieval using geometric hashing, in: ARPA Image Understanding Workshop, 1997."},{"key":"ref015","unstructured":"Cornell Univ., KDDCUP Dataset, available at: http:\/\/www.cs.cornell.edu\/projects\/kddcup\/datasets.html."},{"key":"ref016","doi-asserted-by":"crossref","unstructured":"E.D.\u00a0Cristofaro, S.\u00a0Faber, P.\u00a0Gasti and G.\u00a0Tsudik, Genodroid: are privacy-preserving genomic tests ready for prime time? in: WPES, 2012.","DOI":"10.1145\/2381966.2381980"},{"key":"ref017","doi-asserted-by":"crossref","unstructured":"E.\u00a0De Cristofaro, P.\u00a0Gasti and G.\u00a0Tsudik, Fast and private computation of cardinality of set intersection and union, in: CANS, 2012.","DOI":"10.1007\/978-3-642-35404-5_17"},{"key":"ref018","unstructured":"U.S. Department of Homeland Security, available at: http:\/\/www.dhs.gov\/files\/programs\/usv.shtm."},{"key":"ref019","doi-asserted-by":"publisher","DOI":"10.1128\/AEM.66.6.2572-2577.2000"},{"key":"ref020","doi-asserted-by":"crossref","unstructured":"Z.\u00a0Erkin, M.\u00a0Franz, J.\u00a0Guajardo, S.\u00a0Katzenbeisser, I.\u00a0Lagendijk and T.\u00a0Toft, Privacy-preserving face recognition, in: PETS, 2009.","DOI":"10.1007\/978-3-642-03168-7_14"},{"key":"ref021","doi-asserted-by":"publisher","DOI":"10.1155\/2007\/78943"},{"key":"ref022","doi-asserted-by":"crossref","unstructured":"M.\u00a0Freedman, K.\u00a0Nissim and B.\u00a0Pinkas, Efficient private matching and set intersection, in: EUROCRYPT, 2004.","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"ref023","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, Foundations of Cryptography, Cambridge Univ. Press, 2004.","DOI":"10.1017\/CBO9780511721656"},{"key":"ref024","unstructured":"IrisGuard Press Release, available at: http:\/\/cl.ly\/3KIB."},{"key":"ref025","unstructured":"P.\u00a0Jaccard, Etude comparative de la distribution florale dans une portion des Alpes et du Jura, 1901."},{"key":"ref026","doi-asserted-by":"publisher","DOI":"10.1109\/83.841531"},{"key":"ref027","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(95)00160-3"},{"key":"ref028","doi-asserted-by":"crossref","unstructured":"W.\u00a0Jiang, M.\u00a0Murugesan, C.\u00a0Clifton and L.\u00a0Si, Similar document detection with limited information disclosure, in: ICDE, 2008.","DOI":"10.1109\/ICDE.2008.4497482"},{"key":"ref029","doi-asserted-by":"crossref","unstructured":"W.\u00a0Jiang and B.K.\u00a0Samanthula, N-gram based secure similar document detection, in: DBSec 2011, Lecture Notes in Computer Science, Springer, 2011.","DOI":"10.1007\/978-3-642-22348-8_19"},{"key":"ref030","doi-asserted-by":"crossref","unstructured":"M.\u00a0Kantarcioglu, R.\u00a0Nix and J.\u00a0Vaidya, An efficient approximate protocol for privacy-preserving association rule mining, in: KDD, 2009.","DOI":"10.1007\/978-3-642-01307-2_48"},{"key":"ref031","doi-asserted-by":"crossref","unstructured":"S.\u00a0Katti, B.\u00a0Krishnamurthy and D.\u00a0Katabi, Collaborating against common enemies, in: IMC, 2005.","DOI":"10.1145\/1330107.1330151"},{"key":"ref032","doi-asserted-by":"crossref","unstructured":"F.\u00a0Kerschbaum, Outsourced private set intersection using homomorphic encryption, in: AsiaCCS, 2012.","DOI":"10.1145\/2414456.2414506"},{"key":"ref033","doi-asserted-by":"crossref","unstructured":"L.\u00a0Kissner and D.\u00a0Song, Privacy-preserving set operations, in: CRYPTO, 2005.","DOI":"10.21236\/ADA457144"},{"key":"ref034","doi-asserted-by":"crossref","unstructured":"M.\u00a0Li, N.\u00a0Cao, S.\u00a0Yu and W.\u00a0Lou, Findu: Privacy-preserving personal profile matching in mobile social networks, in: INFOCOM, 2011.","DOI":"10.1109\/INFCOM.2011.5935065"},{"key":"ref035","doi-asserted-by":"crossref","unstructured":"H.\u00a0Lipmaa, Verifiable homomorphic oblivious transfer and private equality test, in: ASIACRYPT, 2003.","DOI":"10.1007\/978-3-540-40061-5_27"},{"key":"ref036","doi-asserted-by":"crossref","unstructured":"W.\u00a0Lu, A.\u00a0Swaminathan, A.L.\u00a0Varna and M.\u00a0Wu, Enabling search over encrypted multimedia databases, in: Media Forensics and Security, 2009.","DOI":"10.1117\/12.806980"},{"key":"ref037","doi-asserted-by":"crossref","unstructured":"W.\u00a0Lu, A.L.\u00a0Varna, A.\u00a0Swaminathan and M.\u00a0Wu, Secure image retrieval through feature protection, in: ICASSP, 2009.","DOI":"10.1109\/ICASSP.2009.4959888"},{"key":"ref038","unstructured":"W.Y.\u00a0Ma and B.S.\u00a0Manjunath, Texture features and learning similarity, in: CVPR, 1996."},{"key":"ref039","unstructured":"U.\u00a0Manber, Finding similar files in a large file system, in: USENIX, 1994."},{"key":"ref040","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0175-9"},{"key":"ref041","doi-asserted-by":"crossref","unstructured":"W.\u00a0Niblack, R.\u00a0Barber, W.\u00a0Equitz, M.\u00a0Flickner, E.H.\u00a0Glasman, D.\u00a0Petkovic, P.\u00a0Yanker, C.\u00a0Faloutsos and G.\u00a0Taubin, The QBIC project: Querying images by content, using color, texture, and shape, in: SPIE, 1993.","DOI":"10.1117\/12.143648"},{"key":"ref042","unstructured":"Ookla Net Metrics, Canada and US source data, available at: http:\/\/www.netindex.com\/source-data\/, 2011."},{"key":"ref043","doi-asserted-by":"crossref","unstructured":"M.\u00a0Osadchy, B.\u00a0Pinkas, A.\u00a0Jarrous and B.\u00a0Moskovich, SCiFI \u2013 A system for secure face identification, in: IEEE S&P, 2010.","DOI":"10.1109\/SP.2010.39"},{"key":"ref044","unstructured":"P.\u00a0Paillier, Public-key cryptosystems based on composite degree residuosity classes, in: EUROCRYPT, 1999."},{"key":"ref045","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2006.37"},{"key":"ref046","unstructured":"P.\u00a0Ravikumar, W.\u00a0Cohen and S.\u00a0Fienberg, A secure protocol for computing string distance metrics, in: PSDM, 2004."},{"key":"ref047","doi-asserted-by":"crossref","unstructured":"A.R.\u00a0Sadeghi, T.\u00a0Schneider and I.\u00a0Wehrenberg, Efficient privacy-preserving face recognition, in: ICISC, 2009.","DOI":"10.1007\/978-3-642-14423-3_16"},{"key":"ref048","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(96)00108-2"},{"key":"ref049","doi-asserted-by":"crossref","unstructured":"M.\u00a0Singh, P.\u00a0Krishna and A.\u00a0Saxena, A privacy preserving Jaccard similarity function for mining encrypted data, in: TENCON, 2009.","DOI":"10.1109\/TENCON.2009.5395869"},{"key":"ref050","doi-asserted-by":"publisher","DOI":"10.1109\/34.895972"},{"key":"ref051","unstructured":"J.R.\u00a0Smith and S.F.\u00a0Chang, Tools and techniques for color image retrieval, in: SPIE, 1996."},{"key":"ref052","unstructured":"A.\u00a0Strehl, J.\u00a0Ghosh and R.\u00a0Mooney, Impact of similarity measures on web-page clustering, in: AAAI, 2000."},{"key":"ref053","unstructured":"P.\u00a0Tan, M.\u00a0Steinbach, V.\u00a0Kumar et al., Introduction to Data Mining, Pearson, 2006."},{"key":"ref054","doi-asserted-by":"publisher","DOI":"10.3233\/JCS-2005-13401"},{"key":"ref055","doi-asserted-by":"crossref","unstructured":"C.\u00a0Xiao, W.\u00a0Wang, X.\u00a0Lin and J.\u00a0Yu, Efficient similarity joins for near duplicate detection, in: WWW, 2008.","DOI":"10.1145\/1367497.1367516"},{"key":"ref056","doi-asserted-by":"crossref","unstructured":"A.\u00a0Yao, How to generate and exchange secrets, in: FOCS, 1986.","DOI":"10.1109\/SFCS.1986.25"},{"key":"ref057","unstructured":"Youtube press release, available at: http:\/\/www.youtube.com\/t\/press_statistics."},{"key":"ref058","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Zhang, W.\u00a0Liu and W.\u00a0Lou, Anonymous communications in mobile ad hoc networks, in: INFOCOM, Vol.\u00a03, 2005.","DOI":"10.1007\/0-387-22690-7_9"}],"container-title":["Journal of Computer Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-130482","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JCS-130482","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-130482","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T20:44:44Z","timestamp":1777495484000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JCS-130482"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,20]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,3,20]]}},"alternative-id":["10.3233\/JCS-130482"],"URL":"https:\/\/doi.org\/10.3233\/jcs-130482","relation":{},"ISSN":["0926-227X","1875-8924"],"issn-type":[{"value":"0926-227X","type":"print"},{"value":"1875-8924","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,3,20]]}}}