Paper 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.