Optimized and Privacy-Preserving MAX/MIN Protocols for Large-Scale Data

In the era of big data, data is key to the accuracy of analytical models, and cloud computing services are often used to efficiently process large volumes of data. However, outsourcing sensitive data to a third-party cloud service provider results in a loss of direct control over the data, raising serious security concerns. The target of this study is to propose highly efficient and privacy-preserving protocols that compute the maximum/minimum value in large-scale data. To achieve the improvements in efficiency, the proposed protocols reuse the intermediate results generated in independent subprotocols. Existing privacy-preserving maximum/minimum protocols are based on approximation methods that sacrifice accuracy or reveal information during execution. They use costly comparison operations that are proportional to the size of the input data and are not suitable for large-scale data applications. In contrast, the proposed protocols theoretically reduce the number of communication rounds by 25%, the communication size by 50%, and the computational cost by 42% compared to the existing protocols. Nevertheless, the accuracy and privacy are fully maintained. In order to demonstrate these efficiency improvements concretely, we conducted experiments and demonstrated that the proposed protocols reduce the communication volume by half and the execution time by 22%. Because the proposed protocols support parallel execution, their performance can be substantially enhanced in cloud environments that provide large-scale parallel processing resources. Even data owners with restricted computational capabilities can use the protocols without exposing their information. Under the secure version, even cloud servers executing the protocol learn nothing about the input data or the computation results.