Privacy-Preserving Graphical Similarity Determination

LI Shun-dong; YANG Xiao-li; ZUO Xiang-jian; ZHOU Su-fang; KANG Jia; LIU Xin

doi:10.3969/j.issn.0372-2112.2017.09.019

您当前的位置：

首页 >

文章列表页 >

Privacy-Preserving Graphical Similarity Determination

更新时间：2025-07-16

- Privacy-Preserving Graphical Similarity Determination
- Acta Electronica Sinica Vol. 45, Issue 9, Pages: 2184-2189(2017)
- 作者机构：
  
  1. 陕西师范大学计算机科学学院,陕西,西安,710119
  2. 内蒙古科技大学信息工程学院,内蒙古,包头,014010
  3. 陕西师范大学计算机科学学院,陕西,西安,710119
  4. 内蒙古科技大学信息工程学院,内蒙古,包头,014010
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2017.09.019
  CLC： TP302
- Published Online：25 September 2017，
  
  Published：2017
- 稿件说明：
移动端阅览
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.
DOI：

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. DOI： 10.3969/j.issn.0372-2112.2017.09.019.

摘要

目前，关于几何图形的相似问题仅限于多边形的相似，而一般几何图形相似的问题还没有研究.本文利用单向散列函数首先设计了保密判断两个数是否相等的协议、保密矩阵和向量是否相等的协议；最终，利用矩阵和向量相等的协议设计了保密判断图形是否同构和图形是否相似的协议.给出了以上协议的安全性证明、仿真实验与效率分析，实验数据表明本文保密的图形相似判定协议效率是两个多边形相似协议效率的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.

关键词

Keywords

references

Views

285

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Secure Computation of Subsets from Tuple Sets

Maximum Value of Sum of Intersection Elements of Secret Calculation

A Protocol for Privacy-Preserving Intersect-Determination of Two Polygons

Secure Multi-Party Computation for Minimum and Its Applications

Related Author

LI Shun-dong

DU Ji-xin

YU Jia-tong

WU Chuan-yu

MA Xiu-lian

ZHANG Juan-juan

LI Shun-dong

LUO Yong-long

Related Institution

School of Computer Science， Shaanxi Normal University

Department of Computer Science,University of Science and Technology of China

Department of Computer Science,Anhui Normal University

Department of Computer ScienceUniversity of Science and Technology of ChinaHefeiAnhui 230027China

Department of Computer ScienceAnhui Normal UniversityWuhuAnhui 241000China

⁰