Welcome to the resource topic for 2016/665
Breaking and Fixing Private Set Intersection Protocols
Authors: Mikkel LambækAbstract:
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.
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .