International Association
for Cryptologic Research

We present a new method for doing multi-party private set intersection against a malicious adversary, which reduces the total communication cost to $ O(nl\kappa) $. 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.