一种实用高效的安全多方排序协议
|
摘要
安全多方排序问题是保护用户隐私的多方协作计算中最为重要的核心问题之一。为避免基于比较的排序方法,借鉴计数排序和桶排序的思想,把多方排序问题简化为多方求和问题。采用数据压缩及巧妙的编码方法,结合安全多方求和技术,发挥蒙特卡罗算法的优势,构造了一个安全实用的多方排序协议。该协议保证了解决安全多方排序问题的安全性、有效性、公平性。
Secure multi-party sorting is one of the most fundamental and key problems in the multi-party collaborative computation of protecting the privacy of the users. In this paper,we simplified multi-party sorting problem into multiparty sum problem by avoiding the sorting methods based on the comparison and following some good ideas from count sorting and bucket sorting. A secure and practical multi-party sorting protocol was constructed by using data compression and ingenious encoding methods,combining the secure multi-party summation technology and taking advantages of Monte Carlo algorithm. This protocol ensures the security,effectiveness and fairness of solving the secure multi-party sorting problem.
Secure multi-party sorting is one of the most fundamental and key problems in the multi-party collaborative computation of protecting the privacy of the users. In this paper,we simplified multi-party sorting problem into multiparty sum problem by avoiding the sorting methods based on the comparison and following some good ideas from count sorting and bucket sorting. A secure and practical multi-party sorting protocol was constructed by using data compression and ingenious encoding methods,combining the secure multi-party summation technology and taking advantages of Monte Carlo algorithm. This protocol ensures the security,effectiveness and fairness of solving the secure multi-party sorting problem.
引文
[1]Yao A C.Protocols for secure computation[C]//Proceedings of 23rd IEEE Symposium on the Foundation of Computer Science(FOCS).Los Alamitos,CA.IEEE,1982:160-164.
[2]Lin H Y,Tzeng W G.An Efficient Solution to the Millionaires’Problem Based on Homomorphic Encryption[C]//Proceedings of the Third international conference on Applied Cryptography and Network Security.Springer-Verlag,2005:456-466.
[3]李顺东,戴一奇,游启友.姚氏百万富翁问题的高效解决方案[J].电子学报,2005,33(5):769-773.
[4]杨婷婷,林昌露,刘忆宁,等.基于多方排序协议的安全电子投票方案[J].计算机系统应用,2015,24(8):25-32.
[5]孙溢.安全多方计算中若干应用协议的研究[D].北京:北京邮电大学,2015.
[6]李顺东,亢佳,杨晓艺,等.基于字符串排序的高效保密数据库查询[J].软件学报,2018,29(7):1-16.
[7]Jónsson K V,Kreitz G,Uddin M.Secure Multi-Party Sorting and Applications[C]//Proceedings of the 9th international conference on Applied Cryptography and Network Security(ACNS),2011.
[8]Goodrich M T.Randomized Shellsort:A Simple Data-Oblivious Sorting Algorithm[J].Journal of the Acm,2011,58(6):1-26.
[9]Zhang B.Generic constant-round oblivious sorting algorithm for MPC[C]//Proceedings of the 5th international conference on Provable security.Springer-Verlag,2011:240-256.
[10]Hamada K,Kikuchi R,Dai I,et al.Practically Efficient Multi-party Sorting Protocols from Comparison Sort Algorithms[C]//International Conference on Information Security and Cryptology.2012:202-216.
[11]刘文,罗守山,陈萍.利用EIGamal密码体制解决安全多方多数据排序问题[J].通信学报,2007,28(11):1-5.
[12]邱梅,罗守山,刘文,等.利用RSA密码体制解决安全多方多数据排序问题[J].电子学报,2009,37(5):1119-1123.
[13]李顺东,张选平.排序问题的多方保密计算协议[J].西安交通大学学报,2008,42(2):231-233,235.
[14]肖倩,罗守山,陈萍,等.半诚实模型下安全多方排序问题的研究[J].电子学报,2008,36(4):709-714
[15]唐春明,石桂花,姚正安.排序问题的安全多方计算协议[J].中国科学:信息科学,2011,41(7):789-797.
[16]潘金贵,顾铁成,曾俭,等.现代计算机常用数据结构和算法[M].南京:南京大学出版社,1994.
[17]Paillier P.Public-key cryptosystems based on composite degree residuosity classes[C]//Proceedings of the 17th international conference on Theory and application of cryptographic techniques.Springer-Verlag,1999:223-238.
[18]苏东,王克,吕克伟.Paillier陷门函数的两个变体的比特安全性分析[J].计算机学报,2010,33(6):1050-1059.
[19]石润华,仲红,崔杰,等.具有统计特性的不经意传输协议[J].电子学报,2014,42(11):2273-2279.
[2]Lin H Y,Tzeng W G.An Efficient Solution to the Millionaires’Problem Based on Homomorphic Encryption[C]//Proceedings of the Third international conference on Applied Cryptography and Network Security.Springer-Verlag,2005:456-466.
[3]李顺东,戴一奇,游启友.姚氏百万富翁问题的高效解决方案[J].电子学报,2005,33(5):769-773.
[4]杨婷婷,林昌露,刘忆宁,等.基于多方排序协议的安全电子投票方案[J].计算机系统应用,2015,24(8):25-32.
[5]孙溢.安全多方计算中若干应用协议的研究[D].北京:北京邮电大学,2015.
[6]李顺东,亢佳,杨晓艺,等.基于字符串排序的高效保密数据库查询[J].软件学报,2018,29(7):1-16.
[7]Jónsson K V,Kreitz G,Uddin M.Secure Multi-Party Sorting and Applications[C]//Proceedings of the 9th international conference on Applied Cryptography and Network Security(ACNS),2011.
[8]Goodrich M T.Randomized Shellsort:A Simple Data-Oblivious Sorting Algorithm[J].Journal of the Acm,2011,58(6):1-26.
[9]Zhang B.Generic constant-round oblivious sorting algorithm for MPC[C]//Proceedings of the 5th international conference on Provable security.Springer-Verlag,2011:240-256.
[10]Hamada K,Kikuchi R,Dai I,et al.Practically Efficient Multi-party Sorting Protocols from Comparison Sort Algorithms[C]//International Conference on Information Security and Cryptology.2012:202-216.
[11]刘文,罗守山,陈萍.利用EIGamal密码体制解决安全多方多数据排序问题[J].通信学报,2007,28(11):1-5.
[12]邱梅,罗守山,刘文,等.利用RSA密码体制解决安全多方多数据排序问题[J].电子学报,2009,37(5):1119-1123.
[13]李顺东,张选平.排序问题的多方保密计算协议[J].西安交通大学学报,2008,42(2):231-233,235.
[14]肖倩,罗守山,陈萍,等.半诚实模型下安全多方排序问题的研究[J].电子学报,2008,36(4):709-714
[15]唐春明,石桂花,姚正安.排序问题的安全多方计算协议[J].中国科学:信息科学,2011,41(7):789-797.
[16]潘金贵,顾铁成,曾俭,等.现代计算机常用数据结构和算法[M].南京:南京大学出版社,1994.
[17]Paillier P.Public-key cryptosystems based on composite degree residuosity classes[C]//Proceedings of the 17th international conference on Theory and application of cryptographic techniques.Springer-Verlag,1999:223-238.
[18]苏东,王克,吕克伟.Paillier陷门函数的两个变体的比特安全性分析[J].计算机学报,2010,33(6):1050-1059.
[19]石润华,仲红,崔杰,等.具有统计特性的不经意传输协议[J].电子学报,2014,42(11):2273-2279.