魏 琼, 李顺东, 王文丽, 杜润萌

陕西师范大学 计算机科学学院, 西安710119

1 引言

安全多方计算(Secure Multi-party Computation, MPC) 指的是两个或更多的参与者利用各自的保密数据作为计算的输入, 联合进行的保密计算, 计算结束后没有参与方能获得多于规定输出的信息, 是信息社会隐私保护的重要技术. 通过安全多方计算, 参与者可以在互不信任的网络环境中联合计算, 以实现保密的数据挖掘[1]、数据查询[2,3]、外包计算[4]等, 解决了数据的隐私性和安全性问题, 因此安全多方计算在国际密码学界研究中具有重要地位. 安全多方计算由图灵奖获得者姚期智首次提出[5], Goldreich、Micali 等人在此基础上做了大量研究[6,7], 他们的研究成果奠定了安全多方计算的理论基础[8-10]. 图灵奖获得者Goldwasser 认为安全多方计算是密码学一个极其重要的工具, 将成为计算科学一个必不可少的组成部分[11]. 目前研究的安全多方计算问题包括科学计算[12-15]、计算几何[16-19]、统计分析[20,21]等方面, 但此类安全多方计算问题大多限于整数数据为输入的保密计算, 未涉及描述事物关联的隐私数据的保密计算. 研究事物之间关联并发现规律, 对于认识世界、改造世界至关重要.

图论模型是一种强大而灵活的科学建模与数据分析工具, 是研究事物之间相互关联、相互影响最有效的模型. 事物之间的相互关联与影响构成了各种各样的网络, 如社交网络、交通网络、信息传播网络、疾病传播网络等, 这些网络都是图, 图可以直观地表达事……