Private Set Intersection: Past, Present and Future
Ionita Andreea
Faculty of Computer Science, Alexandru Ioan Cuza University, Iasi, Romania
Keywords:
Private Set Intersection, Bilinear Maps, Symmetric Encryption, Secret Sharing, Modular Inverse.
Abstract:
Privacy has been more and more difficult to obtain since the development of the Internet. Private set inter-
section has been and still is a subject of great interest. In this paper we present the state of the art for PSI
and propose four new directions for PSI protocols based on bilinear maps, secret sharing, modular inverse and
symmetric encryption. Although our proposals are not the best in terms of efficiency, we believe that there are
many optimizations to be done to achieve performance competitive with the best known protocols.
1 INTRODUCTION
With the development of the Internet, privacy has be-
come increasingly difficult to obtain. A specific prob-
lem of privacy that is hard to obtain is the intersection
of two sets. Making the intersection of two sets is
of course a easy thing to do, but when privacy comes
in, it becomes a lot harder. Lets say we have a so-
cial network and we want to keep friendships private
for each user. However, if two users want to see their
mutual friends and preserve the privacy of non-mutual
friends, they may need a private set intersection pro-
tocol. Of course, there is the trivial solution where
both A and B give their input to a trusted third party in
order to compute the intersection set. However, hav-
ing a trusted third party only happens in fairy-tales. In
terms of secure multiparty computation, private set in-
tersection is a technique that allows two parties hold-
ing sets to compare encrypted versions of these sets
in order to compute the intersection. It is desired that
any of the two participants does not learn more than it
should. We further present some applications for PSI:
1. Covid19 App. Every user collects tracing data on
their mobile phones. If the local health authorities
diagnose a user positive with the coronavirus, the
user can share their data and transfer it to a server.
Any other user of the app can now learn if they
have potentially been in contact with a positive
tested user by asking that server with the updated
data.
2. Mobile Messaging Service. Someone who uses
an application ”APP” for mobile messaging ser-
vice wants to know who is using the same appli-
cation from its contacts. Of course, his privacy is
very important to him and does not want the com-
pany who owns ”APP” to know his contacts.
3. Paternity Tests Privacy.
Outline. We give definitions of PSI types and cryp-
tography and present the adversary model in Section
2. In Section 3 we classify PSI protocols in public-
key cryptography based PSI, generic-secure compu-
tation based PSI and OT-based PSI. Also, we focus
on some hybrid protocols that we present in detail. In
Section 4 we propose four new PSI approaches based
on modular inverse, bilinear maps, secret sharing and
self encryption. In the last section, we conclude our
study about PSI.
2 PRELIMINARIES
2.1 Adversary Model
Semi-honest Model. This type of adversary is also
known as honest-but-curious. As the name implies,
a semi-honest party tries to be honest, so follows the
protocol properly but is curious so it keeps a record of
all its intermediate computations.
Security in Semi-honest Model. A protocol is con-
sidered to be secure in a semi-honest setting if and
only if the view obtained in the execution is the same
as the view obtained in the ideal model. In the case
of semi-honest adversaries, the ideal model consists
of each party sending its input to the trusted party,
and the third party computing the corresponding out-
put pair and sending each output to the corresponding
party.
Malicious Adversary in Ideal Model. In this type of
setting we consider the followings scenarios: • Input:
Each party receives its input u. The honest party al-
ways sends u to the TTP, but the malicious party may
680
Andreea, I.
Private Set Intersection: Past, Present and Future.
DOI: 10.5220/0010525806800685
In Proceedings of the 18th International Conference on Security and Cryptography (SECRYPT 2021), pages 680-685
ISBN: 978-989-758-524-1
Copyright
c
2021 by SCITEPRESS – Science and Technology Publications, Lda. All rights reserved
send an arbitrary u
0
or abort. • TTP’s answer: In case
the TTP obtained an input pair, it replies the first party
with the wanted answer. Otherwise, it send ”NULL”.
In case the first party (who received the answer) is ma-
licious, it may stop the TTP to send the answer to the
second party. If so, TTP sends ”NULL” to the second
party. If the TTP is not stopped, it sends the answer
to the second party.
Malicious Adversary in Real Model. The malicious
party can have any strategy implementable by a prob-
abilistic polynomial-time algorithm to get informa-
tion that he should not get.
Security in Malicious Model. Loosely speaking, the
definition asserts that a secure two-party protocol em-
ulates the ideal model. This is formulated by saying
that admissible adversaries in the ideal model are able
to simulate the execution of a secure real-model pro-
tocol under any admissible adversaries.
2.2 Cryptographic Primitives
Oblivious Pseudorandom Function. In an oblivi-
ous pseudorandom function, information is concealed
from two parties that are involved in a PRF. That is, if
Alice gives the input for a PRF to Bob, and Bob com-
putes a PRF and gives the output to Alice, Bob is not
able to see either the input or the output, and Alice is
not able to see the secret key Bob uses with the PRF.
Permutation-based Hashing. Permutation-based
hashing is a technique that allows the hashed elements
to be converted in shorter strings that can be stored in
the hash table for reducing storage space and compu-
tation complexity.
Cuckoo Hashing. Pagh and Rodler
(PaghandRodler, 2004) proposed a dynamiza-
tion of a static dictionary that uses two hash tables:
T
1
and T
2
, each consisting of r words and two hash
functions h
1
, h
2
. Every key x ∈ S is stored either in
cell h
1
(x) of T
1
or in cell h
2
(x) of T
2
, but never in
both.
Paillier Cryptosystem. is a probabilistic asymmetric
algorithm for public key cryptography that is based on
the intractability of decisional composite residuosity
assumption. The problem of computing n-th residue
classes is believed to be computationally difficult.
The Paillier cryptosystem supports:homomorphic ad-
dition of plaintexts and homomorphic multiplication
of plaintexts.
2.3 Efficient Data Structures
Bloom Filter: is a compressed data structure, with
the the use of which, a set of n elements can be com-
pressed to an array A of m bits.
Oblivious Keyword Search (OKS): is a structure
that allows a user to search and retrieve the data as-
sociated with a chosen keyword in an oblivious way.
3 STATE OF THE ART IN PSI
We choose to use the classification made by (Pinkas
et al., 2014) for PSI protocols: 1. Public-key cryp-
tography-based PSI; 2. Generic secure computa-
tion-based PSI; 3. Oblivious transfer-based PSI. For
each classification, we point out the main ideas of the
type of protocol and the related work.
3.1 Public-key Cryptography-based PSI
Diffie Helman. In (Meadows, 1986) it is proposed
the first protocol for private matching with the use
of Diffie Helman key exchange scheme. In the be-
ginning the server chooses a secret a and the client
chooses a secret b. The idea is quite simple: server
encrypts its input {x
1
, x
2
, ..., x
n
} as {x
a
1
, x
a
2
, ..., x
a
n
}
and client encrypts its input {y
1
, y
2
, ..., y
n
} as
{y
b
1
, y
b
2
, ..., y
b
n
}. They send their encryptions to each
other and compute {(y
b
1
)
a
, (y
b
2
)
a
, ..., (y
b
n
)
a
} respec-
tively {(x
a
1
)
b
, (x
a
2
)
b
, ..., (x
a
n
)
b
}. Because both a and b
are secret, it is hard to compute g
ab
from knowing
(g
a
, g
b
).
RSA. The protocols based on RSA make use of
strong RSA assumption.
The work by Cristofaro and Tsudik (De Cristo-
faro and Tsudik, 2010) addressed the problem of pri-
vate set intersection by means of RSA signature. They
adapt Ogata and Kurosava’s adaptive Oblivious Key-
word Search (Ogata and Kurosawa, 2004) for the PSI
scenario as it follows: ” instead of encrypting a string
of 0’s the server reveals the key as the hash of the
signature for all elements in her set”. Despite the ef-
ficiency of the protocol it comes with some issues.
One of them is the fact that the double running of the
protocol reveals to the client the changes made in the
server’s set.
3.2 Generic Secure Computation-based
PSI
There are generic protocols that solve general prob-
lems of secure two party computation. More specif-
ically, these protocols allow two parties to securely
evaluate any function that can be expressed as a
Boolean circuit. A Boolean circuit is a mathemati-
cal model for combinational digital logic circuits. It
Private Set Intersection: Past, Present and Future
681
provides a model for many digital components used
in computer engineering. The generic protocol that
we want to focus on is Yao’s garbled circuits protocol
that is used to evaluate any discrete function that can
be represented as a circuit. That means, in terms of
PSI, that both the Server and the Client put together
their inputs and evaluate the intersection function with
no leaking beyond what is implied by the intersection
output.
In 2012 there was the belief that solutions for PSI
using generic approaches were impractical so Huang,
Evans and Katz decided to explore the validity of
that belief. In (Huang et al., 2012) they perform PSI
using Yao’s generic garbled circuit approach obtain-
ing efficient protocols assuming the semi-honest set-
ting. They consider three classes of protocols for PSI
based on Yas’s garbled circuit technique which takes
any boolean circuit C and yields a secure protocol for
computing C. The main idea of the third is that each
set is sorted locally and then obliviously merged into a
single sorted list. Then each adjacent pair is compared
and if the elements are equal, one of them is kept, and
if not, the pair is replaced by a random value. The
resulting list must be shuffled for not leaking any in-
formation. They concluded that protocols based on
generic secure computation ”can offer performance
that is competitive with the best known custom proto-
cols”.
3.3 Oblivious Transfer-based PSI
Oblivious Transfer. protocol is a type of protocol
in which a sender transfers one of potentially many
pieces of information to a receiver, but remains obliv-
ious as to what piece has been transferred.
In 2004 Freedman, Nissim and Pinkas (Freed-
man et al., 2004) were the first to introduce the con-
cept of private set intersection solved using protocols
based on oblivious polynomial evaluation that acts as
a client-server communication where only the client
learns the output. They obtain O(k) communica-
tion overhead and O(k ln ln k) computation for lists of
length k. The protocol works as follows: C uses inter-
polation to generate the polynomial P(y) =
∑
k
c
u=0
α
u
y
u
of degree k
c
with roots {x
1
, x
2
, ..., x
k
c
} (his input).
C encrypts the coefficients and sends them to S.
∀y ∈ Y , S computes Enc(P(y)) using the homomor-
phic properties to evaluate the polynomial. Then, he
chooses a random r and computes Enc(rP(y) + y).
Finally, he sends all the k
s
ciphertexts permuted back
to the client. C decrypts all k
s
values and outputs the
set intersection.
Freedman et al. (Freedman et al., 2016) tried to
hit it big again in 2016. They proposed two proto-
cols based on the use of homomorphic encryption.
They obtain linear communication and computation
overhead using both Paillier and ElGamal encryption
schemes. They implement the protocols and analyse
with different constants.
In contrast to previous protocols that used secure
polynomial evaluation, Hazay and Lindell (Hazay and
Lindell, 2008) came with a different approach in deal-
ing with secure set intersection problem. They pro-
posed the first protocols based on secure pseudoran-
dom function evaluation. Their work was continued
and improved by Jarecki and Liu in (Jarecki and Liu,
2009). However, the input domain of the PRF is re-
stricted to polynomial size.
Chase and Miao in (Chase and Miao, 2020) make
a positive progress on finding a new PSI protocol
that achieves better communication and computation
trade-offs. Their protocol is based on oblivious trans-
fer, hashing, symmetric-key and bitwise operations.
Their protocol achieves security in the random oracle
model when the B party (the sender who gets nothing
for output) is malicious.
Their PSI protocol’s most important part is a new
multi-point oblivious pseudorandom function proto-
col that is based on oblivious transfer and relies on
symmetric-key, bitwise operations and hashing. The
idea of the protocol is simple: since they can achieve
multi-point OPRF while the second party has mul-
tiple elements as input and his output consists on all
the elements evaluated then the set intersection can be
easily computed in a private manner. The first party
evaluates the PRF on every element in his set and
send all the PRF values to the second party and by
comparison these PRF values, he figures out the in-
tersection of the two sets.
Ruan and Mao (Ruan and Mao, 2020) propose a
new approach to PSI protocol, transforming the prob-
lem of the intersection of sets into the problem of find-
ing roots of polynomials by using point-value poly-
nomial representation. Their protocol stands out be-
cause of the lack of using a cryptosystem.
In this article, the authors represent the sets as
polynomials’ point-value pairs as follows: each party
denotes n elements (s
1
, ..., s
n
) as a n-degree polyno-
mial p(x) =
∏
n
i=1
(x − s
i
). They agree on a list of
d elements {x
1
, ..., x
d
} and evaluate their polynomi-
als on these numerical values, making point-value
pairs {(x
1
, p(x
1
)), ..., x
d
, p(x
d
))}. Because n ≤ d + 1,
the point-value pairs can be seen as a representation
of each polynomial. Next they blind their polyno-
mials by using pseudorandom function {(x
1
, p(x
1
) +
z
1
), ..., (x
d
, p(x
d
) + z
d
)} and exchange the blinded
point-value pairs. The polynomial can be found by
interpolation and the intersection by computing the
SECRYPT 2021 - 18th International Conference on Security and Cryptography
682
roots of the polynomial.
In (Kolesnikov et al., 2016) there is presented the
fastest protocol in the semi-honest environment. In
short, in this protocol A can learn only one output of
each PRF function F
i
, while B can learn any output
he wants. Next A hashes his elements using Cuckoo
Hashing, so he has two possible hash functions to use
but chooses only one. On the other hand, B sends both
of the hash functions used on his elements to encom-
pass both possibilities of A.
The protocol in (Pinkas et al., 2020) uses the same
conceptual setup as the semi-honest protocol from
(Kolesnikov et al., 2016). Instead of placing each item
into one bin or the other, A will secret share that item
between the two bins. An item a = s
1
⊕ s
2
is associ-
ated with PRF outputs F
1
(s
1
) and F
2
(s
2
) and if these
PRF outputs are XOR-ed together it will get the re-
sult F
12
(a). B can compute the function F
12
on any
element he wants so he simply computes the function
computed by the associated elements of his input on
his elements and send them to A.
4 OUR PROPOSALS FOR PSI
In this chapter we are going to present some ideas
that can be starting points for further PSI protocols.
On our best knowledge, these ideas are not presented
in the existing literature. In the following proto-
cols, A
0
s input is S = {a
1
, a
2
, ..., a
v
} and B
0
s input is
C = {b
1
, b
2
, ..., b
w
}.
4.1 Bilinear Maps Approach
For this construction idea we consider the following:
1. G
1
and G
2
are two (multiplicative) cyclic groups of
prime order p; 2. g
1
is a generator of G
1
and g
2
is a
generator of G
2
; 3. ψ is a computable isomorphism
from G
1
to G
2
, with ψ(g
1
) = g
2
; 4. e is a computable
bilinear map e : G
1
× G
2
→ G
T
as described below.
A bilinear map is a map e : G
1
× G
2
→ G
T
with
the following properties: 1. For all u ∈ G
1
, v ∈ G
2
and a, b ∈ Z, e(u
a
, v
b
) = e(u, v)
ab
. This property is
called bilinearity. 2. e(g
1
, g
2
) 6= 1; This property is
called non − degenerate. Further we will present the
PSI protocol:
A generates a secret parameter s
1
and public pa-
rameters p
1
, g
s
1
and B generates a secret parameter
s
2
and a public parameter p
2
. B computes g
s
2
p
2
b
j
for
every j = 1, 2, ..., w .
To make the intersection, B must find g
s
1
p
1
s
2
p
2
T
and
verify if
e(g
a
i
s
1
p
1
, g
s
2
p
2
b
j
) = g
s
1
p
1
s
2
p
2
T
. (1)
g
s
1
p
1
s
2
p
2
T
can be computed in the following way:
e(g
s
1
, g
p
1
s
2
p
2
)=g
s
1
p
1
s
2
p
2
T
.
Correctness. is assured by the bilinear maps proper-
ties. More exactly, the bilinearity property e(g
a
, g
b
) =
e(g, g)
ab
. We denote e(g, g) as g
T
. When B re-
ceives
−→
X from A, he computes e(X
i
, g
s
2
p
2
b
j
) and ver-
ifies if the answer is g
s
1
p
1
s
2
p
2
T
. In a more detailed
way he computes e(X
i
, g
s
2
p
2
b
j
) = e(g
a
i
s
1
p
1
, g
s
2
p
2
b
j
) =
e(g, g)
a
i
s
1
p
1
s
2
p
2
b
j
. If a
i
and b
j
are the same, so they
are part of the intersection, b
j
is simplified by a
i
and
results exactly e(g, g)
s
1
p
1
s
2
p
2
which is g
s
1
p
1
s
2
p
2
T
.
Security. In terms of security, this protocol has an ex-
clusion issue, meaning that an attacker can determine
for sure if an element z is not in A’s set by checking
for i ∈ {1, ..., v} if e(X
i
, g
s
2
p
2
z
) is g
s
1
p
1
s
2
p
2
T
. This is-
sue is dangerous especially when the set’s domain is
small.
Efficiency. In terms of communication, there is trans-
ferred a vector of v elements from A to B. In terms of
computational complexity, in the worst case, there are
made w verification for each of the v elements from
the vector, leading to O(v · w). This idea is expensive
because of the use of the not so light bilinear maps
but if a faster and lighter bilinear map variant would
be found, this proposal could materialize.
4.2 Secret Sharing Approach
Secret sharing refers to methods for distributing a se-
cret among a group of participants, each of whom is
allocated a share of the secret. The secret can be re-
constructed only when a sufficient number of shares
are combined together; individual shares are of no use
on their own.
Take into consideration that Enc is a homomor-
phic encryption scheme.
A constructs a secret sec starting from the subse-
crets {a
1
, ..., a
v
} (his input) with threshold v. Then
he encrypts his input with a homomorphic encryption
scheme to allow further operations over cryptotext. A
sends to B the encryptions of his input along with sec.
In this moment B has A’s elements encrypted, sec
beside his input. B encrypts his elements and tries to
find the intersection. B remove one element from A’s
set at a time and replaces it with each of his element
to see if he can find the same secret as sec. If he does,
the element that he put for the replacement is part of
the intersection.
This sketch has many issues. Firstly there must be
found a secret sharing scheme that does not take into
consideration the order of the elements. The known
secret sharing schemes take into consideration the or-
der of the subsecrets in founding the secret. Secondly,
Private Set Intersection: Past, Present and Future
683
B has to perform v×w encryption to find the intersec-
tion, which is far away from the best time achieved
by speciality literature for PSI computation. How-
ever, this idea is an interesting starting point, thinking
about how cloud computing is more and more popular
every day.
Correctness. is ensured by the fact that the secret
sec can be exclusively reconstituted by all v elements
from A’s set. Considering that the threshold is v, sec
cannot be reconstituted with less than v or with other
elements than A’s elements. When B replaces succes-
sively one element and replaces it with each of his el-
ements, he can recover the secret sec if and only if the
element replaced is the same with the replacement, so
it is part of the intersection.
Security. A security issue is that an adversary can
check is one element is not part of the A’s set by re-
placing successively each element with x. Also, the
elements are send encrypted with a homomorphic en-
cryption scheme and because of that an attacker can
verify if an element that he encrypts with the same
homomorphic encryption scheme is part of A’s set.
Efficiency. In terms of communication complexity,
there are send only the secret sec and a vector with the
encryptions of A. To find the intersection, the compu-
tational complexity is O(v · w) because for each ele-
ment from the A’s set, B takes each of its elements
and verifies if is in the intersection.
4.3 Modular Inverse Approach
A modular multiplicative inverse of an integer a is an
integer x such that the product ax is congruent to 1
with respect to the modulus m. More formally,
ax ≡ 1 mod m.
Our idea of PSI protocol that uses modular inverse in
presented below: A generates randomly a and sends it
to B. For every b
i
, B finds x
i
such that
ax
i
≡ 1 mod b
i
.
B sends
−→
x to A. Once received the vector
−→
x , A
finds the intersection by multiplying a with each x
i
,
i ∈ {1, ..., w} at a time and see if there exists a
j
,
j ∈ {1, ..., v} such that ax
i
≡ 1 mod a
j
. If exists, the
element a
j
is in the intersection.
Correctness. Finding a modular inverse does not give
a unique answer if the modulo is not prime. Because
the modulo is himself the secret, it is hard to force
it to be prime, so the correctness is hard to obtain.
However a solution would be for A to send a vector of
elements to B to find the modular inverse of those.
Security. A security issue consists in the fact that the
protocol can be attacked by a man in the middle. An
observer can obtain precious information about B’s
set by knowing a and
−→
x . The attacker can find that
elements of B are divisible by ax
i
− 1 and if B has
prime elements, the malicious one can find exactly its
elements. Also, the information found by the man in
the middle can be found also by A. As well, on suc-
cessive run of the protocol, the man in the middle and
A can find B’s secrets with high probability or at least
a divisor of the secret. (By making gcd of (ax
i
, a
0
x
0
j
).)
Efficiency. The communication complexity is O(w)
because of the send of vector
−→
x . In terms of compu-
tational complexity, B performs w findings of modu-
lar inverse and A makes v · w multiplications to find
the intersection.
4.4 Symmetric Encryption Approach
A generates a random value r and v random values
r
i
and computes c
i
= Enc
a
i
+r
(a
i
||r
i
||len(r
i
)) for each
i ∈ {1, ..., v} then sends the encryptions (vector
−→
c )
along with r to B.
B tries to decrypt each encryption received from
A using the key b
j
+ r, for every j ∈ {1, ..., w}.
If Dec
b
j
+r
(c
i
) is b
j
||random||l where random is of
length l for one j ∈ {1, 2, .., w} and i ∈ {1, 2, ..., v}
then b
j
is an element from the intersection.
4.4.1 Security Proof
We cannot prevent the server to send false data.
Let C, S be two sets from a predefined universe, f
∩
be the set intersection function defined as:
f
∩
(C, S) = ( f
C
(C, S), f
S
(C, S)) = (C ∩ S, ∧).
The correctness of the algorithm refers to the fact that
the intersection output is the correct one. Intuitively,
the intersection correctness in the proposed protocol
comes from the fact that we add at the end of each se-
cret (elements from the set) a random number and the
length of the random number. In this way, after de-
crypting with the correct key, it is very precise where
the secret ends, by eliminating the random number
and its length. So, for each element of A we can ver-
ify with maximum precision if it is also in B’s set.
Theorem 1. If Enc is a symmetric encryption algo-
rithm and Dec is it inverse, a symmetric decryption
algorithm, then the protocol securely realizes f
∩
(C, S)
in the semihonest model.
Proof. To prove 1 we will give the construction of
two simulators Sim
A
and Sim
B
to simulate the view
of each of the two parties. We want to show that
the simulator’s view is indistinguishable from the
real world’s protocol’s view. Indistinguishability is a
SECRYPT 2021 - 18th International Conference on Security and Cryptography
684
property that means an adversary is unable to distin-
guish pairs of ciphertexts based on the message they
encrypt.
Simulator of A.
1. Sim
A
is given the input of A: S = {a
1
, ..., a
v
}. Be-
cause A does not get any input from the protocol,
neither is Sim
A
;
2. Sim
A
generates random r ←
rand
{0, 1}
∗
;
3. For every i ∈ {1, ..., v}, Sim
A
generate a random
r
i
←
rand
{0, 1}
∗
;
4. Instead of encrypting the input he was given, he
randomly generates c
i
and sends the vector
−→
c to
B.
Simulator of B.
1. Sim
B
is given the input of B: C = {a
1
, ..., a
v
} and
its output formed by the intersection f
∩
(C, S).
2. Sim
B
generates random what he should have re-
ceived from A: c
i
←
rand
{0, 1}
∗
for every i ∈
{1, ..., v}.
This property is achieved by having a different ran-
dom for each secret, so the cyphertext is always dif-
ferent. Two secrets can have the same cyphertext with
the probability of random generator giving the same
number.
Unlinkability is also achieved by randomness.
Taking into consideration that every time there is a
new random generated, two actions are hard to be
linked.
Efficiency. The communication complexity is O(v)
because A sends to B the vector
−→
c . For each element
from
−→
c , B tries to decrypt with each of its keys. This
lead to computational complexity of O(v · w).
5 CONCLUSIONS
In this overview, we presented the main aspects of pri-
vate set intersection along with existing protocols. In
the end we propose four new directions in terms of
PSI that are not yet efficient but can be starting points
for future protocols. The most promising is the pro-
posal that makes use of symmetric encryption and we
wish to improve its general efficiency in future. For
the approach that uses secret sharing, in our future
work we wish to find a secret sharing scheme that
does not takes into consideration the order of the ele-
ments.
In conclusion PSI is still an object of great interest
in speciality literature because of its multiple usage
and our wish is to develop a protocol good in practice
for solving one of the biggest internet’s problems: the
privacy.
REFERENCES
Chase, M. and Miao, P. (2020). Private set intersection in
the internet setting from lightweight oblivious prf. In
CRYPTO, pages 34–63. Springer.
De Cristofaro, E. and Tsudik, G. (2010). Practical private
set intersection protocols with linear complexity. In
FC, pages 143–159. Springer.
Freedman, M. J., Hazay, C., Nissim, K., and Pinkas, B.
(2016). Efficient set intersection with simulation-
based security. Journal of Cryptology, 29(1):115–155.
Freedman, M. J., Nissim, K., and Pinkas, B. (2004). Effi-
cient private matching and set intersection. In Euro-
Crypt, pages 1–19. Springer.
Hazay, C. and Lindell, Y. (2008). Efficient protocols for
set intersection and pattern matching with security
against malicious and covert adversaries. In TCC,
pages 155–175. Springer.
Huang, Y., Evans, D., and Katz, J. (2012). Private set inter-
section: Are garbled circuits better than custom pro-
tocols? In NDSS.
Jarecki, S. and Liu, X. (2009). Efficient oblivious pseudo-
random function with applications to adaptive ot and
secure computation of set intersection. In TCC, pages
577–594. Springer.
Kolesnikov, V., Kumaresan, R., Rosulek, M., and Trieu, N.
(2016). Efficient batched oblivious prf with appli-
cations to private set intersection. In Proceedings of
the 2016 ACM SIGSAC Conference on Computer and
Communications Security, pages 818–829.
Meadows, C. (1986). A more efficient cryptographic match-
making protocol for use in the absence of a continu-
ously available third party. In 1986 IEEE Symposium
on Security and Privacy, pages 134–134. IEEE.
Ogata, W. and Kurosawa, K. (2004). Oblivious keyword
search. Journal of complexity, 20(2-3):356–371.
Pagh, R. and Rodler, F. F. (2004). Cuckoo hashing. Journal
of Algorithms, 51(2):122–144.
Pinkas, B., Rosulek, M., Trieu, N., and Yanai, A. (2020).
Psi from paxos: fast, malicious private set intersec-
tion. In EuroCrypt, pages 739–767. Springer.
Pinkas, B., Schneider, T., and Zohner, M. (2014). Faster
private set intersection based on {OT} extension. In
{USENIX} Security 14, pages 797–812.
Ruan, O. and Mao, H. (2020). Efficient private set inter-
section using point-value polynomial representation.
Security and Communication Networks, 2020.
Private Set Intersection: Past, Present and Future
685
