Efficient Private Multiset ID Protocols

Cong Zhang; Weiran Liu; Bolin Ding; Dongdai Lin

Paper 2023/986

Efficient Private Multiset ID Protocols

Cong Zhang, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Weiran Liu, Alibaba Group (China)

Bolin Ding, Alibaba Group (China)

Dongdai Lin, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

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 ID Private 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},
      url = {https://eprint.iacr.org/2023/986}
}