Computer Science ›› 2016, Vol. 43 ›› Issue (1): 181-185.doi: 10.11896/j.issn.1002-137X.2016.01.041

Previous Articles     Next Articles

Efficient Solution to SMP Based on Coding and Homomorphic Encryption

TANG Xuan, ZHONG Hong, SHI Run-hua and CUI Jie   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Socialist millionaires’ problem(SMP) is the problem of two millionaires wanting to know whether they are equally rich,whose solutions can be used to build the basic protocol in many application systems.Firstly,we presented a new encoding scheme to encode private data.And then based on this encoding scheme and the ElGamal homomorphic encryption algorithm,we designed a creative scheme for socialist millionaires’ problem.The validity,security and efficiency were analyzed.Finally,the comparison of protocols indicates that our scheme has high efficiency.

Key words: Secure multi-party computation,Socialist millionaires’ problem(SMP),Encoding,Homomorphic encryption

[1] Yao A C.Protocol for Secure Computations[C]∥2013 IEEE54th Annual Symposium on Foundations of Computer Science.Los Alamitos:IEEE,1982:160-164
[2] Cachin C.Efficient private bidding and auctions with an obli-vious third party[C]∥Proceedings of the 6th ACM Conference on Computer and Communications Security.NY:ACM,1999:120-127
[3] Qin Jing,Zhang Zhen-feng,Feng Deng-guo,et al.A protocol of specific secure two-party computation[J].Journal of China Institute of Communications,2004,5(11):35-42(in Chinese)秦静,张振峰,冯登国,等.一个特殊的安全多方计算协议[J].通信学报,2004,5(11):35-42
[4] Ioannidis I,Grama A.An efficient protocol for Yao’s millionai-res problem[C]∥ Proceedings of the 36th Annual Hawaii International Conference on System Sciences.Hawaii:IEEE,2003:205a
[5] Li Shun-dong,Dai Yi-qi,You Qi-you.An Efficient Solution to Yao’s Millionaires’ Problem[J].Acta Electronica Sinica,2005,3(5):769-773(in Chinese)李顺东,戴一奇,游启友.姚氏百万富翁问题的高效解决方案[J].电子学报,2005,3(5):769-773
[6] 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.NewYork:Springer Berlin Heidelberg,2005:456-466
[7] Qin Bo,Qin Hui,Zhou Ke-fu,et al.Millionaires’ protocol with constant complexity[J].Journal of Xi’an University of Techno-logy,2005,1(2):149-152(in Chinese)秦波,秦慧,周克复,等.常数复杂性的百万富翁协议[J].西安理工大学学报,2005,1(2):149-152
[8] Li Shun-dong,Wang Dao-shun.Efficient Secure Multiparty Com-putation Based on Homomorphic Encryption[J].Acta Electronica Sinica,2013,41(4):798-803(in Chinese)李顺东,王道顺.基于同态加密的高效多方保密计算[J].电子学报,2013,41(4):798-803
[9] Schoenmakers B,Tuyls P.Practical two-party computationbased on the conditional gate[M]∥Advances in Cryptology-ASIACRYPT 2004.Springer Berlin Heidelberg,2004:119-136
[10] Fagin R,Naor M,Winkler P.Comparing information withoutleaking it [J].Communications of the ACM,1996,9(5):77-85
[11] Jakobsson M,Yung M.Proving Without Knowing:On Obli-vious,Agnostic and Blindfolded Provers[C]∥Proceedings of Advances in Cryptology-CRYPTO’96.Springer-Verlag,1996:186-200
[12] Boudot F,Schoenmakers B,Traoré J.A Fair and Efficient Solution to the Socialist Millionaires' Problem [J].Discrete Applied Mathematics,2001,1(1):23-36
[13] Qin Jing,Zhang Zhen-feng,Feng Deng-guo,et al.A protocol of comparing information without leaking [J].Journal of Software,2004,5(3):421-427(in Chinese)秦静,张振峰,冯登国,等.无信息泄露的比较协议[J].软件学报,2004,5(3):421-427
[14] Liu Wen,Luo Shou-shan,Chen Ping.Solution to SMP Based on Sliding Window and Commutation Encryption Function[J].Computer Engineering,2007,33(22):163-171(in Chinese)刘文,罗守山,陈萍.基于滑动窗口和交换加密函数解决SMP的新方案[J].计算机工程,2007,33(22):163-171
[15] Xiao Qian,Luo Shou-shan,Chen Ping,et al.Research on the Problem of Secure Multi-party Ranking Under Semi-honest Model[J].Acta Electronica Sinica,2008,6(4):709-714(in Chinese)肖倩,罗守山,陈萍,等.半诚实模型下安全多方排序问题的研究[J].电子学报,2008,6(4):709-714
[16] Liu Wen,Wang Yong-bin.Secure multi-party comparing protocol and its applications[J].Acta Electronica Sinica,2012,0(5):871-876(in Chinese)刘文,王永滨.安全多方比较相等协议及其应用[J].电子学报,2012,0(5):871-876
[17] Goldreich O.The Fundamental of Cryptography:Basic Applications[M].London:Cambridge University Press,2004
[18] Goldreich O.Secure multi-party computation(Manuscript.Preliminary version)[Z].1998

No related articles found!
Full text



No Suggested Reading articles found!