高效的区间保密计算及应用

《高效的区间保密计算及应用》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第４０卷第７期计算机学报Ｖｏｌ．４０Ｎｏ．７２０１７年７月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＪｕｌｙ２０１７高效的区间保密计算及应用郭奕１），２）１）３）１）４）周素芳窦家维李顺东王道顺１）（陕西师范大学计算机科学学院西安７１０１１９）２）（中国科学院软件研究所可信计算与信息保障实验室北京１００１９０）３）（陕西师范大学数学与信息科学学院西安７１０１１９）４）（清华大学计算机科学与技术系北京１０００８４）摘要多方保密计算是目前国际密码学界的研究热点，是网络空间隐私保护与信息安全的关键技术．密码学者已经研究了很多多方保密计算问题，但更

2、多的多方保密计算问题还有待研究．文中研究一个重要的多方保密计算问题———有理数的区间的保密计算，即保密地计算一个保密的有理数在不在另一个保密的有理数区间内．该问题在密码学中有重要的理论意义，在其他多方保密计算协议的构造中有重要的实际意义，在隐私保护方面有广泛的应用．其中包括计算几何上的点与圆环的包含问题《，点与无限区域的包含问题，点与线段的包含问题等．甚至在现实的商品交易中，运用该问题的解决方案能够减少交易成本．文中基于Ｐａｉｌｌｉｅｒ同态加密方案，以百万富翁协议为基本思想，利用计算几何理论，将有理数区间保密计算问题输入的有理数看成过原点的直线的斜率

3、，将区间保密计算问题归约为直线之间的位置关系计，根据平面直角坐标系上三点定义的三角形面积计算公式，设计了一个高效的有理数区间保密计算协议；采用基本算术知识，将有理数的大小比较归约到算术不等式的判定，调用对称密码整数集百万富翁协议，设计了另一个高效的有理数区间保密计算协议算；用模拟范例证明了两个协议的安全性；通过理论和实际编程分析了协议的效率；分析表明两个协议是正确高效的；最后给出了协议在解决其他多方保密计算问题中的应用实例．机关键词密码学；多方保密计算；区间保密计算；同态加密中图法分类号ＴＰ３０９犇犗犐号１０．１１８９７／ＳＰ．Ｊ．１０１６．２０１７

4、．０１６６４学犈犳犳犻犮犻犲狀狋犘狉犻狏犪犮狔犘狉犲狊犲狉狏犻狀犵犐狀狋犲狉狏犪犾犆狅犿狆狌狋犪狋犻狅狀犪狀犱犐狋狊犃报狆狆犾犻犮犪狋犻狅狀狊１），２）１）３）１）４）ＧＵＯＹｉＭｉｎＺＨＯＵＳｕＦａｎｇＤＯＵＪｉａＷｅｉＬＩＳｈｕｎＤｏｎ》ｇＷＡＮＧＤａｏＳｈｕｎ１）（犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲，犛犺犪犪狀狓犻犖狅狉犿犪犾犝狀犻狏犲狉狊犻狋狔，犡犻’犪狀７１０１１９）２）（犜狉狌狊狋犲犱犆狅犿狆狌狋犻狀犵犪狀犱犐狀犳狅狉犿犪狋犻狅狀犃狊狊狌狉犪狀犮犲犔犪犫狅狉犪狋狅狉狔，犐狀狊狋犻狋狌狋犲狅犳犛狅犳狋狑犪狉犲，犆犺犻

5、狀犲狊犲犃犮犪犱犲犿狔狅犳犛犮犻犲狀犮犲狊，犅犲犻犼犻狀犵１００１９０）３）（犛犮犺狅狅犾狅犳犕犪狋犺犲犿犪狋犻犮狊犪狀犱犐狀犳狅狉犿犪狋犻狅狀犛犮犻犲狀犮犲，犛犺犪犪狀狓犻犖狅狉犿犪犾犝狀犻狏犲狉狊犻狋狔，犡犻’犪狀７１０１１９）４）（犇犲狆犪狉狋犿犲狀狋狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犜狊犻狀犵犺狌犪犝狀犻狏犲狉狊犻狋狔，犅犲犻犼犻狀犵１０００８４）犃犫狊狋狉犪犮狋Ｓｅｃｕｒｅｍｕｌｔｉｐａｒｔｙｃｏｍｐｕｔａｔｉｏｎ（ＳＭＣ）ｉｓｐｒｅｓｅｎｔｌｙａｒｅｓｅａｒｃｈｆｏｃｕｓｉｎｔｈｅｉｎｔｅｒｎａｔｉｏｎａｌｃｒ

6、ｙｐｔｏｇｒａｐｈｉｃｃｏｍｍｕｎｉｔｙａｎｄａｋｅｙｔｅｃｈｎｏｌｏｇｙｏｆｐｒｉｖａｃｙｐｒｅｓｅｒｖｉｎｇａｎｄｉｎｆｏｒｍａｔｉｏｎｓｅｃｕｒｉｔｙｉｎｃｙｂｅｒｓｐａｃｅ．ＴｈｉｓｐａｐｅｒｉｎｖｅｓｔｉｇａｔｅｓａｎｉｍｐｏｒｔａｎｔＳＭＣｐｒｏｂｌｅｍ，ｓｐｅｃｉｆｉｃｐｒｉｖａｃｙｐｒｅｓｅｒｖｉｎｇｒａｔｉｏｎａｌｉｎｔｅｒｖａｌｃｏｍｐｕｔａｔｉｏｎ（ＰＩＣ）．ＰＩＣａｔｔｅｍｐｔｓｔｏｓｅｃｕｒｅｌｙｄｅｔｅｒｍｉｎｅｗｈｅｔｈｅｒｏｎｅｐｒｉｖａｔｅｒａｔｉｏｎａｌｎｕｍｂｅｒｂｅｌｏｎｇｓｔｏａｐｒｉｖａｔｅｒａｔｉｏｎａ

7、ｌｉｎｔｅｒｖａｌ．Ｔｈｉｓｐｒｏｂｌｅｍｉｓｏｆｔｈｅｏｒｅｔｉｃａｌｃｒｙｐｔｏｇｒａｐｈｉｃｉｍｐｏｒｔａｎｃｅ，ｈａｓｐｒａｃｔｉｃａｌｉｍｐｏｒｔａｎｃｅｉｎｃｏｎｓｔｒｕｃｔｉｎｇｏｔｈｅｒＳＭＣｐｒｏｔｏｃｏｌｓ，ａｎｄｈａｓｍａｎｙＰＩＣｒｅｌａｔｅｄａｐｐｌｉｃａｔｉｏｎｓ，ｓｕｃｈａｓｔｈｅｉｎｃｌｕｓｉｏｎｐｒｏｂｌｅｍｓｂｅｔｗｅｅｎｐｏｉｎｔａｎｄｒｉｎｇ，ｐｏｉｎｔａｎｄｉｎｆｉｎｉｔｅｒｅｇｉｏｎ，ｐｏｉｎｔａｎｄｓｅｇｍｅｎｔ，ａｎｄｓｏｏｎ，ｅｖｅｎｉｓａｂｌｅｔｏｒｅｄｕｃｅｔｈｅｃｏｓｔｉｎｒｅａｌｃｏｍｍｏｄ

8、ｉｔｙｔｒａｎｓａｃｔｉｏｎ．收稿日期：２０１５０５１９；在线出版日期：２０１６０４２４．本课题得到