Paper 2022/713
More Efficient (Reusable) Private Set Union
, Bar-Ilan UniversityAbstract
We study the problem of private set union in the two-party setting, providing several new constructions. We consider the case where one party is designated to receive output. In the semi-honest setting, we provide two protocols. Our four-round protocol out-performs the state-ofthe-art in both communication and computation, and has a runtime that is 1.3X-2X faster than existing protocols. Our two-round protocol is only slightly more expensive, but it is still faster than existing protocols and has the property that the receiver message can be re-used across multiple executions. All our semi-honest protocols are post-quantum secure. In the setting where the sender is malicious, we provide the first protocols that avoid the use of expensive zero-knowledge proofs. We estimate (conservatively) that our constructions are less than 2X more expensive than the best known semi-honest constructions. As in the semi-honest setting, we describe two protocols: a faster one that requires four rounds of communication, and a slightly more expensive protocol that allows the receiver message to be re-used. Our work draws on several techniques from the literature on private set intersection, and helps clarify how these techniques generalize (and don’t generalize) to the problem of PSU.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Private Set Union Secure Two-Party Computation Reusability
- Contact author(s)
-
gordon @ gmu edu
carmit hazay @ biu ac il
ple13 @ gmu edu
mliang5 @ gmu edu - History
- 2022-06-06: revised
- 2022-06-04: received
- See all versions
- Short URL
- https://ia.cr/2022/713
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/713,
author = {Dov Gordon and Carmit Hazay and Phi Hung Le and Mingyu Liang},
title = {More Efficient (Reusable) Private Set Union},
howpublished = {Cryptology ePrint Archive, Paper 2022/713},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/713}},
url = {https://eprint.iacr.org/2022/713}
}
