Three-Party Private Set Operation Protocols Using Polynomials and OPPRF
- W. Wang, Y. Abe, M. Iwamoto, and K. Ohta
- Symposium on Cryptography and Information Security, (SCIS2019)
A Private Set Operation (PSO) protocol is a secure multi-party computation protocol (MPC) that allows participants to know the result of set operations (union, intersection, difference etc.) of their inputs but learn nothing else. Although PSO protocols have many applications, previous work on PSO protocols mainly focused on the Private Set Intersection (PSI) protocols. One exception would be the work by Blanton and Aguiar, which is inefficient since it consists of consecutive PSO protocols for two sets. On the other hand, a PSI protocol based on polynomials is known to be efficient due to the homomorphic encryption for two parties. However, the computation cost becomes heavier if it is extended for three parties due to the cost of homomorphic encryption. In this work, we propose a new PSO protocol for three parties by combining polynomials with the Oblivious Programmable PRF (OPPRF) proposed by Kolesnikov et al. The proposed scheme is efficient even if three-party cases since OPPRF is constructed by a symmetric key encryption combining with polynomials.