Paper 2023/986
Efficient Private Multiset ID Protocols
Abstract
Private-ID (PID) protocol enables two parties, each holding a private set of items, to privately compute a set of random universal identifiers (UID) corresponding to the records in the union of their sets, where each party additionally learns which UIDs correspond to which items in its set but not if they belong to the intersection or not. PID is very useful in the privacy computation of databases query, e.g. inner join and join for compute. Known PID protocols all assume the input of both parties is a set. In the case of join, a more common scenario is that one party's primary key (unique) needs to join the other party's foreign key (duplicate). How to construct an efficient Private Multiset ID (PMID) protocol to support the above \emph{key-foreign key join} remains open. We resolve this problem by constructing efficient PMID protocols from Oblivious PRF, Private Set Union, and a newly introduced primitive called Deterministic-Value Oblivious Programmable PRF (dv-OPPRF). We also propose some PMID applications, including Private Inner Join, Private Full Join, and Private Join for Compute. We implement our PMID protocols and state-of-the-art PID protocols as performance baselines. The experiments show that the performances of our PMID are almost the same as the state-of-the-art PIDs when we set the multiplicity $U_x = U_y = 1$. Our PMID protocols scale well when either $U_x > 1$ or $U_y > 1$. The performances also correctly reflect excessive data expansion when both $U_x, U_y > 1$ for the more general \emph{cross join} case.
Note: This is the full version of a paper to be published in ICICS 2023.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. ICICS 2023
- Keywords
- Private IDPrivate Join for Compute
- Contact author(s)
-
zhangcong @ iie ac cn
weiran lwr @ alibaba-inc com
bolin ding @ alibaba-inc com
ddlin @ iie ac cn - History
- 2023-06-26: approved
- 2023-06-24: received
- See all versions
- Short URL
- https://ia.cr/2023/986
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/986,
author = {Cong Zhang and Weiran Liu and Bolin Ding and Dongdai Lin},
title = {Efficient Private Multiset ID Protocols},
howpublished = {Cryptology ePrint Archive, Paper 2023/986},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/986}},
url = {https://eprint.iacr.org/2023/986}
}
