Cryptology ePrint Archive: Report 2022/338

Private Intersection-Weighted-Sum

Koji Chida and Koki Hamada and Atsunori Ichikawa and Masanobu Kii and Junichi Tomida

Abstract: We propose secure two-party computation for a new functionality that we call Private Intersection-Weighted-Sum (PIW-Sum) and present an efficient semi-honestly secure protocol. In this computation, two parties own integer matrices $\mathbf{X}$ and $\mathbf{Y}$, respectively, where each row of the matrices is associated with an identifier. Let $I=(i_{1} ,..., i_{n})$ be the intersection of the identifier sets for the two parties. The goal is to compute the matrix $\widehat{\mathbf{Y}}^{\top}\widehat{\mathbf{X}}$ together with the cardinality $|I|$, where the $j$-th rows of $\widehat{\mathbf{X}}$ and $\widehat{\mathbf{Y}}$ are the rows of $\mathbf{X}$ and $\mathbf{Y}$ with identifier $i_{j}$, respectively. This functionality is a generalization of Private Intersection-Sum (PI-Sum) proposed by Ion et al.~(EuroS\&P'20) and has important real-world applications such as computing a cross tabulation after the equijoin of two tables owned by different parties.

Our protocol is built on a new variant of oblivious pseudorandom function (OPRF), and we construct the new variant of OPRF from the decisional Diffie-Hellman (DDH) assumption. We implement both our PIW-Sum protocol and the the most efficient PI-Sum protocol by Ion et al.~and compare their performance in the same environment. This shows that both communication cost and computational cost of our protocol are only about 2 times greater than those of the PI-Sum protocol in the case where $\mathbf{X}$ and $\mathbf{Y}$ are column vectors, i.e., the number of columns of $\mathbf{X}$ and $\mathbf{Y}$ is one.

Category / Keywords: cryptographic protocols / private set intersection, private intersection-sum, private intersection-weighted-sum, two-party computation, secure computation

Date: received 11 Mar 2022, last revised 11 Mar 2022

Contact author: junichi tomida vw at hco ntt co jp

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2022/338

[ Cryptology ePrint archive ]