Paper 2016/665

Breaking and Fixing Private Set Intersection Protocols

Mikkel Lambæk

Abstract

A private set intersection protocol consists of two parties, a Sender and a Receiver, each with a secret input set. The protocol aims to have the Receiver output an intersection of the two sets while keeping the elements in the sets secret. This thesis thoroughly analyzes four recently published set intersection protocols, where it explains each protocol and checks whether it satisfies its corresponding security definition. The first two protocols [PSZ14, PSSZ15a] use random oblivious transfer where [PSSZ15a] is an optimized version of [PSZ14]. In the optimized protocol a correctness error is identified and prevented at a minor increase in run-time. An attempt to make [PSSZ15a] secure against a malicious adversary is shown, where the resulting protocol is proven secure against a semi-honest Sender and malicious Receiver. The third protocol [DCW13] is based on Bloom filters combined with oblivious transfer, and proposes protocols for two different security levels. The semi-honestly secure protocol satisfies its definition, while their proposal for a maliciously secure protocol is insufficient. This thesis shows two attacks a malicious Sender is capable of, without finding efficient countermeasures. The last protocol [DC16] allows computing four different set operations, where five errors are identified. Each error is explained and a proposal to avoid the issue is shown.

Note: This work is the Master's thesis of Mikkel Lambæk. It was developed at Aarhus University under the supervision of Claudio Orlandi.