| Secure multi-party computation is a hot research focus in international cryptographic community in recent years. It's application is very wide, like data mining, scientific computing, database using and so on, and it has become an important tool in the field of cryptography extremely and an indispensable component in the field of calculation. Although the general problems of secure multi-party computation are solvable, the theory solutions may not be feasible because of the efficiency or the calculation. The specific problem needs specific solution. So, to study various problems of secure multi-party computation and solutions whice have practical background is one of the problems which are attended by people.For there are specific geometry problems provided in a lot of application fields, it is necessary to build effective algorithms for these problems, and they are the base of computational geometry. These problems including Euclid tour salespersons problem, Minimum spanning tree problems, Linear programming problems and so on. There are a lot of solved problems based on convex hull, and lots of mature solutions, but the convex hull problems based on protection of privacy information are on the way of researching. Confidential computational geometry problem is a new field of secure multi-party computation researching, and is one kind of specific secure multi-party computation. Although there are some theoretical solutions, they may not be feasible because of the efficiency, and need specific approach. At present, international researching on these problems is in the initial stage, and to research efficient and practical secure multi-party computation protocol is one of the problems which are attended by people.In this paper, the problems that have been solved are the basic problems of computational geometry based on privacy protecting. The most important things are how to find the problems and the methods to solve them but the problems they are. The secure multi-party computation is used in computational geometry to solve two problems. One is privacy protecting similitude determination for two convex polygons. It is a special secure multi-party computation question. Private determination of whether two sets of data are equal or are proportional correspondingly is a basic problem of secure multi-party computation. The problem of similitude determination for two convex polygons is solved by using corresponding equality-testing protocol and dot-product protocol, and the protocol for determining whether two sets of data are proportional correspondingly.The other one is a convex hull algorithm for planar point set based on privacy protecting. Convex hull algorithm is base in computational geometry, but to determine a big convex hull by two private point sets is a special computation geometry problem, and is also a special secure multi-party computation problem. By using the scheme for solving intersection problem of two line-segments, and equality-testing protocol, and Oblivious Transfer mind, a protocol to determine a line by two secret points is proposed, and by which a convex hull algorithm for planar point set based on privacy protecting is proposed.In the end, the conclusion is given and the further research direction is pointed out. |
