Implementing two Threshold Private Set Intersection Protocols based on Homomorphic Encryption

Abstract: Private set intersection is a technique for finding the intersection of (two) parties' sets without disclosing anything else, and it finds it use in e.g. contact discovery, finding friends who are already on a social platform. Multi-party threshold private set intersection is an extension of this which allows multiple parties and only reveals the intersection if the intersection is larger than a given threshold. Badrinarayanan, Miao and Rindal \cite{main} proposed three protocols for performing multi-party threshold private set intersection. Their proposals rely on homomorphic encryption and are the first solution to realize multi-party threshold private set intersection with communication complexity linear in threshold size, and thus sublinear in set size. In the this thesis, we investigate how to implement two of the three protocols in \cite{main} and their actual efficiency in practice. Our implementation is in the Go programming language and it is independent of the encryption schemes. Although our implementation is meant to run on a single computer, it is possible to extend it to multiple computers in an easy way. In order to implement the protocols in \cite{main}, we present an algorithm for homomorphically finding the minimal polynomial of linearly recurrent sequences in this setting. This is to the best of our knowledge the first development of such an algorithm. In addition we also implemented, and made publicly available, a Go library for performing basic matrix operations with elements being of any type, particularly useful for working with matrices homomorphically.