eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2016/665

Breaking and Fixing Private Set Intersection Protocols

Mikkel Lambæk


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
private set intersection
Contact author(s)
lambaek988 @ hotmail com
2016-07-01: received
Short URL
Creative Commons Attribution


      author = {Mikkel Lambæk},
      title = {Breaking and Fixing Private Set Intersection Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2016/665},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/665}},
      url = {https://eprint.iacr.org/2016/665}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.