2010 | OriginalPaper | Chapter
Fast Secure Computation of Set Intersection
Authors : Stanisław Jarecki, Xiaomin Liu
Published in: Security and Cryptography for Networks
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A secure set intersection protocol between sender
S
and receiver
R
on respective inputs
X
and
Y
s.t. |
X
|,|
Y
| ≤
n
, allows
R
to learn
X
∩
Y
while
S
learns nothing about
R
’s inputs. In other words it is a secure computation of functionality
on sets of size at most
n
. A variant we call
adaptive
set intersection implements an interactive version of this functionality, which on senders
S
’s input
X
allows the receiver
R
to
adaptively
make up to
n
queries
y
i
and learn whether or not
y
i
∈
X
.
We show that a simple protocol using |
X
| + 4|
Y
| modular exponentiations and one round of interaction is a secure computation of the adaptive set intersection functionality against malicious adversaries in the Random Oracle Model (ROM) under a
One-More Gap Diffie-Hellman
(OMGDH) assumption, i.e. assuming the One-More Diffie-Hellman problem is hard even when the DDH problem is easy. Even though the protocol has only a single round, the corresponding ideal functionality is adaptive because receiver’s queries are efficiently extractable only eventually, rather than during protocol execution. However, under the OMGDH assumption in ROM the set of queries any efficient receiver can make is
committed
at the time of protocol execution, and hence no efficient adversary can benefit from the adaptive feature of this functionality.
Finally we show that this protocol easily extends to Set Intersection with Data Transfer, which is equivalent to the “Keyword Search” problem, where sender
S
associates each item xi in X with a data entry di, and
R
learns all (
x
i
,
d
i
) pairs such that
x
i
∈
Y
.