Paper 2021/1440

Improved Circuit-based PSI via Equality Preserving Compression

Kyoohyung Han and Dukjae Moon and Yongha Son

Abstract

Circuit-based Private Set Intersection (circuit-PSI) enables two parties with input set $X$ and $Y$ to compute a function $f$ over the intersection set $X \cap Y$, without revealing any other information. State-of-the-art protocols for circuit-PSI commonly involves a procedure that securely checks whether two input strings are equal and outputs an additive share of the equality result. More importantly, this procedure occupies the largest portion, roughly $90\%$ computational or communication cost for circuit-PSI. In this work, we propose {\textit{equality preserving compression}} (EPC) protocol that compresses the length of equality check targets while preserving equality using homomorphic encryption (HE) scheme, which is secure against the semi-honest adversary. We then apply our EPC protocol to previous circuit-PSI protocols framework and implement them. As a result, we achieve around 2x improvement on both communication and computational cost {\emph{at one stroke}} than previous results.