集合成员关系的安全多方计算及其应用

doi:10.3969/j.issn.0372-2112.2017.05.013

电子学报 ›› 2017, Vol. 45 ›› Issue (5): 1109-1116.DOI: 10.3969/j.issn.0372-2112.2017.05.013

集合成员关系的安全多方计算及其应用

陈振华¹, 李顺东², 王道顺³, 黄琼⁴, 张卫国¹

1. 西安科技大学计算机科学与技术学院, 陕西西安 710054;
2. 陕西师范大学计算机科学学院, 陕西西安 710062;
3. 清华大学计算机科学与技术系, 北京 100084;
4. 华南农业大学数学与信息学院, 广东广州 510642

收稿日期:2015-11-02 修回日期:2016-05-12 出版日期:2017-05-25
- 通讯作者:
- 陈振华
- 作者简介:
- 李顺东 男,1963年生于河南,博士生导师,研究方向为安全多方计算;王道顺 男,1967年生于四川,硕士生导师,研究方向为分组密码的设计与分析;黄琼男,1981年生于江西,硕士生导师,研究方向为数字水印,防伪技术;张卫国 男,1963年生于陕西,硕士生导师,研究方向为信息安全.
- 基金资助:
- 西安科技大学博士启动基金 (No.2015QDJ008）; 信息安全国家重点实验室开放课题基金 (No.2016-MS-19）

Secure Multiparty Computation of Set Membership and Its Applications

CHEN Zhen-hua¹, LI Shun-dong², WANG Dao-shun³, HUANG Qiong⁴, ZHANG Wei-guo¹

1. School of Computer Science and Technology, Xi'an University of Science and Technology, Xi'an, Shaanxi 710054, China;
2. School of Computer Science, Shaanxi Normal University, Xi'an, Shaanxi 710062, China;
3. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
4. College of Mathematics and Informatics, South China Agricultural University, Guangzhou, Guangdong 510642, China

Received:2015-11-02 Revised:2016-05-12 Online:2017-05-25 Published:2017-05-25

摘要/Abstract

摘要：

集合成员关系的安全多方计算在保密数据挖掘和保密数据查询等方面有着重要的应用价值.针对以往方案在集合规模较大时的低效问题，本文将原问题转化成多项式一次性求值问题，在此基础上共设计了四个协议.利用同态加密设计了平凡协议1；利用离散对数设计了高效协议2，此协议非常简洁.最后，针对不同的应用场景又分别设计了云计算环境下外包用户计算的协议3和抗抵赖环境下可公开保密判定的协议4.通过分析和比较显示，我们的方案除了集合的势，其余任何信息都没有泄露，并且在集合规模较大时，相比以往方案高效而简洁.

关键词: 集合成员, 安全多方计算, 同态加密, 离散对数, 云计算, 抗抵赖

Abstract:

Secure multiparty computation of set membership is significant to privacy-preserving data mining,data query,etc.In this paper,we first transform the original problem into the one-time evaluation problem for polynomial,and then construct four protocols.We design the trivial protocol 1 using homomorphic encryption and construct the efficient protocol 2 using discrete logarithm instead of encryption,which is very concise.Lastly,according to the different application scenarios,we also propose protocol 3 and protocol 4:the former can be used to outsource computation in cloud computing environment;the latter can be used for public secure computation against repudiation.The analysis and comparison show that our protocols are more efficient and concise than previously known.

Key words: set membership, secure multi-party computation, homomorphic encryption, discrete logarithm, cloud computing, against repudiation

中图分类号:

TP309

陈振华, 李顺东, 王道顺, 黄琼, 张卫国. 集合成员关系的安全多方计算及其应用[J]. 电子学报, 2017, 45(5): 1109-1116.

CHEN Zhen-hua, LI Shun-dong, WANG Dao-shun, HUANG Qiong, ZHANG Wei-guo. Secure Multiparty Computation of Set Membership and Its Applications[J]. Acta Electronica Sinica, 2017, 45(5): 1109-1116.

参考文献

[1] Yao A C.Protocols for secure computations[A].Proceedings of 23rd IEEE Symposium on Foundations of Computer Science[C].Chicago,USA,1982.160-164.
[2] Du W L,Atallah M J.Privacy-preserving cooperative scientific computations[A].Proceedings of 14th IEEE Computer Security Foundations Workshop Lecture[C].Cape Breton,Canada,2001.273-282.
[3] Agrawal R,Srikant R.Privacy-preserving data mining[A].Proceedings of ACM International Conference on Management of Data and Symposium on Principles of Database Systems[C].Dallas,USA,2000.439-450.
[4] 杨高明,杨静,张健沛.聚类的(A,k)-匿名数据发布[J].电子学报,2011,39(8):1941-1946. Yang G M,Yang J,Zhang J P.Achieving (A,k)-anonymity via clustering in data publishing[J].Acta Electronica Sinica,2011,39(8):1941-1946.(in Chinese)
[5] Goldberg I.Improving the robustness of private information retrieval[A].Proceedings of IEEE Symposium on Security and Privacy[C].Berkeley,CA,2007.131-148.
[6] Samanthula,B K,Elmehdwi,Y,Howser,Gerry,et al.A secure data sharing and query processing framework via federation of cloud computing[J].Information Systems,2015,48:196-212.
[7] Loftus J,Smart N P.Secure outsourced computation[A].Progress in Cryptology-AfricaCrypt 2011[C].Dakar,Senegal,2011.LNCS 6737:1-20.
[8] Goldwasser.Multi-party computations:Past and present[A].Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing[C].Santa Barbara,USA,1997.1-6.
[9] Goldreich O,Micali S,Wigderson,A.How to play ANY mental game[A].Proceedings of the 19thAnnual ACM Conference on Theory of Computing[C].Pittsburgh,USA,1987.218-229.
[10] Goldreich O.Foundations of cryptography:Basic applications[M].London:Cambridge University Press,2004.599-729.
[11] Du W L,Atallah M J.Secure multi-party computation problems and their applications:A review and open problems[A].Proceedings of New Security Paradigms Workshop 2001[C].Cloudcroft,USA,2001.11-20.
[12] Freedman M J,Nissim K,Pinkas B.Efficient private matching and set intersection[A].Advances in Cryptology-EuroCrypt 2004[C].Interlaken,Switzerland,2004.LNCS 3027:1-19.
[13] Kissner L,Song D.Privacy-preserving set operations[A].Advances in Cryptology-Crypt 2005[C].Santa Barbara,USA,2005.LNCS 3621:241-257.
[14] 李顺东,王道顺.现代密码学:理论.方法与研究前沿[M].北京:科学出版社,2009.193-232.
[15] 马敏耀.安全多方计算及其扩展问题的研究[M].北京:北京邮电大学,2010.
[16] 豆永丽,等.集合成员判定问题的安全多方计算解决方案[J].计算机应用,2013,33(12):3527-3530. Dou yongli,et al.Secure multiparty computation solutions of collection member decision[J].Journal of Computer Applications,2013,33(12):3527-3530.(in Chinese)
[17] Paillier P.Public-key cryptosystems based on composite degree residue classes[A].Advances in Cryptology-EuroCrypt 1999,Prague,Czech[C].Republic.1999,LNCS 1592:223-238.
[18] Boneh,EJGD,Nissim K.Evaluating 2-DNF Formulas on Ciphertexts[A].TCC 2005[C].Cambridge,USA,2005.LNCS 3378:325-341.
[19] Mitsunari S,Sakai R,Kasahara M.A new traitor tracing[J].IEICE TRANSACTIONS on Fundamentals of Electronics,Communications and Computer Sciences,2002,E85-A (2):181-484.
[20] Feldman,P A practical scheme for non-interactive verifiable secret sharing[A].Proceedings of the IEEE 28th Annual Symposium on Foundations of Computer Science[C].Los Angeles,USA,1987.427-438.
[21] Du W,Zhan Z.A practical approach to solve secure multi-party computation problems[A].Proceedings of the ACM 2002 workshop on New security paradigms[C].Virginia Beach,USA,2002.127-135.

集合成员关系的安全多方计算及其应用

Secure Multiparty Computation of Set Membership and Its Applications

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	丁毅, 沈薇, 李海生, 钟琼慧, 田明宇, 李洁. 面向CNN的区块链可信隐私服务计算模型[J]. 电子学报, 2022, 50(6): 1399-1409.
[2]	罗智勇, 朱梓豪, 谢志强, 孙广路. 面向云计算的花朵差分授粉工作流多目标优化算法研究[J]. 电子学报, 2021, 49(3): 470-476.
[3]	汪榆淋, 窦家维. k-min问题安全多方计算方案及应用[J]. 电子学报, 2021, 49(11): 2256-2260.
[4]	宋秀丽, 周道洋, 文爱君. d维(t,n)门限量子同态加密算法的设计与仿真[J]. 电子学报, 2020, 48(5): 846-853.
[5]	李航, 冯朝胜, 刘帅南, 刘彬, 赵开强. 支持离线/在线加密及可验证外包解密的CP-WABE方案[J]. 电子学报, 2020, 48(11): 2146-2153.
[6]	李顺东, 杜润萌, 杨颜璟, 魏琼. 有理数相等的保密判定[J]. 电子学报, 2020, 48(10): 1933-1937.
[7]	窦家维, 陈明艳. 多重集的保密计算及应用[J]. 电子学报, 2020, 48(1): 204-208.
[8]	侯红霞, 杨波, 张丽娜, 张明瑞. 安全的两方协作SM2签名算法[J]. 电子学报, 2020, 48(1): 1-8.
[9]	李秋贤, 田有亮, 王缵. 基于全同态加密的理性委托计算协议[J]. 电子学报, 2019, 47(2): 470-474.
[10]	窦家维, 王文丽, 刘旭红, 李顺东. 有理区间的安全多方计算与应用[J]. 电子学报, 2018, 46(9): 2057-2062.
[11]	窦家维, 李顺东. 数据相等问题的安全多方计算方案研究[J]. 电子学报, 2018, 46(5): 1107-1112.
[12]	李子臣, 张卷美, 杨亚涛, 张峰娟. 基于NTRU的全同态加密方案[J]. 电子学报, 2018, 46(4): 938-944.
[13]	卢晶, 段勇, 刘海波. 基于z值的分布式密度峰值聚类算法[J]. 电子学报, 2018, 46(3): 730-738.
[14]	段然, 顾纯祥, 祝跃飞, 郑永辉, 陈莉. 一种NTRU格上基于身份全同态加密体制设计[J]. 电子学报, 2018, 46(10): 2410-2417.
[15]	苏盛辉, 孙国栋. 基于多离散对数问题的公钥密码的分析[J]. 电子学报, 2018, 46(1): 218-222.