The millionaires' problem is an important problem in secure multiparty computation and a basic building block of secure multiparty computation protocols.Secure vector dominance statistic problem is a problem generalized for the millionaires' problem,which can be used to get the number of yi>xi without leaking further information.In this paper,we first propose an encoding scheme to encode private numbers; then based the new encoding scheme and homomorphic encryption scheme,we design a protocol for millionaires' problem and prove that the protocol is secure in the semi-honest model using the simulation paradigm.Then,we utilize this scheme to propose a solution to secure vector dominance statistic problem.The performance analysis indicates that our protocol is simpler and more efficient than the others.Finally,we use the scheme to solve the integer division problem and privately determine the relation between point and lines.
[1] C Yao.Protocols for secure computations[A].Proceedings of the 23th IEEE Symposium on Foundations of Computer Science[C].Chicago:IEEE Press,1982.160-164.
[2] Goldreich O,Micali S,Wigderson A.How to play any mental game[A].Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing[C].New York:ACM,1987.218-229.
[3] Goldreich O.Foundations of Cryptography:Volume 2,Basic Applications[M].London:Cambridge University Press,2004.599-764.
[4] Du W,Atallah M J.Privacy-preserving cooperative scientific computations[A].Proceedings of the 14th IEEE workshop on Computer Security Foundations[C].Canada:IEEE Computer Society,2001.273.
[5] Choi S G,Hwang K W,Katz J,et al.Secure Multi-Party Computation of Boolean Circuits with Applications to Privacy in On-line Marketplaces[M].Berlin:Springer Berlin Heidelberg,2012.416-432.
[6] Li Y,Chen M,Li Q,et al.Enabling multilevel trust in privacy preserving data mining[J].Knowledge and Data Engineering,IEEE Transactions on,2012,24(9):1598-1612.
[7] Toft T.Secure data structures based on multi-party computation[A].Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing[C].New York:ACM,2011.291-292.
[8] Loftus J,Smart N P.Secure Outsourced Computation[M].Progress in Cryptology-AFRICACRYPT 2011.Berlin:Springer Berlin Heidelberg,2011.1-20.
[9] A C Yao.How to generate and exchange secrets[A].Proceedings of 27th Annual Symposium on Foundations of Computer Science (FOCS'86)[C].Toronto:IEEE,1986.162-167.
[10] Ioannidis and A.Grama.An efficient protocol for Yao's millionaires' problem[A].Proceedings of the 36th Hawaii Interna-tional Conference on System Sciences[C].Hawaii:IEEE,2003.6-9.
[11] 秦静,张振峰,冯登国,李宝.无信息泄漏的比较协议[J].软件学报,2004,15(3):421-427. Qin Jing,Zhang Zhen-feng,Feng Deng-guo,Li Bao.A protocol of comparing information without leaking[J].Journal of Software,2004,15(3):421-427.(in Chinese)
[12] Sheikh R,Mishra D K,Kumar B.Secure multiparty computation:from millionaires problem to anonymizer[J].Information Security Journal:A Global Perspective,2011,20(1):25-33.
[13] Grigoriev D,Shpilrain V.Yao's millionaires' problem and decoy-based public key encryption by classical physics[J].International Journal of Foundations of Computer Science,2014,25(04):409-417.
[14] Karimian Ardestani N.Efficient Non-Interactive Secure Two-Party Computation for Equality and Comparison[D].Canada:University of Calgary,2015.
[15] Lipmaa H,Toft T.Secure Equality and Greater-Than Tests with Sublinear Online Complexity[M].Automata,Languages and Programming.Berlin:Springer Berlin Heidelberg,2013.645-656.
[16] Lin H Y,Tzeng W G.An efficient solution to the millionaires' problem based on homomorphic encryption[A].Applied Cryptography and Network Security[C].Berlin:Springer Berlin Heidelberg,2005.456-466.
[17] 李顺东,王道顺.基于同态加密的高效多方保密计算[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.(in Chinese)
[18] Atallah M J,Du W.Secure Multi-Party Computational Geometry[M].Algorithms and Data Structures.Berlin:Springer Berlin Heidelberg,2001.165-179.
[19] 刘文,罗守山,王永滨.安全两方向量优势统计协议及其应用[J].电子学报,2010,38(11):2573-2577. Liu Wen,Luo Shou-shan,Wang Yong-bin.Secure two-party vector dominance statistic protocol and Its application[J].Acta Electronica Sinica,2010,38(11):2573-2577.(in Chinese)
[20] 钱小强,仲红,石润华.无茫然第三方的安全两方向量优势统计协议[J].计算机工程,2014,40(2):148-152. Qian Xiao-qiang,Zhong Hong,Shi Run-hua.Secure two-party vector dominance statistic protocol without oblivious third party[J].Computer Engineering,2014,40(2):148-152.(in Chinese)
[21] Paillier P.Public-key cryptosystems based on composite degree residuosity classes[A].Advances in cryptology-EUROCRYPT'99[C].Berlin:Springer Berlin Heidelberg,1999.223-238.
2017, Vol. 45 
