安全多方计算协议的研究
|
摘要
随着网络技术的不断进步,以及高性能计算机、网格等日益强大的计算环境的出现,计算的方式正在发生极大地改变,用户可以利用网络上强大的计算资源来完成自己的计算任务。因此,在这种环境中,如何确保用户数据的安全,是需要考虑的一个最基本问题。
安全多方计算(Secure Multiparty Computation, SMC)是指一组互不信任的参与者,在不泄露各自私有信息的前提下进行的多方合作计算。自图灵奖得主A. C. Yao于上世纪80年代提出安全多方计算的概念以来,已得到许多学者的研究,其在密码学上的地位也日渐重要,它是电子选举、电子拍卖等密码学协议的基础。安全多方计算拓展了传统的分布式计算以及信息安全的范畴,为网络协作计算开创了一种新的计算模式,对解决网络环境下的信息安全问题具有重要的现实意义。
安全多方计算的研究是一个极其复杂的工作,尤其对于特殊问题的研究远远没有达到理想的程度。在本文中,笔者将重点讨论有关科学计算领域的安全两方及多方计算协议的问题,其内容包括多项式的求值及乘法运算、初等函数的运算(除反三角函数外)、行列式求值、向量及矩阵的相关运算、解线性方程组等。文章对一些已有的半诚实模型下的安全两方计算协议进行推广,提出了一些的安全多方计算协议,并对各协议的正确性、安全性及复杂性进行了讨论。此外,本文还对恶意模型下的安全两方及多方计算进行了探讨,提出了几个可容忍恶意行为模型下的基础及扩展协议。
With the continuous development of network technology, and with the appearance of high quality computers and net grid, the meanings and mode of computations are mostly changed. Users can make use of the powerful computation resources to complete their computation tasks. Therefore in this environment, the safety of users'data become very important and necessary.
Secure Multi-party Computation (SMC) is a computation among a set of participants who do not have confidence in one another, in which participants collaborate on desired tasks but do not reveal private information of their own. Since it was initially suggested by A.C.Yao in the 1980s, SMC have been a major part of modern cryptography and attracted numerous researchers'interest. It's the basis of many distributed cryptographic protocols such as threshold cryptosystem, electronic voting and electronic auction, etc. Secure multi-party computation has extended the traditional distributed computation and information security areas. A new computation mode was created for network collaborative computation. It is very significant to solve the information security problems in the network environment.
Researches on the SMC are very complicated tasks. And researches on the special issues are far from ideal. In this paper, secure two-party and multiparty computation protocol problems were discussed which including polynomial evaluation and multiplication, elementary function operation (except inverse trigonometric function), determinant evalua-tion, vector and matrix related operation, solving linear equation and so on. Some existing secure two-party computation protocols of semi-honest models were generalized. A series of secure multiparty computation protocols were advanced. Correctness, security and complexi-ty of these protocols were discussed. In addition, it was discussed the secure two-party and multiparty computations of malicious models. Some foundations and extended protocols were advanced which can be tolerated under the malicious behavior models.
安全多方计算(Secure Multiparty Computation, SMC)是指一组互不信任的参与者,在不泄露各自私有信息的前提下进行的多方合作计算。自图灵奖得主A. C. Yao于上世纪80年代提出安全多方计算的概念以来,已得到许多学者的研究,其在密码学上的地位也日渐重要,它是电子选举、电子拍卖等密码学协议的基础。安全多方计算拓展了传统的分布式计算以及信息安全的范畴,为网络协作计算开创了一种新的计算模式,对解决网络环境下的信息安全问题具有重要的现实意义。
安全多方计算的研究是一个极其复杂的工作,尤其对于特殊问题的研究远远没有达到理想的程度。在本文中,笔者将重点讨论有关科学计算领域的安全两方及多方计算协议的问题,其内容包括多项式的求值及乘法运算、初等函数的运算(除反三角函数外)、行列式求值、向量及矩阵的相关运算、解线性方程组等。文章对一些已有的半诚实模型下的安全两方计算协议进行推广,提出了一些的安全多方计算协议,并对各协议的正确性、安全性及复杂性进行了讨论。此外,本文还对恶意模型下的安全两方及多方计算进行了探讨,提出了几个可容忍恶意行为模型下的基础及扩展协议。
With the continuous development of network technology, and with the appearance of high quality computers and net grid, the meanings and mode of computations are mostly changed. Users can make use of the powerful computation resources to complete their computation tasks. Therefore in this environment, the safety of users'data become very important and necessary.
Secure Multi-party Computation (SMC) is a computation among a set of participants who do not have confidence in one another, in which participants collaborate on desired tasks but do not reveal private information of their own. Since it was initially suggested by A.C.Yao in the 1980s, SMC have been a major part of modern cryptography and attracted numerous researchers'interest. It's the basis of many distributed cryptographic protocols such as threshold cryptosystem, electronic voting and electronic auction, etc. Secure multi-party computation has extended the traditional distributed computation and information security areas. A new computation mode was created for network collaborative computation. It is very significant to solve the information security problems in the network environment.
Researches on the SMC are very complicated tasks. And researches on the special issues are far from ideal. In this paper, secure two-party and multiparty computation protocol problems were discussed which including polynomial evaluation and multiplication, elementary function operation (except inverse trigonometric function), determinant evalua-tion, vector and matrix related operation, solving linear equation and so on. Some existing secure two-party computation protocols of semi-honest models were generalized. A series of secure multiparty computation protocols were advanced. Correctness, security and complexi-ty of these protocols were discussed. In addition, it was discussed the secure two-party and multiparty computations of malicious models. Some foundations and extended protocols were advanced which can be tolerated under the malicious behavior models.
引文
[1]Shannon CE. Communication theory of secrecy systems. Bell System Technical. Journal,28,1949:pp.656-715.
[2]Diffie W, Hellman ME. New directions in cryptography. IEEE Transactions on Information Theory.1976,22(6):pp.644-654.
[3]W.Stallings. Cryptography and Network Security[M]. second edition. Prentice Hall, New Jersey,1998.
[4]A.Menezes.Van Oorschot and S.Vanstone. The Handbook of Applied Croptograph[M]. CRC Press, New York,1996.
[5]B.Schneier. Applied Cryptograph[M]. second edition. Prentice Hall,1996.
[6]A.C.Yao. Protocols for secure computations. In Proc.23rd IEEE Symp. On the Foundation of Computer Science. IEEE.1982:pp.160-164.
[7]O.Goldreich, S.Micali and A.Wigderson. How to play any mental game. In proc.19th ACM Symp. On the Theory of Computing.1987:pp.218-229.
[8]D.Chaum, C.Crepeau and I.Damgard. Multiparty unconditionally secure protocols (extended abstract). In Proc.20th ACM Symp. On the Theory of Computing.1988:pp.11-19.
[9]S.Goldwasser and L.Levin. Fair computation of general functions in presence of immoral majority. In Advances in Cryptology-CRYPTO'90 volume 537 of LNCS. Springer-Verlag,1990.
[10]O.Goldreich, S.Goldwasser and N.Linial. Fault-Tolerant Computation in the Full Information Model.32nd FOCS.1991:pp.447-457.
[11]R.Ostrovsky and M.Yung. How to withstand mobile virus attacks. Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing.1991:pp.51-59.
[12]S.Micali and P.Rogaway. Secure Computation. CRYPTO.1991.
[13]D.Beaver. Foundations of Secure Interactive Computing. CRYPTO.1991.
[14]M.Hirt, U.Maurer. Complete Characterization of Adversaries Tolerable in General Multiparty Computations. Proc.ACM POD'97. pp.25-34.
[15]Cramer, Damgard, Dziembowski, Hirt and Rabin. Multiparty Computations from Any Linear Secret Sharing Scheme. In:Proc.EUROCRYPT'00.
[16]秦静,张振峰,冯登国,李宝.一个特殊的安全双方计算协议.通信学报.2004,vo1.25 No.11.
[17]W.Du and M.J.Atallah. Privacy-preserving cooperative scientific computations. In 14th IEEE Computer Security Foundations Workshop, Nova Scotia, Canada, June 11-13 2001:pp.273-282.
[18]W.Du and M.J.Atallah. Secure multi-party computation problems and their applications:A review and open problems. In New Security Paradigms Workshop, Cloudcroft,New Mexico,USA, September 11-13 2001:pp.11-20.
[19]W.Du and Z.Zhan. A practical approach to solve secure multi-party computation problems. In Proceedings of New Security Paradigms Workshop, Virginia Beach,Virginia,USA, September 23-26 2002.
[20]罗文俊,李祥.多方安全保密科学计算的研究.计算机学报.2005年,第5期.
[21]Wenliang Du. A Study of Several Specific Secure Two-party Computation Problems. ph.D.Thesis. Purdue University.2000.
[22]Wenliang Du and Mikhail J.Atallah. Privacy-preserving Cooperative Statistical Analysis. In 2001 ACSAC:Annual Computer Security Applications Conference, New Orleans,Louisiana,USA, December 10-14 2001:pp.102-110.
[23]B.Chor and N.Giboa. Computationally private information retrieval (extended abstract). In Proceedings of the 29th Annual ACM symposium on theory of Computing, El Paso, TX USA, May 4-6 1997.
[24]C.Cachin, S.Micali and M.Stadler. Computationally private information retrieval with polylogarithmic communication. Advances in Cryptotogy:EUROCRYPT'99, Lecture Notes in Computer Science,1592:402-414,1999.
[25]G.Di-Crescenzo, Y.Ishai and R.Ostrovsky. Universal service-providers for database private information retrieval. In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing, September 21 1998.
[26]Y.Gertner, Y.Ishai, E.Kushilevitz and T.Malkin. Protecting data privacy in private information retrieval schemes. In Proceedings of the 30th Annual ACM symposium on Theory of computing, May 24-26 1998.
[27]Y.Ishai and E.Kushilevitz. Improved upper bounds on information-theoretic private information retrieval (extended abstract). In proceedings of the 31st Annual ACM symposium on theory of computing, Atlanta,GA USA, May 1-4 1999.
[28]O.Goldreich. Secure multi-party computation (working draft).
[29]WenJun Luo, Xiang Li. A Study of Secure Multi-Party Elementary Function Computation problem. Journal of communication and computer. USA.
[30]O.Goldreich. The Foundations of Cryptography-Volume 2,Basic Applications. Cambridge:Cambridge University Press 2004.
[31]李强.安全多方计算协议的研究与应用[D].上海交通大学,2003.
[32]Adi Shamir. How to share a secret. Communication of the Association for Computing Machinery. November 1979,22(11):612-613.
[33]G.R.Blakley. Safeguarding cryptographic keys. In Richard E.Merwin, Jacque-line T.Zanca and Merlin. Smith,editors,1979 National Computer Conference:June 4-7,1979, New York, volume 48 of AFIPS Conference preceedings, pp.313-317, Montvale,NJ,USA, 1979.AFIPS Press.
[34]Asmuth and Bloom. A modular approach to key safeguarding. IEEE Transactions on Information Theory,29,1983.
[35]M.E.Hellman, E.D.Karnin and J.W.Greene. On sharing secret systems. IEEE Transactions on Information Theory,29,1983.
[36]J.Benaloh and J.Leichter. Generalized secret sharing and monotone functions. Lecture Notes in Computer Science,27-35,1990.
[37]A Saito, M.Ito and T.Nishizeki. Multiple assignment scheme for sharing secret. Journal of Cryptology.1993, Vol.6, No.1.
[38]罗文俊,李祥.双向零知识证明与初等函数两方保密计算.贵州大学学报(自然科学版).Feb.2004,Vo1.21 No.1.
[39]荆巍巍,黄刘生,罗永龙,徐维江.一个安全两方共享秘密的乘法协议.小型微型计算机系统.2009,Vo1.30 No.3.
[40]罗文俊,李祥.多方安全矩阵乘法协议及应用.计算机学报July 2005, Vol.28No.7.
[41]刘铎,戴一奇.一个多方求特征值协议的分析与改进.北京电子科技学院学报.Dec.2007,Vo1.15 No.4.
[42]刘二根等.线性代数[M].南昌：江西高校出版社,1999.
[43]贾恒越,刘焕平.求矩阵逆的安全双方计算协议.计算机工程与应用.2008,44(33).
[44]王小妹.安全多方计算的协议研究[D].北京邮电大学,2008.
[45]张志芳.保护隐私的联合求解线性方程组.何大可,黄月江.中国密码学会2007年会,成都,2007.西南交通大学出版社,2007.
[46]罗文俊,李祥.矩阵特征值的两方安全保密计算.吉首大学学报(自然科学版).Dec.2003,Vo1.24 No.4.
[47]张华.安全多方计算及其应用研究[D].西安电子科技大学,2005.
[48]荆巍巍.安全多方计算中若干基础协议及应用的研究[D].中国科学技术大学,2008.
[49]杨方圆.安全多方计算的研究[D].山东大学,2007.
[50]董涛.安全多方计算的应用研究[D].解放军信息工程大学,2007.
[51]杨波.现代密码学.清华大学出版社,2003.
[52]Hans Delfs, Helmut Knebl. Introduction to Cryptography:Principles and Applications.肖国镇,张宁译.清华大学出版社,2008.
[53]William Stallings. Cryptography and Network Security:Principles and Practices.孟庆树,王丽娜,傅建明等译.第4版.电子工业出版社,2006.
[54]裴定一,徐祥.信息安全数学基础.人民邮电出版社,2007.
[55]孙世新.组合数学.第3版.电子科技大学出版社,2003.
[2]Diffie W, Hellman ME. New directions in cryptography. IEEE Transactions on Information Theory.1976,22(6):pp.644-654.
[3]W.Stallings. Cryptography and Network Security[M]. second edition. Prentice Hall, New Jersey,1998.
[4]A.Menezes.Van Oorschot and S.Vanstone. The Handbook of Applied Croptograph[M]. CRC Press, New York,1996.
[5]B.Schneier. Applied Cryptograph[M]. second edition. Prentice Hall,1996.
[6]A.C.Yao. Protocols for secure computations. In Proc.23rd IEEE Symp. On the Foundation of Computer Science. IEEE.1982:pp.160-164.
[7]O.Goldreich, S.Micali and A.Wigderson. How to play any mental game. In proc.19th ACM Symp. On the Theory of Computing.1987:pp.218-229.
[8]D.Chaum, C.Crepeau and I.Damgard. Multiparty unconditionally secure protocols (extended abstract). In Proc.20th ACM Symp. On the Theory of Computing.1988:pp.11-19.
[9]S.Goldwasser and L.Levin. Fair computation of general functions in presence of immoral majority. In Advances in Cryptology-CRYPTO'90 volume 537 of LNCS. Springer-Verlag,1990.
[10]O.Goldreich, S.Goldwasser and N.Linial. Fault-Tolerant Computation in the Full Information Model.32nd FOCS.1991:pp.447-457.
[11]R.Ostrovsky and M.Yung. How to withstand mobile virus attacks. Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing.1991:pp.51-59.
[12]S.Micali and P.Rogaway. Secure Computation. CRYPTO.1991.
[13]D.Beaver. Foundations of Secure Interactive Computing. CRYPTO.1991.
[14]M.Hirt, U.Maurer. Complete Characterization of Adversaries Tolerable in General Multiparty Computations. Proc.ACM POD'97. pp.25-34.
[15]Cramer, Damgard, Dziembowski, Hirt and Rabin. Multiparty Computations from Any Linear Secret Sharing Scheme. In:Proc.EUROCRYPT'00.
[16]秦静,张振峰,冯登国,李宝.一个特殊的安全双方计算协议.通信学报.2004,vo1.25 No.11.
[17]W.Du and M.J.Atallah. Privacy-preserving cooperative scientific computations. In 14th IEEE Computer Security Foundations Workshop, Nova Scotia, Canada, June 11-13 2001:pp.273-282.
[18]W.Du and M.J.Atallah. Secure multi-party computation problems and their applications:A review and open problems. In New Security Paradigms Workshop, Cloudcroft,New Mexico,USA, September 11-13 2001:pp.11-20.
[19]W.Du and Z.Zhan. A practical approach to solve secure multi-party computation problems. In Proceedings of New Security Paradigms Workshop, Virginia Beach,Virginia,USA, September 23-26 2002.
[20]罗文俊,李祥.多方安全保密科学计算的研究.计算机学报.2005年,第5期.
[21]Wenliang Du. A Study of Several Specific Secure Two-party Computation Problems. ph.D.Thesis. Purdue University.2000.
[22]Wenliang Du and Mikhail J.Atallah. Privacy-preserving Cooperative Statistical Analysis. In 2001 ACSAC:Annual Computer Security Applications Conference, New Orleans,Louisiana,USA, December 10-14 2001:pp.102-110.
[23]B.Chor and N.Giboa. Computationally private information retrieval (extended abstract). In Proceedings of the 29th Annual ACM symposium on theory of Computing, El Paso, TX USA, May 4-6 1997.
[24]C.Cachin, S.Micali and M.Stadler. Computationally private information retrieval with polylogarithmic communication. Advances in Cryptotogy:EUROCRYPT'99, Lecture Notes in Computer Science,1592:402-414,1999.
[25]G.Di-Crescenzo, Y.Ishai and R.Ostrovsky. Universal service-providers for database private information retrieval. In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing, September 21 1998.
[26]Y.Gertner, Y.Ishai, E.Kushilevitz and T.Malkin. Protecting data privacy in private information retrieval schemes. In Proceedings of the 30th Annual ACM symposium on Theory of computing, May 24-26 1998.
[27]Y.Ishai and E.Kushilevitz. Improved upper bounds on information-theoretic private information retrieval (extended abstract). In proceedings of the 31st Annual ACM symposium on theory of computing, Atlanta,GA USA, May 1-4 1999.
[28]O.Goldreich. Secure multi-party computation (working draft).
[29]WenJun Luo, Xiang Li. A Study of Secure Multi-Party Elementary Function Computation problem. Journal of communication and computer. USA.
[30]O.Goldreich. The Foundations of Cryptography-Volume 2,Basic Applications. Cambridge:Cambridge University Press 2004.
[31]李强.安全多方计算协议的研究与应用[D].上海交通大学,2003.
[32]Adi Shamir. How to share a secret. Communication of the Association for Computing Machinery. November 1979,22(11):612-613.
[33]G.R.Blakley. Safeguarding cryptographic keys. In Richard E.Merwin, Jacque-line T.Zanca and Merlin. Smith,editors,1979 National Computer Conference:June 4-7,1979, New York, volume 48 of AFIPS Conference preceedings, pp.313-317, Montvale,NJ,USA, 1979.AFIPS Press.
[34]Asmuth and Bloom. A modular approach to key safeguarding. IEEE Transactions on Information Theory,29,1983.
[35]M.E.Hellman, E.D.Karnin and J.W.Greene. On sharing secret systems. IEEE Transactions on Information Theory,29,1983.
[36]J.Benaloh and J.Leichter. Generalized secret sharing and monotone functions. Lecture Notes in Computer Science,27-35,1990.
[37]A Saito, M.Ito and T.Nishizeki. Multiple assignment scheme for sharing secret. Journal of Cryptology.1993, Vol.6, No.1.
[38]罗文俊,李祥.双向零知识证明与初等函数两方保密计算.贵州大学学报(自然科学版).Feb.2004,Vo1.21 No.1.
[39]荆巍巍,黄刘生,罗永龙,徐维江.一个安全两方共享秘密的乘法协议.小型微型计算机系统.2009,Vo1.30 No.3.
[40]罗文俊,李祥.多方安全矩阵乘法协议及应用.计算机学报July 2005, Vol.28No.7.
[41]刘铎,戴一奇.一个多方求特征值协议的分析与改进.北京电子科技学院学报.Dec.2007,Vo1.15 No.4.
[42]刘二根等.线性代数[M].南昌：江西高校出版社,1999.
[43]贾恒越,刘焕平.求矩阵逆的安全双方计算协议.计算机工程与应用.2008,44(33).
[44]王小妹.安全多方计算的协议研究[D].北京邮电大学,2008.
[45]张志芳.保护隐私的联合求解线性方程组.何大可,黄月江.中国密码学会2007年会,成都,2007.西南交通大学出版社,2007.
[46]罗文俊,李祥.矩阵特征值的两方安全保密计算.吉首大学学报(自然科学版).Dec.2003,Vo1.24 No.4.
[47]张华.安全多方计算及其应用研究[D].西安电子科技大学,2005.
[48]荆巍巍.安全多方计算中若干基础协议及应用的研究[D].中国科学技术大学,2008.
[49]杨方圆.安全多方计算的研究[D].山东大学,2007.
[50]董涛.安全多方计算的应用研究[D].解放军信息工程大学,2007.
[51]杨波.现代密码学.清华大学出版社,2003.
[52]Hans Delfs, Helmut Knebl. Introduction to Cryptography:Principles and Applications.肖国镇,张宁译.清华大学出版社,2008.
[53]William Stallings. Cryptography and Network Security:Principles and Practices.孟庆树,王丽娜,傅建明等译.第4版.电子工业出版社,2006.
[54]裴定一,徐祥.信息安全数学基础.人民邮电出版社,2007.
[55]孙世新.组合数学.第3版.电子科技大学出版社,2003.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |