Paper 2021/1440

Improved Circuit-based PSI via Equality Preserving Compression

Kyoohyung Han, Samsung SDS
Dukjae Moon, Samsung SDS
Yongha Son, Samsung SDS

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. This procedure is typically performed by generic two party computation protocols, and its cost occupies quite large portion of the total cost of 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. This can be seamlessly applied to state-of-the-art circuit-PSI protocol frameworks. We demonstrate by implementation that our EPC provides $10-40\%$ speed-up for circuit-PSI with set size from $2^{16}$ to $2^{20}$, on LAN network. We believe that EPC protocol itself can be independent interest, which can be applied to other application than PSI.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. SAC 2022
Private Set Intersection Circuit-based Private Set Intersection Homomorphic Encryption
Contact author(s)
kh89 han @ samsung com
dukjae moon @ samsung com
yongha son @ samsung com
2022-08-25: last of 2 revisions
2021-10-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kyoohyung Han and Dukjae Moon and Yongha Son},
      title = {Improved Circuit-based PSI via Equality Preserving Compression},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1440},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.