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

作　　者：LI Shundong DAI Yiqi WANG Daoshun LUO Ping 

机构地区：[1]Department of Computer Science and Technology, Beijing Normal University, Beijing 100875, China [2]Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

出　　处：《Progress in Natural Science:Materials International》2006年第5期538-545,共8页自然科学进展·国际材料（英文版）

基　　金：Supported by National Natural Science Foundation of China (Grant No. 90304014) and Hi-tech Research and Development Program of China(Grant No. 2005AA114160)

摘　　要：Secure multi-party computation （SMC） is a research focus in international cryptographie 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 communieation complexity.安全多党的计算(SMC ) 是在国际密码的社区的一个研究焦点。在 present' ，到集合的交叉问题没有 SMC。在这 paper' ，我们首先建议一个 SMC 答案到这个问题。适用的领唱者编码方法到计算几何学问题的家并且基于点包括问题和矩形并且进一步的交叉问题的答案与广泛地接受的模拟范例证明他们的保存隐私的性质的我们进一步建议的集合交叉 problem' 的答案。与已知的答案的家相比，这些新答案具有更少的计算复杂性和更少的通讯 complexity' 并且有明显的优势在计算并且通讯复杂性。

关 键 词：Cantor encoding secure multi-party computation set-intersection rectangle-intersection computational complexity. 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]