Advanced

Implementing two Threshold Private Set Intersection Protocols based on Homomorphic Encryption

Jeppsson, Anton LU (2021) EITM01 20202
Department of Electrical and Information Technology
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
Jeppsson, Anton LU
supervisor
organization
course
EITM01 20202
year
type
H2 - Master's Degree (Two Years)
subject
keywords
Private Set Intersection, Homomorphic Encryption, Cryptology
report number
LU/LTH-EIT 2021-805
language
English
id
9040368
date added to LUP
2021-02-16 11:12:08
date last changed
2021-02-16 11:12:08
@misc{9040368,
  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.},
  author       = {Jeppsson, Anton},
  keyword      = {Private Set Intersection,Homomorphic Encryption,Cryptology},
  language     = {eng},
  note         = {Student Paper},
  title        = {Implementing two Threshold Private Set Intersection Protocols based on Homomorphic Encryption},
  year         = {2021},
}