A Study Of Two Privacy-preserving Geometric Computation Problems

In recent years,science and technology have developed rapidly,and data in various industries such as finance,medicine,traffic has rapidly expanded on the Internet.Big data has an increasingly important impact on various fields of the country and society.People obtain valuable information from massive amounts of data by sharing data,but in this process the leakage of some sensitive data will brings serious consequences.Therefore,there is a contradiction between data sharing and privacy leaking.Secure multi-party computation(SMC)is an effective tool to solve the contradiction.SMC makes parties perform cooperative computation on their private data to obtain corresponding result without disclosing the privacy.SMC is a powerful and important tool for preserving privacy and information security in cooperative computation.Secure multi-party computational geometry(SMCG)is an important research direction of SMC.The secure multi-party interval computation and privately determining whether two segments intersect are two basic problems in SMCG.There still are many problems to be solved in research scope such as security,efficiency.This thesis studies two basic problems in SMCG:privacy-preserving determining the relationship between a secret interval and a threshold and privately determining whether two segments intersect.The main research contents are as follows.1.We extend the secure multi-party interval computation problem.In aspect of privately determining the relationship between a secret interval and a threshold,we design two efficient protocols for two different scenarios:the secret intervals are generated by two-party and multi-party.Both protocols can resist collusion attacks.Finally,we use above protocols as building blocks to privately detemine the relationship between a private point and a smallest rectangle and the relationship between a private point and and a secret segment.2.We analyze the shortcomings of the existing schemes that privately determine whether two segments intersect,and propose an improved protocol to privately determine whether two segments intersect.Comparing with the existing schemes,our new protocol is more secure.Also,we study the segment intersection problem that arises in a new scenario,which appeals stricter security.We design an efficient protocol using the formula that computes the area of a triangle formed by three points.Based on the protocol determining whether two segments intersect,we design a protocol to privately determine whether two private polygons intersect.