保护私有信息的图形相似判定

doi:10.3969/j.issn.0372-2112.2017.09.019

电子学报 ›› 2017, Vol. 45 ›› Issue (9): 2184-2189.DOI: 10.3969/j.issn.0372-2112.2017.09.019

保护私有信息的图形相似判定

李顺东¹, 杨晓莉¹, 左祥建¹, 周素芳¹, 亢佳¹, 刘新^1,2

1. 陕西师范大学计算机科学学院, 陕西西安 710119;
2. 内蒙古科技大学信息工程学院, 内蒙古包头 014010

收稿日期:2016-08-07 修回日期:2016-10-19 出版日期:2017-09-25
- 作者简介:
- 李顺东,男,1963年生于河南平顶山.现为陕西师范大学计算机科学学院教授、博士生导师.主要研究方向为密码学与信息安全.E-mail:shundong@snnu.edu.cn;杨晓莉,女,1989年生于陕西商洛.现为陕西师范大学计算机科学学院硕士研究生.主要研究方向为密码学与信息安全.E-mail:xiaoliyang@snnu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61272435）; 内蒙古自然科学基金 (No.2017MS0602）; 中央高校基本科研业务费专项资金资助 (No.2016TS061）; 内蒙古自治区高等学校科学研究项目 (No.NJZY17164）

Privacy-Preserving Graphical Similarity Determination

LI Shun-dong¹, YANG Xiao-li¹, ZUO Xiang-jian¹, ZHOU Su-fang¹, KANG Jia¹, LIU Xin^1,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

Received:2016-08-07 Revised:2016-10-19 Online:2017-09-25 Published:2017-09-25
- Supported by:
- National Natural Science Foundation of China (No.61272435); Natural Science Foundation of Inner Mongolia Autonomous Region, China (No.2017MS0602); Fundamental Research Funds for the Central Universities (No.2016TS061); Scientific Research Project of Universities and Colleges in Inner Mongolia Autonomous Region (No.NJZY17164)

摘要/Abstract

摘要： 目前，关于几何图形的相似问题仅限于多边形的相似，而一般几何图形相似的问题还没有研究.本文利用单向散列函数首先设计了保密判断两个数是否相等的协议、保密矩阵和向量是否相等的协议；最终，利用矩阵和向量相等的协议设计了保密判断图形是否同构和图形是否相似的协议.给出了以上协议的安全性证明、仿真实验与效率分析，实验数据表明本文保密的图形相似判定协议效率是两个多边形相似协议效率的889倍.图形相似的保密判定问题是一个全新的安全多方计算几何问题，本文研究成果可应用在分子生物学、机械工程和地形匹配等领域.

关键词: 密码学, 安全多方计算, 计算几何, 图形相似, 图形同构

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.

Key words: cryptography, secure multi-party computation, computational geometry, graphics similar, graphics isomorphism

中图分类号:

TP302

李顺东, 杨晓莉, 左祥建, 等. 保护私有信息的图形相似判定[J]. 电子学报, 2017, 45(9): 2184-2189.

LI Shun-dong, YANG Xiao-li, ZUO Xiang-jian, et al. Privacy-Preserving Graphical Similarity Determination[J]. Acta Electronica Sinica, 2017, 45(9): 2184-2189.

参考文献

[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.

保护私有信息的图形相似判定

Privacy-Preserving Graphical Similarity Determination

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李顺东, 赵雪玲, 家珠亮. 集合交集元素和的保密计算[J]. 电子学报, 2023, 51(1): 86-92.
[2]	金紫凤, 潘思聪, 危辉. 可变环境下基于位姿变换矩阵的机器人无标定手眼协调方法[J]. 电子学报, 2022, 50(10): 2318-2328.
[3]	赵璐, 刘春红, 杜蛟, 曹天庆. Z₄上两类具有最优自相关四元序列的线性复杂度研究[J]. 电子学报, 2021, 49(4): 631-636.
[4]	汪榆淋, 窦家维. k-min问题安全多方计算方案及应用[J]. 电子学报, 2021, 49(11): 2256-2260.
[5]	窦家维, 王颖囡, 葛雪. 区间关系保密计算若干问题研究[J]. 电子学报, 2021, 49(1): 50-57.
[6]	陈露, 相峰, 孙知信. 基于属性密码体制的区块链安全技术研究进展[J]. 电子学报, 2021, 49(1): 192-200.
[7]	戚珉, 陈明. 标准模型下基于身份的混淆乐观公平交换方案[J]. 电子学报, 2020, 48(8): 1516-1527.
[8]	杨启良, 周彦伟, 杨坤伟, 王涛. 标准模型下可公开验证的匿名IBE方案的安全性分析[J]. 电子学报, 2020, 48(2): 291-295.
[9]	李顺东, 杜润萌, 杨颜璟, 魏琼. 有理数相等的保密判定[J]. 电子学报, 2020, 48(10): 1933-1937.
[10]	窦家维, 陈明艳. 多重集的保密计算及应用[J]. 电子学报, 2020, 48(1): 204-208.
[11]	杨小东, 王美丁, 裴喜祯, 李雨潼, 陈春霖, 麻婷春. 一种标准模型下无证书签名方案的安全性分析与改进[J]. 电子学报, 2019, 47(9): 1972-1978.
[12]	窦家维, 王文丽, 刘旭红, 李顺东. 有理区间的安全多方计算与应用[J]. 电子学报, 2018, 46(9): 2057-2062.
[13]	杜蛟, 刘春红, 张恩, 尚玉婧, 董乐. 基于拉丁方的GF(p)上q元旋转对称弹性函数的新构造[J]. 电子学报, 2018, 46(9): 2173-2180.
[14]	董丽华, 曾勇, 王春红, 胡予濮. LFCSR:基于FCSR的新密码学部件[J]. 电子学报, 2018, 46(8): 1924-1930.
[15]	窦家维, 李顺东. 数据相等问题的安全多方计算方案研究[J]. 电子学报, 2018, 46(5): 1107-1112.