集合间基本操作的多方保密计算

亢 佳，杨晓艺，刘 新

(陕西师范大学 计算机科学学院，陕西 西安 710119)

集合间基本操作的多方保密计算

亢 佳，杨晓艺，刘 新

(陕西师范大学 计算机科学学院，陕西 西安 710119)

多方保密计算是近年来国际密码学界研究的热点问题。集合是科学研究中一个非常重要的概念，其在数学领域具有无可比拟的特殊重要性。现实生活中的许多问题可以转化成集合之间的基本操作问题来解决。对集合间的保密操作，如保密地计算集合交集、并集是多方保密计算中的一个重要方面，在保密的数据挖掘，保密的数据库查询等方面有重要的意义，在现实生活中也有广泛的应用前景和实用价值。为了解决集合之间基本操作的保密问题，提出了基于Paillier加法同态加密算法的安全两数差平方计算协议和求解集合交集的保密协议，并设计了基于百万富翁协议的求解集合并集的保密协议。理论分析表明，基于Paillier加法同态加密算法的安全两数差平方计算协议以及求解集合交集与并集的保密协议具有较好的正确性和安全性。

多方保密计算；集合交集；集合并集；加法同态

0 引 言

多方保密计算是近年来国际密码学界的一个研究热点[1-5]，在计算科学中占有重要地位。多方保密计算问题由Yao[6]最先提出，Goldreich等[7]对其进行了深入研究，推动多方保密计算理论的发展。

许多学者致力于研究具有实际应用背景的多方保密计算问题以及它们的解决方案，所研究的问题包括比较两个数的大小[8-11]、保密的数据挖掘[12]、比较两条信息是否相同[13]、保密的数据库查询、保密拍卖[14]、保密的统计分析、保密的计算几何[15-18]等。……