Efficient Set Intersection with Simulation-Based Security

Michael Joseph Freedman, Carmit Hazay, Kobbi Nissim, Benny Pinkas

Research output: Contribution to journalArticle

29 Citations (Scopus)

Abstract

We 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.

Original languageEnglish (US)
Pages (from-to)115-155
Number of pages41
JournalJournal of Cryptology
Volume29
Issue number1
DOIs
StatePublished - Jan 1 2016

Fingerprint

Efficient Set
Intersection
Polynomials
Cryptography
Simulation
Communication
Experiments
Homomorphic Encryption
Polynomial
Random Oracle Model
Hashing
Standard Model
Computing

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Applied Mathematics

Cite this

Freedman, Michael Joseph ; Hazay, Carmit ; Nissim, Kobbi ; Pinkas, Benny. / Efficient Set Intersection with Simulation-Based Security. In: Journal of Cryptology. 2016 ; Vol. 29, No. 1. pp. 115-155.
@article{206c7a2fd82c4015af21118da374a3a1,
title = "Efficient Set Intersection with Simulation-Based Security",
abstract = "We 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.",
author = "Freedman, {Michael Joseph} and Carmit Hazay and Kobbi Nissim and Benny Pinkas",
year = "2016",
month = "1",
day = "1",
doi = "10.1007/s00145-014-9190-0",
language = "English (US)",
volume = "29",
pages = "115--155",
journal = "Journal of Cryptology",
issn = "0933-2790",
publisher = "Springer New York",
number = "1",

}

Efficient Set Intersection with Simulation-Based Security. / Freedman, Michael Joseph; Hazay, Carmit; Nissim, Kobbi; Pinkas, Benny.

In: Journal of Cryptology, Vol. 29, No. 1, 01.01.2016, p. 115-155.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Efficient Set Intersection with Simulation-Based Security

AU - Freedman, Michael Joseph

AU - Hazay, Carmit

AU - Nissim, Kobbi

AU - Pinkas, Benny

PY - 2016/1/1

Y1 - 2016/1/1

N2 - We 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.

AB - We 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.

UR - http://www.scopus.com/inward/record.url?scp=84955414958&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84955414958&partnerID=8YFLogxK

U2 - 10.1007/s00145-014-9190-0

DO - 10.1007/s00145-014-9190-0

M3 - Article

VL - 29

SP - 115

EP - 155

JO - Journal of Cryptology

JF - Journal of Cryptology

SN - 0933-2790

IS - 1

ER -