Research On Protecting And Utilizing Private Data In Cooperative Computation

As the development of web technology, cooperation between the web users becomes more and more popular. These users join together to exchange their private data in order to compute some composite functions. However, those who jointly compute the function may concern much about their own private data’s security, because these data can cause any trouble to them if divulged. Thus, to preserve cooperators’private data is a vital aspect in network based cooperation. To solve this problem, many researchers devote great effort in the privacy-preserving job during the cooperation. A.C.Yao is the first researcher to put forward a theory called Secure Multi-party Computation (SMC) in order to achieve the goal of protecting private data. And ever since then, SMC have being drawing great attention among the mass security researchers, and thus come out lots of valuable SMC theories as well as applications.SMC is a theory to protect private data of those users who jointly compute a composite function using their private inputs. It can make sure that the results are correct and the procedures are secure. If one SMC protocol can still protect the private data through some attackers with infinite computational ability, then we call it Secure in Theory. However, if one SMC protocol can only stay secure through some attackers with polynomial computational ability, then we call it Secure in Cryptography. A.C.Yao proposed a secure protocol to solve the Millionaire’s Problem using a cryptographic method. S.Goldwasser raised a theory called Zero Knowledge Proof (ZKP in short) Systems and simplified the model to be studied in SMC. We can just research the semi-honest model in SMC for simplicity. The SMC protocol in malicious model can be derived from the semi-honest model using the ZKP Systems. MO.Rabin proposed a very import protocol called Oblivious Transfer protocol in1981and was used to compose SMC protocol for the first time in1988by J.Kilian. O.Goldreich enlarged the scope of the usage of Yao’s theory from two-party to multi-party, and came up with another universal protocol to compute any functions securely in Cryptography. M.Ben-or then proposed a very important theoretical result which is almost the same as D.Chaum’s. It says in the model of Security in Theory, if the number of colluding attackers less than a half of the total attackers(t<n/2) in passive attack situation, or less than a third of the total number (t<n/3) in active attack situation, any function can be securely computed. Goldreich sums up most of the research achievements and forms the system of SMC theory in1998.SMC is of great importance in various kinds of situations with privacy concerns, such as military cooperation and commercial investments and so on. For example, some countries want to jointly guard an area but don’t want to tell the others its distribution of the military strength. Another example is that some companies want to jointly develop a business district. They should avoid overlapped investment to achieve interest maximization but don’t want the others know the business layout.The dissertation summarizes the achievements of previous researchers. We firstly introduce the research background and status of SMC in chapter1. After the overview of previous research achievements, we come up with the arrangement of the research contents, as well as the framework of the following chapters.In chapter2, we introduce the definition, theory and applications in SMC. And then introduce the common method to construct the SMC protocols. Afterwards, we introduce the massive basic protocols in SMC, and also give a description of the implements in each protocol. To make the protocol construction in the following chapters unified, we define a series of symbols in the end.In chapter3, we focus on the point-convex hull inclusion problem, including static situation and dynamic situation. We firstly present a point-line relative position protocol in order to tell which side the point is located. Then, we consider leaking certain information in order to get a high efficiency, not affecting the security of private data. After the construction of protocol in static situation, we move on to discuss how to achieve the dynamic inclusion judgment. We use the velocity to get the interval in order to diminish the judging times, but can still detect the inclusion in time. And then, we discuss the rotation state of convex hull, and give a responding SMC protocol. The research in this chapter makes SMC protocol much practical.In chapter4, we discuss the construction of convex hull problem. Firstly, we develop the cross product protocol in order to let any three parties can jointly do the cross product securely. Based on this, we present a protocol for any three parties to construct convex hull. This protocol can adjust to the active join or quit of users very well. If one user wants to join in, he just computes the local convex hull and then jointly judging which point is the point of final convex hull. When some points join in or quit, the protocol can also perform well without additional modifications. Thus, the protocol has very good flexibility.In chapter5, we introduce the problem of sharing the meeting points of two intersect circles. For example, in scientific experiments, they want to jointly analyze their private results to get the boundary of experiment data, but don’t want the others acquire any private information. We can view the data scope as a circle, and then the problem is to compute the meeting points of two circles. Our solution is to transfer the accurate point to numerical value, and then adopt the binary search algorithm to calculate the approximate value. The sub protocols in the solution are secure, so no one can derive any other information from the mid steps, including the direction information.In chapter6, we focus on the privacy preserving personalized recommendation systems. We design a self-adjust bipartite network with feedback function based on two algorithms, Heat Conduction algorithm and Mass Diffusion algorithm. We view the connections between users and items as wires with damping parameter, which can partly reflect the recommendation ability. When the value transfers through the wire, it will cost a bit depending on the parameter. Then we design a SMC protocol based on the new model to make sure of the private values not disclosed when providing the recommended list. After analyzing the protocol, we find that it can be used to the separated database jointed together to perform the privacy preserving recommending procedures. So we make the recommendation much more practical, especially in the situation when some of the companies want to cooperate using their private database to provide a better user experience. It benefits not only the companies, but also the users as well.