A Number Of Secure Multi-party Computation Problems

Secure multi-party computation is a comprehensive research field which relates to theory of computing, cryptography, distributed system, number theory, modern algebra and other subjects. It has received widespread attention from the researchers no sooner than it emerged due to its affluent theoretical contents and extensive application prospective. Since1982, the year when the first secure multi-party computational problem, known as Yao’s Millionaires’Problem, was proposed by Andrew C. Yao, secure multi-party computation has become a fundamental research subject for its plentiful contents in cryptography. The research on it is promising and prosperous, both in its basic theory and in its real-life applications.In a general secure multi-party computational protocol, two or more parties jointly compute a specific function f(x1,x2,...,x1,)=(f1(x1,x2,...,xn),...,fn(x1,x2,...,xn)) in which x1is the corresponding private input of the i-th participant. After the execution, each party Pi obtains his own output yi=f1(x1,x2,...,xn), respectively; meanwhile nothing about their private inputs is disclosed. In most secure multi-party computational problems, such as securely evaluating the average of three or more than three parties, each yi is totally the same; while in others, each participant may get different outputs, for instance, the scalar product protocol.The thesis mainly investigates two kinds of secure multi-party computational problems:privacy-preserving data mining which is also regarded as a branch field of data mining, and privacy-preserving computational geometry. In addition, some fundamental building blocks of secure multi-party computation have been proposed or promoted to improve the performance. To summarize, the main conclusions of this thesis are as follows:· In privacy-preserving data mining, we proposed a new algorithm which can be used to make some transformations of private data for date preprocessing. Preprocessing data with this algorithm will make the data supplier cannot only obtain the result/benefit he wants, but also prevent the data mining executor from getting the underlying effective rules that the data supplier does not want to disclose.· An efficient protocol for determining the position relation between points and straight lines is proposed and its correctness is rigorously proved. Its extended version can be used to determine the position relation between points and some special curves, such as polynomial function curves and exponential function curves.· The efficiency of some secure multi-party computational building blocks is improved, for instance, the scalar product protocol and the number comparison protocol. These improvements of existing basic protocols will serve as aides, to largely improve the efficiency of other complex secure multi-party computational protocols.