基于同态加密的高效多方保密计算

doi:10.3969/j.issn.0372-2112.2013.04.029

电子学报 ›› 2013, Vol. 41 ›› Issue (4): 798-803.DOI: 10.3969/j.issn.0372-2112.2013.04.029

基于同态加密的高效多方保密计算

李顺东¹, 王道顺²

1. 陕西师范大学计算机科学学院,陕西西安 710062;
2. 清华大学计算机科学与技术系,北京 100084

收稿日期:2012-06-29 修回日期:2012-10-22 出版日期:2013-04-25
- 作者简介:
- 李顺东 男,1963年12月生,河南平顶山人.1984、1987年在西安工程大学获工学学士、硕士学位;2003年在西安交通大学获计算机科学与技术工学博士学位.现为陕西师范大学计算机科学学院教授、博士生导师.主要从事密码学与信息安全研究. E-mail:shundong@snnu.edu.cn 王道顺 男,1964年12月生,四川苍山人.1987年获兰州大学数学学士学位,2001年获四川大学数学博士学位.现为清华大学计算机科学与技术系副教授,博士生导师.主要研究兴趣为密钥管理、数字水印与多媒体安全. E-mail:daoshun@tsinghua.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61070189,No.61272435,No.61170032); 陕西省科技攻关计划 (No.2008K01-58)

Efficient Secure Multiparty Computation Based on Homomorphic Encryption

LI Shun-dong¹, WANG Dao-shun²

1. School of Computer Science, Shaanxi Normal University, Xi'an, Shaanxi 710062, China;
2. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

Received:2012-06-29 Revised:2012-10-22 Online:2013-04-25 Published:2013-04-25
- Supported by:
- National Natural Science Foundation of China (No.61070189, No.61272435, No.61170032); Key Technology Research and Development Program of Shaanxi Province (No.2008K01-58)

摘要/Abstract

摘要： 多方保密计算是信息社会隐私保护的核心技术,是国际密码学界的研究热点之一.本文首先提出了一种新的对保密数据进行编码的方案,接着利用这种新的编码方案和同态加密方案,构造了一个百万富翁问题新的解决方案,并证明了方案的安全性.新的方案更简洁、更具有普遍意义,能够对可定义全序关系的任意两个对象进行比较.最后用这个新的解决方案解决了另一个新的多方保密计算问题-两个整数的互素问题,证明了方案是安全的.

关键词: 密码学, 同态加密, 多方保密计算, 百万富翁问题, 互素问题

Abstract: Secure multiparty computation is a key privacy-preserving technology in cyberspaces and a research focus in the international cryptographic community.We first present a new encoding scheme to encode private data.By using this encoding scheme together with homomorphic encryption scheme,we construct a new scheme for Yao's millionaires' problem and prove its privacy-preserving property.This new scheme is more concise,more general and can be applied to compare any two objects on which a total order can be defined.We finally utilize the new scheme to propose a solution to the coprime problem and prove the privacy-preserving properties of the solution.

Key words: Cryptography, homomorphic encryption, secure multiparty computation, millionaires' problem, coprime problem

中图分类号:

TN918.3

李顺东, 王道顺. 基于同态加密的高效多方保密计算[J]. 电子学报, 2013, 41(4): 798-803.

LI Shun-dong, WANG Dao-shun . Efficient Secure Multiparty Computation Based on Homomorphic Encryption[J]. Acta Electronica Sinica, 2013, 41(4): 798-803.

参考文献

[1] A C Yao.Protocols for secure computations [A].Proceedings of the 23th IEEE Sym posium on Foundations of Computer Science [C].Piscataway:IEEE Press,1982.160-1 64.
[2] S Goldwasser.Multi-party computations:Past and present [A].Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing [C].NY:ACM P ress,1997.1-6.
[3] W L Du,M J Atallah.Privacy-preserving cooperative scientific computations [A] .Proceedings of 14th IEEE Computer Security Foundations Workshop Lecture [C].P iscataway:IEEE Press,2001.273-282.
[4] S G Choi,K W Hwangy,J Katz,et al.Secure multi-party computation of boolean circ uits with applications to privacy in on-line marketplaces [A].Lecture Notes i n Computer Science 7178 [C].NY:Springer,2012.416-432.
[5] R Agrawal,R Srikant.Privacy-preserving data mining [A].Proceedings of ACM Int ernational Conference on Management of Data and Symposium on Principles of Datab ase Systems [C].NY:ACM Press,2000.439-450.
[6] 杨高明,杨静,张健沛.聚类的(α,k)-匿名数据发布[J].电子学报,2011,39(8):1941-19 46. YANG Gao-ming,YANG Jing,ZHANG Jian-pei. Achieving(α,k)-anonymity via cluste ring in data publishing [J].Acta Electronica Sinica,2011,39(8):1941-1946.(in C hinese)
[7] T Toft.Secure data structures based on multi-party computation [A].Proceeding s of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed C omputing [C].NY:ACM Press,2011.291-292.
[8] J Loftus,N P Smart.Secure outsourced computation[A].Lecture Notes in Computer Science 6737[C].NY:Springer,2010.1-20.
[9] O Goldreich,S Micali,A Wigderson.How to play any mental game [A].Proceedings o f the Nineteenth Annual ACM Conference on Theory of Computing [C].Piscataway:I EEE Press,1987.218-229.
[10] O Goldreich.The Fundamental of Cryptography:Basic Applications [M].London:Camb ridge University Press,2004.
[11] A C Yao.How to generate and exchange secrets [A]. Proceedings of 27th Annual S ymposium on Foundations of Computer Science [C].Piscataway:IEEE Press,1986.162 -167.
[12] I Ioannidis,A Grama.An efficient protocol for yao's millionaires' problem [A].Proceedings of the 36th Hawaii International Conference on System Science [C].Piscataway:IEEE Press,2003.1-6.
[13] C Clifton,D Marks.Security and privacy implications of data mining [A].Proceed ings of the ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery [C].NY:ACM Press,1996.15-19.
[14] 王波,杨静.一种基于逆聚类的个性化隐私匿名方法[J].电子学报,2012,40(5):883-890. WANG Bo,YANG Jing.A personalized privacy anonymous method based on inverse clust ering [J].Acta Electronica Sinica,2012,40(5):883-890.(in Chinese)
[15] Fagin R,Naor M,Winklery P.Comparing information without leaking it [J].Communi cations of the ACM,1996,39(5):77-85.
[16] 刘文,王永滨.安全多方信息比较相等协议及其应用[J].电子学报,2012,40(5):871-876. LIU Wen,WANG Yong-bin.Secure multi-party comparing protocol and its applicatio ns [J].Acta Electronica Sinica,2012,40(5):871-876.(in Chinese)
[17] W L Du,M J Atallah.Protocols for secure remote database access with approximate matching [A].Advance of E-Commerce and Privacy [C].NY:Springer,2001.87111.
[18] C Cachin.Efficient private bidding and auctions with an oblivious third party [A].Proceedings of the 6th ACM Conference on Computer and Communications Securit y [C].NY:ACM Press,1999.120-127.
[19] M J Atallah,W L Du.Secure multi-party computational geometry [A].Lecture Note s in Computer Science 2125 [C].NY:Springer,2001.165-179.
[20] Li S D,Dai Y Q.Secure two-party computational geometry [J].Journal of Compute r Science and Technology,2005,20(2):258-263.
[21] W L Du,M J Atallah.Secure multi-party computation problems and their applicatio ns:A review and open problems [A].Proceedings of New Security Paradigms Worksh op 2001 [C].NY:ACM Press,2001.11-20.
[22] Sheikha R,Mishra D K,Kumar B.Secure multiparty computation:From millionaires pro blem to anonymizer [J].Information Security Journal:A Global Perspective,2011, 20(1):25-33.
[23] H Y Lin,W G Tzeng.An efficient solution to the millionaires' problem based on h omomorphic encryption [A].Proceedings of Applied Cryptography and Network Secu rity 2005 (LNCS3531)[C].NY:Springer,2005.456-466.
[24] R Rivest,L Adleman,M Dertouzos.On data banks and privacy homomorphisms [A].Fou ndations of Secure Computation [C].Liverpool:Academic Press,1978.169-177.
[25] P Paillier.Public-key cryptosystems based on composite degree residuosity class es [A].Lecture Notes in Computer Science 1592 [C].NY:Springer,1999.223-238.
[26] M Fischlin.A cost-effective pay-per-multiplication comparison method for mill ionaires[A].Proceedings of the 2001 Conference on Topics in Cryptology:The Cry ptographer's Track at RSA (LNCS2020)[C].NY:Springer,2001.457-472.
[27] 李顺东,戴一奇,尤启友.姚氏百万富翁问题的高效解决方案[J].电子学报,2005,2005,3 3 (5):770-773. LI Shun-dong,DAI Yi-qi,YOU Qi-you.An efficient solution to yao's millionaire s' problem [J].Acta Electronica Sinica,2005,33(5):770-773.(in Chinese)
[28] Li S D,Wang D S,Dai Y Q,et al.Symmetric cryptographic solution to yao's million aires' problem and an evaluation ofsecure multiparty computations [J].Information Sciences,2008,178(2):244-255.
[29] C Gentry.A fully homomorphic encryption scheme (PhD thesis)[OL].http://crypto .stanford.edu /craig/ (2009)

基于同态加密的高效多方保密计算

Efficient Secure Multiparty Computation Based on Homomorphic Encryption

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	丁毅, 沈薇, 李海生, 钟琼慧, 田明宇, 李洁. 面向CNN的区块链可信隐私服务计算模型[J]. 电子学报, 2022, 50(6): 1399-1409.
[2]	赵璐, 刘春红, 杜蛟, 曹天庆. Z₄上两类具有最优自相关四元序列的线性复杂度研究[J]. 电子学报, 2021, 49(4): 631-636.
[3]	汪榆淋, 窦家维. k-min问题安全多方计算方案及应用[J]. 电子学报, 2021, 49(11): 2256-2260.
[4]	陈露, 相峰, 孙知信. 基于属性密码体制的区块链安全技术研究进展[J]. 电子学报, 2021, 49(1): 192-200.
[5]	窦家维, 王颖囡, 葛雪. 区间关系保密计算若干问题研究[J]. 电子学报, 2021, 49(1): 50-57.
[6]	戚珉, 陈明. 标准模型下基于身份的混淆乐观公平交换方案[J]. 电子学报, 2020, 48(8): 1516-1527.
[7]	宋秀丽, 周道洋, 文爱君. d维(t,n)门限量子同态加密算法的设计与仿真[J]. 电子学报, 2020, 48(5): 846-853.
[8]	杨启良, 周彦伟, 杨坤伟, 王涛. 标准模型下可公开验证的匿名IBE方案的安全性分析[J]. 电子学报, 2020, 48(2): 291-295.
[9]	李顺东, 杜润萌, 杨颜璟, 魏琼. 有理数相等的保密判定[J]. 电子学报, 2020, 48(10): 1933-1937.
[10]	窦家维, 陈明艳. 多重集的保密计算及应用[J]. 电子学报, 2020, 48(1): 204-208.
[11]	侯红霞, 杨波, 张丽娜, 张明瑞. 安全的两方协作SM2签名算法[J]. 电子学报, 2020, 48(1): 1-8.
[12]	杨小东, 王美丁, 裴喜祯, 李雨潼, 陈春霖, 麻婷春. 一种标准模型下无证书签名方案的安全性分析与改进[J]. 电子学报, 2019, 47(9): 1972-1978.
[13]	李秋贤, 田有亮, 王缵. 基于全同态加密的理性委托计算协议[J]. 电子学报, 2019, 47(2): 470-474.
[14]	窦家维, 王文丽, 刘旭红, 李顺东. 有理区间的安全多方计算与应用[J]. 电子学报, 2018, 46(9): 2057-2062.
[15]	杜蛟, 刘春红, 张恩, 尚玉婧, 董乐. 基于拉丁方的GF(p)上q元旋转对称弹性函数的新构造[J]. 电子学报, 2018, 46(9): 2173-2180.