Paper 2021/1440

Improved Circuit-based PSI via Equality Preserving Compression

Kyoohyung Han, Dukjae Moon, and Yongha Son


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 speed-up for circuit-PSI protocols over moderate to high bandwidth (over $100$Mbps), which is up to $1.7$x around $500$Mbps.

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
Private Set IntersectionCircuit-based Private Set IntersectionHomomorphic Encryption
Contact author(s)
yongha son @ samsung com
2022-02-22: revised
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.