Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Private Set Intersection, Circuit-based Private Set Intersection, Homomorphic Encryption

Date: received 26 Oct 2021

Contact author: yongha son at samsung com

Available format(s): PDF | BibTeX Citation

Version: 20211027:085112 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]