Low Communication-Cost PSI Protocol for Unbalanced Two-Party Private Sets
Two-party private set intersection (PSI) plays a pivotal role in secure two-party computation protocols. The communication cost in a PSI protocol is normally influenced by the sizes of the participating parties. However, for parties with unbalanced sets, the communication costs of existing protocols...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2024-01-01
|
| Series: | IET Information Security |
| Online Access: | http://dx.doi.org/10.1049/2024/6052651 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849686046254563328 |
|---|---|
| author | Jingyu Ning Zhenhua Tan Kaibing Zhang Weizhong Ye |
| author_facet | Jingyu Ning Zhenhua Tan Kaibing Zhang Weizhong Ye |
| author_sort | Jingyu Ning |
| collection | DOAJ |
| description | Two-party private set intersection (PSI) plays a pivotal role in secure two-party computation protocols. The communication cost in a PSI protocol is normally influenced by the sizes of the participating parties. However, for parties with unbalanced sets, the communication costs of existing protocols mainly depend on the size of the larger set, leading to high communication cost. In this paper, we propose a low communication-cost PSI protocol designed specifically for unbalanced two-party private sets, aiming to enhance the efficiency of communication. For each item in the smaller set, the receiver queries whether it belongs to the larger set, such that the communication cost depends solely on the smaller set. The queries are implemented by private information retrieval which is constructed with trapdoor hash function. Our investigation indicates that in each instance of invoking the trapdoor hash function, the receiver is required to transmit both a hash key and an encoding key to the sender, thus incurring significant communication cost. In order to address this concern, we propose the utilization of a seed hash key, a seed encoding key, and a Latin square. By employing these components, the sender can autonomously generate all the necessary hash keys and encoding keys, obviating the multiple transmissions of such keys. The proposed protocol is provably secure against a semihonest adversary under the Decisional Diffie–Hellman assumption. Through implementation demonstration, we showcase that when the sizes of the two sets are 28 and 214, the communication cost of our protocol is only 3.3% of the state-of-the-art protocol and under 100 Kbps bandwidth, we achieve 1.46x speedup compared to the state-of-the-art protocol. Our source code is available on GitHub: https://github.com/TAN-OpenLab/Unbanlanced-PSI. |
| format | Article |
| id | doaj-art-b91a8e950f3d49068d3525a9047b9ebd |
| institution | DOAJ |
| issn | 1751-8717 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | IET Information Security |
| spelling | doaj-art-b91a8e950f3d49068d3525a9047b9ebd2025-08-20T03:22:50ZengWileyIET Information Security1751-87172024-01-01202410.1049/2024/6052651Low Communication-Cost PSI Protocol for Unbalanced Two-Party Private SetsJingyu Ning0Zhenhua Tan1Kaibing Zhang2Weizhong Ye3Software CollegeSoftware CollegeSoftware CollegeSoftware CollegeTwo-party private set intersection (PSI) plays a pivotal role in secure two-party computation protocols. The communication cost in a PSI protocol is normally influenced by the sizes of the participating parties. However, for parties with unbalanced sets, the communication costs of existing protocols mainly depend on the size of the larger set, leading to high communication cost. In this paper, we propose a low communication-cost PSI protocol designed specifically for unbalanced two-party private sets, aiming to enhance the efficiency of communication. For each item in the smaller set, the receiver queries whether it belongs to the larger set, such that the communication cost depends solely on the smaller set. The queries are implemented by private information retrieval which is constructed with trapdoor hash function. Our investigation indicates that in each instance of invoking the trapdoor hash function, the receiver is required to transmit both a hash key and an encoding key to the sender, thus incurring significant communication cost. In order to address this concern, we propose the utilization of a seed hash key, a seed encoding key, and a Latin square. By employing these components, the sender can autonomously generate all the necessary hash keys and encoding keys, obviating the multiple transmissions of such keys. The proposed protocol is provably secure against a semihonest adversary under the Decisional Diffie–Hellman assumption. Through implementation demonstration, we showcase that when the sizes of the two sets are 28 and 214, the communication cost of our protocol is only 3.3% of the state-of-the-art protocol and under 100 Kbps bandwidth, we achieve 1.46x speedup compared to the state-of-the-art protocol. Our source code is available on GitHub: https://github.com/TAN-OpenLab/Unbanlanced-PSI.http://dx.doi.org/10.1049/2024/6052651 |
| spellingShingle | Jingyu Ning Zhenhua Tan Kaibing Zhang Weizhong Ye Low Communication-Cost PSI Protocol for Unbalanced Two-Party Private Sets IET Information Security |
| title | Low Communication-Cost PSI Protocol for Unbalanced Two-Party Private Sets |
| title_full | Low Communication-Cost PSI Protocol for Unbalanced Two-Party Private Sets |
| title_fullStr | Low Communication-Cost PSI Protocol for Unbalanced Two-Party Private Sets |
| title_full_unstemmed | Low Communication-Cost PSI Protocol for Unbalanced Two-Party Private Sets |
| title_short | Low Communication-Cost PSI Protocol for Unbalanced Two-Party Private Sets |
| title_sort | low communication cost psi protocol for unbalanced two party private sets |
| url | http://dx.doi.org/10.1049/2024/6052651 |
| work_keys_str_mv | AT jingyuning lowcommunicationcostpsiprotocolforunbalancedtwopartyprivatesets AT zhenhuatan lowcommunicationcostpsiprotocolforunbalancedtwopartyprivatesets AT kaibingzhang lowcommunicationcostpsiprotocolforunbalancedtwopartyprivatesets AT weizhongye lowcommunicationcostpsiprotocolforunbalancedtwopartyprivatesets |