### Improved Circuit-based PSI via Equality Preserving Compression

Kyoohyung Han, 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. 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)
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
Private Set IntersectionCircuit-based Private Set IntersectionHomomorphic Encryption
Contact author(s)
yongha son @ samsung com
History
2022-02-22: revised
See all versions
Short URL
https://ia.cr/2021/1440

CC BY

BibTeX

@misc{cryptoeprint:2021/1440,
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{https://eprint.iacr.org/2021/1440}},
url = {https://eprint.iacr.org/2021/1440}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.