Efficient VOLE based Multi-Party PSI with Lower Communication Cost

Shuqing Zhang

Paper 2023/1690

Efficient VOLE based Multi-Party PSI with Lower Communication Cost

Shuqing Zhang, Academy of Mathematics and Systems Science, Chinese Academy of Sciences

Abstract

We present a new method for doing multi-party private set intersection against a malicious adversary, which reduces the total communication cost to $O (n l κ)$ . Additionally, our method can also be used to build a multi-party Circuit-PSI without payload. Our protocol is based on Vector-OLE(VOLE) and oblivious key-value store(OKVS). To meet the requirements of the protocol, we first promote the definition of VOLE to a multi-party version. After that, we use the new primitive to construct our protocol and prove that it can tolerate all-but-two malicious corruptions. Our protocol follows the idea of [RS21], where each party encodes the respective set as a vector, uses VOLE to encrypt the vector, and finally construct an OPRF to get the result. When it comes to multi-party situation, we have to encrypt several vectors at one time. As a result, the VOLE used in [RS21] and follow-up papers is not enough, that brings our idea of an multi-party VOLE.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: VOLE OKVS Multi-Party PSI
Contact author(s): zhangshuqing17 @ mails ucas ac cn
History: 2023-11-03: approved; 2023-11-01: received; See all versions
Short URL: https://ia.cr/2023/1690
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1690,
      author = {Shuqing Zhang},
      title = {Efficient {VOLE} based Multi-Party {PSI} with Lower Communication Cost},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1690},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1690}
}