Research On Private Data Protection And Its Applictions In Network Computing

In recent years, the development of networking increases the desirability of network-based cooperative computation, which is called network computing. But the data used in network computing are usually confidential or private, and the participants do not totally trust each other or even competitors. What they want is to get the final result of the computing without revealing any private input. In practice, this kind of situation in which the participants desire to do cooperative computing but don't trust each other is very common, so privacy concerns often prevent different parties from sharing their data which leads to the failure of cooperative computation. Secure multi-party computation (SMC), which was first proposed by A. C. Yao in in the eighties of the twentieth century and is attracting worldwide attention, aims at this problem and it ensures the correctness of the computation and that no more information is revealed to any participant in the computation than can be inferred from that participant's input and output. Yao, Goldreich, etc. proved that any SMC problem can be solved by circuit evaluation protocol. In the other hand, the situation when secure multi-party computation was attacked by malicious participants was researched by Ben-Or, Chaum, etc., and was solved using zero-knowledge proof.Because the inefficiency of the circuit evaluation, it is impractical to solve practical problem by this general theoretic solution. Goldreich, One of the precursors of SMC, pointed out that specific solutions should be developed for specific problems. Nowadays, SMC has been widely used in large numbers of areas, including data mining, computational geometry, private information retrieval (PIR), statistical analysis, etc. The design of SMC protocols usually bases on the basic protocols of SMC and the universal techniques, and the analysis of them usually bases on the theory of SMC. The improvement of SMC theory can be achieved by researchers, and the basic protocols and universal techniques can be presented and improved by researchers and engineers, and large numbers of practical application protocols can be designed by engineers. This kind of strategy decreases the difficulty of the design and analysis of SMC protocols.This dissertation first summarizes the achievement of previous researchers. We firstly introduce the background and the practical shortages of secure multi-party computation, and our work is to make up for these shortages. Chapter 2 introduces the common concepts and definitions of SMC, including the definition of security and behaviors of participants, etc., and oblivious transfer, zero knowledge proof systems, circuit evaluation protocol. Chapter 2 also discusses the basic protocols and common techniques widely used when designing SMC protocols.And then our work in SMC is presented in the following chapters, which can be divided into two parts: the achievement in SMC theory and the achievement in SMC applications.In Chapter 3, we focus on the achievement in SMC theory. It is well-known that in current literatures, SMC theory focuses on the perfect security, and pays little attention to the balance between efficiency and security. On the contrary, in many practical applications, the protocols' efficiency is critical, and it is also need not to be totally secure when the revealing information is not material. In this situation, how to balance efficiency and security is very important and more valuable than ensuring total security. In this dissertation, this problem is deeply discussed. We propose a series of definitions and concepts to describe and solve this problem. The important concepts include information-revealed quantity, restriction with partial order, and information freeness which is used to compare the security between SMC protocols. In the other hand, we also proposed a new universal technique named Add-Mul Transformation, which can be used to solve a lot of SMC problems.As for SMC applications, this dissertation concentrates on computational geometry (in Chapter 4 and Chapter 5) and clustering analysis (in Chapter 6).In Chapter 4, we give an efficient solution for millionaires' problem based on secure cross product protocol which demonstrates computational geometry is also a methodology to solve practical problems. We propose a universal solution for collision detection problem, and give a complete solution for collision detection of two moving circle using self-adpative technique and SMC. Also the complexity and security of the solution are analyzed. In Chapter 5, we discuss range searching problem. Range searching which is a very important problem in computational geometry, has widely application in practice. It can reture two kinds of result: the count in the neighborhood or the set of points in the neighborhood. We present two solutions for the first-class problem. The analysis shows that the first solution has perfect security but ralatively low efficiency, and the second solution has better efficiency at the cost of not total security. The second-class problem is much easier, and also be discussed briefly.We focus on DBSCAN clustering analysis in Chapter 6, and consider two cases: the data are partitioned vertically or horizontally into many parts, and the complexities and security of solutions are also discussed in detail.