Paper 2021/484

Efficient Scalable Multi-Party Private Set Intersection Using Oblivious PRF

Alireza Kavousi, Javad Mohajeri, and Mahmoud Salmasizadeh

Abstract

In this paper, we present a concretely efficient protocol for private set intersection (PSI) in the multi-party setting using oblivious pseudorandom function (OPRF). In fact, we generalize the approach used in the work of Chase and Miao [CRYPTO 2020] towards deploying a lightweight multi-point OPRF construction for two-party PSI. Our protocol only includes oblivious transfer (OT) extension and garbled Bloom filter as its main ingredients and avoids computationally expensive operations. From a communication pattern perspective, the protocol consists of two types of interactions. The first type is performed over a star-like communication graph in which one designated party interacts with all other parties via performing OTs as the sender. Besides, parties communicate through a path-like communication graph that involves sending a garbled Bloom filter from the first party to its neighboring party following the last one. This design makes our protocol to be highly scalable due to the independence of each party's complexity from the number of participating parties and thus causes a communication and computation complexities of $O(n\lambda k)$, where $n$ is the set size, $k$ is the number of hash functions, and $\lambda$ is the security parameter. Moreover, the asymptotic complexity of the designated party is $O(tn\lambda)$ which linearly scales with the number of parties $t$. We prove security of the proposed protocol against semi-honest adversaries.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. The 17th International Workshop on Security and Trust Management (STM 2021)
Keywords
Secure Multi-Party ComputationPrivate Set IntersectionOblivious Pseudorandom FunctionConcrete Efficiency
Contact author(s)
a kavousi95 @ gmail com
History
2021-08-29: last of 3 revisions
2021-04-16: received
See all versions
Short URL
https://ia.cr/2021/484
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/484,
      author = {Alireza Kavousi and Javad Mohajeri and Mahmoud Salmasizadeh},
      title = {Efficient Scalable Multi-Party Private Set Intersection Using Oblivious {PRF}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/484},
      year = {2021},
      url = {https://eprint.iacr.org/2021/484}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.