LI Shun-dong1, YANG Xiao-li1, ZUO Xiang-jian1, ZHOU Su-fang1, KANG Jia1, LIU Xin1,2
1. School of Computer Science, Shaanxi Normal University, Xi'an, Shaanxi 710119, China;
2. School of Information Engineering, Inner Mongolia University of Science and Technology, Baotou, Inner Mongolia 014010, China
Abstract：At present,graphical similarity is limited to polygonal similarity,but the problem of general graphical similarity has not been studied.We first present protocols for privately determining whether two numbers,matrices or vectors are equal based on one-way hash function.Finally,we design protocols to privately determine whether two special graphics are isomorphic,and whether two graphics are similar.We prove the security of the protocols,implement them on a personal computer and analyze their efficiency.The simulation shows that the protocol of two similar graphics is 889 times as fast as the protocol of two similar polygons.Privately determining whether two graphs are similar is completely a new secure multiparty computation problem.It has application prospects in the field of the molecular biology,mechanical engineering and terrestrial matching,etc.
[1] Yao A.Protocols for secure computations[A].E Kushilevitz.Proceedings of the 23th IEEE Symposium on Foundations of Computer Science[C].Chicago:IEEE Press,1982.160-164.
[2] Goldreich O,et al.How to play any mental game[A].Alfred V.Aho.Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing[C].New York:ACM,1987.218-229.
[3] Goldreich O.Foundations of Cryptography:Basic Applications[M].London:Cambridge University Press,2004.599-764.
[4] Yasin S,et al.Cryptography based e-commerce security:a review[J].International Journal of Computer Science Issues,2012,9(2):132-137.
[5] Sharma R.Review paper on cryptography[J].International Journal of Research,2015,2(5):141-142.
[6] Kumar S N.Review on network security and cryptography[J].Science and Education,2015,3(1):1-11.
[7] Du W L,Atallah J.Secure multi-party computation problems and their applications:A review and open problems[A].B Timmerman.New Security Paradigms Workshop 2001[C].New York,USA:ACM,2001.11-20.
[8] Atallah M J,Du W.Secure Multi-party Computational Geometry[M].Berlin:Springer Berlin Heidelberg,2001.165-179.
[9] Li S D,DAI Y Q.Secure two-party computational geometry[J].Journal of Computer Science and Technology,2005,20(2):258-263.
[10] Li S D,WU C Y,et al.Secure multiparty computation of solid geometric problems and their applications[J].Information Sciences,2014,282:401-413.
[11] Li S D,Dai Y Q,et al.A secure multi-party computation solution to intersection problems of sets and rectangles[J].Progress in Natural Science,2006,16(5):538-545.
[12] Liu L,Chen X,Lou W.Secure three-party computational protocols for triangle area[J].International Journal of Information Security,2016,15(1):1-13.
[13] 王涛春,罗永龙,等.多边形相似判定中的私有信息保护[J].小型微型计算机系统,2012,33(2):383-387. Wang T C,Luo Y L,et al.Privacy-preserving in the determination of polygonal similarity[J].Journal of Chinese Computer Systems,2012,33(2):383-387.(in Chinese)
[14] 祝晓晖.基于几何图形相似仿真系统的设计与实现[D].四川:电子科技大学,2012. Zhu X H.The Design and Implementation of Simulation System Based on Geometry Similarity[D].Sichuan:University of Electronic Science and Technology of China,2012.
[15] Ionescu A,Leiss E L.On the role of complementation in implicit language equations and relations[J].Journal of Computer and System Sciences,2014,80(2):457-467.
[16] Li S D,Wang D S,Dai Y Q.Efficient secure multiparty computational geometry[J].Chinese Journal of Electronics,2010,19(2):324-328.
2017, Vol. 45 
