A secure multi-party computation solution to intersection problems of sets and rectangles

摘要

Secure multi-party computation (SMC) is a research focus in international cryptographic community. At present, there is no SMC solution to the intersection problem of sets. In this paper, we first propose a SMC solution to this problem. Applying Cantor encoding method to computational geometry problems, and based on the solution to set-intersection problem, we further propose solutions to points inclusion problem and intersection problem of rectangles and further prove their privacy-preserving property with widely accepted simulation paradigm. Compared with the known solutions, these new solutions are of less computational complexity and less communication complexity, and have obvious superiority in computational and communication complexity.