Over-threshold multi-party private set operation protocols for lightweight clients

The problem of private set operation (PSO) can realize the function of data set analysis on the premise of privacy protection, which has been widely concerned by researchers in academia and industry. Over-threshold multi-party private set operation (OT-MP-PSO) is a special class of PSO, where multiple parties hold their own private set respectively and want to securely compute which element appears in at least t private sets of all parties for an adjustable threshold t. In practical scenarios, this primitive has many applications, such as voting systems and network operations centers collaborating to identify common threats. However, in current studies, the computational costs of existing protocols are exponentially related to the threshold t thus the range of t is limited to keep the protocols efficient. In this paper, we designed an efficient OT-MP-PSO protocol in a dual cloud setting and the range of t is not limited. In addition, we also design a series of private set fine-grained computation protocols that combine threshold, such as the cardinality of the result set and the sum of the element labels that satisfy the threshold condition. Moreover, we give formal security proofs for the proposed protocols and validate the efficiency of our protocols through experiments. On small data sets, our protocol has very little computational and communication overhead. When the set size ranges from 101 to 103, the experimental results show that our protocol is significantly better than the state-of-the-art approach. Finally, we introduce a typical application of our protocols in the field of voting.

Automated summary

The problem of private set operation (PSO) has attracted wide attention from researchers in academia and industry as it enables data set analysis while preserving privacy. Over-threshold multi-party private set operation (OT-MP-PSO), a special class of PSO, finds applications in various scenarios such as voting systems and network operations centers. However, existing protocols have exponential computational costs with respect to the threshold t, limiting the range of t for efficient protocols. In this paper, we propose an efficient OT-MP-PSO protocol in the dual cloud setting without any limitation on the range of t. We also design a series of private set fine-grained computation protocols incorporating threshold conditions. Formal security proofs are provided for these protocols, and experimental results demonstrate their efficiency. Our protocol shows significant improvement over the state-of-the-art approach when applied to small data sets ranging from 101 to 103. A typical voting application scenario is also introduced to showcase the practicality of our protocols.