Paper 2020/825

Private Set Intersection from TFHE for Cloud Computing Scenarios

Jiayu Qiang and Yi Deng

Abstract

In most scenarios of Private Set Intersection (PSI) computed on a cloud server, the client has a smaller set size and lower computation ability than that of the cloud server, which is known as the unbalanced setting. We use Torus Fully Homomorphic Encryption (TFHE) for the first time instead of the leveled ones to construct a PSI protocol. More precisely, we mainly focus on an adaptive and dynamic setting since the server may provide services to multiple clients at the same time and its data set is updated in real time. We use TFHE to construct an adaptive PSI for unbounded items with a lower communication complexity of $O(|Y|)$ than [19](CCS17), where $Y$ is the length of client's sets) . TFHE support arbitrary depth of homomorphic operations, which avoids those optimizations[19]made to reduce the depth of the circuit, resulting in additional computation and communication complexity. We propose a basic protocol that can efficiently compute the intersection with small items and then we apply a partition technique to our full protocol in order to support unbounded items. We also achieve a flexible dynamic protocol by adjusting our parameters into an adaptive setting, which can further reduce the communication cost of our PSI protocol, especially in cloud computing scenarios mentioned above.