Research On Key Technology Of Secure Two-party Computation And Its Applications

In the era of big data nowadays, data analysis and mining has become a necessary technical means to extract useful information from a mass of data. However, there exists one obstacle at present that the data analyzer could not fully own the data, even do not hold the data in his hands. Besides, it will bring unpredictable damage to disclose one’s private information to the untrusted third party, and analyze the centralized data sets and apply data mining by a third party. This will greatly reduce the possibility of coop-eration computing. Fortunately, the emergence of secure multiparty computing (SMC) technology makes possible bridging these seemingly contradictory facts. It aims at al-lowing that under the premise of not divulging private information, various participants of mistrust can complete analysis and mining of the whole dataset through cooperative computing, in order to obtain more accurate results, achieving the win-win situation. Secure two-party computation is the core content in the field of secure computing. It not only can be directly applied to real life, but also the basis of building secure multi-party protocol. However, so far, a lot of key problems in the secure two-party compu-tation have not been resolved well, which directly leads to the difficulties that a lot of data analysis algorithms cannot achieve the goal of privacy. This paper focuses on the in-depth study on issues of querying kth smallest value, deriving three basic theoretical issues. Combined with solutions of theoretical problems, we have implemented three practical and available privacy protection systems. The main innovations of this paper are listed below:1. Based on the core issue of secure k-th smallest element query, we derive three fun-damental issues, namely secure static k-nearest neighbor query, secure dynamic k-nearest neighbor query, and secure McAfee selection, and give form definitions to these problems.2. Based on the solution for secure static k-Nearest Neighbors query, we design a complete privacy-preserving collaborative Web services quality of service(QoS) prediction framework to bridge the gap between personalization and privacy. The prediction accuracy is guaranteed by Zheng’s approach, while the accom-panied complex nonlinear computations are addressed efficiently by the delicate combination of Yao’s garbled circuit and additively homomorphic encryption. The privacy-preserving collaborative QoS prediction framework is implemented based on an open source framework FasterGC. We adopt in FasterGC to real-ize various optimization in QoS prediction, thus making privacy-preserving QoS prediction not only theoretical interesting but also practical in real applications. 3. We design a secure selection algorithm which can select the share of k-th smallest element in vertically partitioned vector with O (n) communication cost. By using a shuffle protocol to disturb shared information, we guarantee that both partici-pants can only obtain garbled information of the k-NN set to avoid information leakage. We design protocol for k-distance calculation, and provide effective so-lution to search shares of k-distance for each point o∈Nk(p). This kind of problem is the core issue of secure dynamic k-Nearest neighbor query, and has no effective solution so far. We prove that our protocol is universal composable secure under semi-honest model. We also show that, given a dataset O of size n, the communication and computation costs of the protocol are both O (n2), which is acceptable as the original computational complexity of LOF is O(n2) and the communication complexity of distributed LOF without privacy is O(n).4. We design an efficient solution for secure McAfee’s selection based on Yao’s garbled circuits and Batcher’s sorting network. The main cost of this solution is O(nlog2n) symmetric encryption operations and is quite efficient when the number of bidders is relative small. For the large number of bidders, we give a more efficient solution for secure McAfee’s selection based on secure shuffling and secure selection, where the main cost is O(n) symmetric encryption opera-tions. We design secure protocols for McAfee’s auction mechanism and TRUST based on the solutions for secure McAfee’s selection. We apply the definition of security against semi-honest adversaries to formally prove the security of the pro-posed protocols and analyze their computation and communication complexities. Moreover, we implement our approach on top of FasterGC to evaluate running time and message volumes.