Fast Secure Computation of Set Intersection

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

.