判断集合包含关系的安全计算协议.pdf

第32卷第7期 计 算 机 学 报 V01．32No．7 2009 2009年7月 CHINESE 0FCOMPUTERS July JOURNAL 判断集合包含关系的安全计算协议 李荣花’2’ 武传坤 张玉清2’ 1’(中国科学院研究生院北京100049) 2’(国家计算机网络入侵防范中心北京 100049) 3’(中国科学院软件研究所信息安全国家重点实验室北京100080) 摘 要研究了安全计算中关于集合的问题：A拥有一个秘密的集合S一，B拥有一个秘密的集合Ss(Sa和Ss来自 一个全集)，双方希望知道S。是否包含Ss，但是不希望泄漏关于集合S一和Se的其它有用信息．针对此问题，提出了 J限解密 3个具有不同效率和安全性的安全计算协议．设集合Se的大小为Ns．第1个协议基于叠加密(或者支持f 的加法同态加密方案)，需要N。轮通信．另外两个协议基于普通的加法同态加密方案，仅需一轮通信．与同类成果 比，前两个协议使用了新的集合表示法，第3个协议在输出结果阶段不需要门限解密，通信效率较好． 关键词安全计算；集合包含；叠加密；同态加密 中圈法分类号TP309DOI号：10．3724／SP．J．1016．2009．01337 Secure Protocolfor theInclusionRelationofSets Computation Testing LI WUChuan—Kun3’ZHANG Rong-Hual’’2’ Yu—Qin92’ 100049) ”(GraduateUniversityChineseAcademyofSciences，Beijing of 2’(National NetzvorkIntrusionProtection 100049) Computer Center·Beijing 100080) 3’(StateKeyLaboratoryofInformationSecurity。InstituteofSofttoare，ChineseAcademyofSciences，Beijing Aset isconsideredinthesecure Ahas Abstract operationproblem computationsetting．Player toa want asecretset and Bhasasecretset S^andSB universe．They SA player SB，where belong knowif without elseabouttheirsecretsets．Three o