Paper 2022/338

Communication-Efficient Inner Product Private Join and Compute with Cardinality

Koji Chida, Gunma University
Koki Hamada, NTT Social Informatics Laboratories
Atsunori Ichikawa, NTT Social Informatics Laboratories
Masanobu Kii, NTT Social Informatics Laboratories
Junichi Tomida, NTT Social Informatics Laboratories
Abstract

Private join and compute (PJC) is a paradigm where two parties owing their private database securely join their databases and compute a function over the combined database. Inner product PJC, introduced by Lepoint et al. (Asiacrypt'21), is a class of PJC that has a wide range of applications such as secure analysis of advertising campaigns. In this computation, two parties, each of which has a set of identifier-value pairs, compute the inner product of the values after the (inner) join of their databases with respect to the identifiers. They proposed inner product PJC protocols that are specialized for the unbalanced setting where the input sizes of both parties are significantly different and not suitable for the balanced setting where the sizes of two inputs are relatively close. We propose an inner product PJC protocol that is much more efficient than that by Lepoint et al. for balanced inputs in the setting where both parties are allowed to learn the intersection size additionally. Our protocol can be seen as an extension of the private intersection-sum protocol based on the decisional Diffie-Hellman assumption by Ion et al. (EuroS&P'20) and is especially communication-efficient as the private intersection-sum protocol. In the case where both input sizes are $2^{16}$, the communication cost of our inner-product PJC protocol is $46\times$ less than that of the inner product PJC protocol by Lepoint et al.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. AsiaCCS 2023
Keywords
private set intersectionprivate intersection-sumtwo-party computationsecure computationprivate join
Contact author(s)
chida @ gunma-u ac jp
koki hamada rb @ hco ntt co jp
atsunori ichikawa nf @ hco ntt co jp
masanobu kii gw @ hco ntt co jp
junichi tomida vw @ hco ntt co jp
History
2023-11-09: last of 3 revisions
2022-03-14: received
See all versions
Short URL
https://ia.cr/2022/338
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/338,
      author = {Koji Chida and Koki Hamada and Atsunori Ichikawa and Masanobu Kii and Junichi Tomida},
      title = {Communication-Efficient Inner Product Private Join and Compute with Cardinality},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/338},
      year = {2022},
      url = {https://eprint.iacr.org/2022/338}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.