Skip to main content

Efficient Set Intersection with Simulation-Based Security

Author(s): Freedman, Michael J; Hazay, Carmit; Nissim, Kobbi; Pinkas, Benny

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1j84x
Full metadata record
DC FieldValueLanguage
dc.contributor.authorFreedman, Michael J-
dc.contributor.authorHazay, Carmit-
dc.contributor.authorNissim, Kobbi-
dc.contributor.authorPinkas, Benny-
dc.date.accessioned2021-10-08T19:49:04Z-
dc.date.available2021-10-08T19:49:04Z-
dc.date.issued2016en_US
dc.identifier.citationFreedman, Michael J., Carmit Hazay, Kobbi Nissim, and Benny Pinkas. "Efficient Set Intersection with Simulation-Based Security." Journal of Cryptology 29 (2016): 115-155. doi:10.1007/s00145-014-9190-0en_US
dc.identifier.issn0933-2790-
dc.identifier.urihttps://www.cs.princeton.edu/~mfreed/docs/FHNP-jcrypt14.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1j84x-
dc.description.abstractWe consider the problem of computing the intersection of private datasets of two parties, where the datasets contain lists of elements taken from a large domain. This problem has many applications for online collaboration. In this work, we present protocols based on the use of homomorphic encryption and different hashing schemes for both the semi-honest and malicious environments. The protocol for the semi-honest environment is secure in the standard model, while the protocol for the malicious environment is secure in the random oracle model. Our protocols obtain linear communication and computation overhead. We further implement different variants of our semi-honest protocol. Our experiments show that the asymptotic overhead of the protocol is affected by different constants. (In particular, the degree of the polynomials evaluated by the protocol matters less than the number of polynomials that are evaluated.) As a result, the protocol variant with the best asymptotic overhead is not necessarily preferable for inputs of reasonable size.en_US
dc.format.extent115 - 155en_US
dc.language.isoen_USen_US
dc.relation.ispartofJournal of Cryptologyen_US
dc.rightsAuthor's manuscripten_US
dc.titleEfficient Set Intersection with Simulation-Based Securityen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1007/s00145-014-9190-0-
dc.identifier.eissn1432-1378-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
EfficientSetIntersectionSimulationBasedSecurity.pdf529.37 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.