推荐星级：
- 1
- 2
- 3
- 4
- 5
保护私有信息的图形相似判定
资料介绍
目前,关于几何图形的相似问题仅限于多边形的相似,而一般几何图形相似的问题还没有研究.本文利用单向散列函数首先设计了保密判断两个数是否相等的协议、保密矩阵和向量是否相等的协议;最终,利用矩阵和向量相等的协议设计了保密判断图形是否同构和图形是否相似的协议.给出了以上协议的安全性证明、仿真实验与效率分析,实验数据表明本文保密的图形相似判定协议效率是两个多边形相似协议效率的889倍.图形相似的保密判定问题是一个全新的安全多方计算几何问题,本文研究成果可应用在分子生物学、机械工程和地形匹配等领域.
部分文件列表
| 文件名 | 大小 |
| 保护私有信息的图形相似判定.pdf | 704K |
部分页面预览
（完整内容请下载后查看）9
Vol． 45 No． 9
Sep． 2017
第
期
电
子
学
报
2017
9
ACTA ELECTRONICA SINICA
年
月
保护私有信息的图形相似判定
1
1
1
1
1
1，2
，
，
，
，
，
李顺东 杨晓莉 左祥建 周素芳 亢 佳 刘 新
( 1．
，
710119; 2．
，
014010)
陕西师范大学计算机科学学院 陕西西安
内蒙古科技大学信息工程学院 内蒙古包头
:
， ，
．
摘
要
目前 关于几何图形的相似问题仅限于多边形的相似 而一般几何图形相似的问题还没有研究 本文利
、
;
，
用单向散列函数首先设计了保密判断两个数是否相等的协议 保密矩阵和向量是否相等的协议 最终 利用矩阵和向
． 、
量相等的协议设计了保密判断图形是否同构和图形是否相似的协议 给出了以上协议的安全性证明 仿真实验与效率
，
分析 实验数据表明本文保密的图形相似判定协议效率是两个多边形相似协议效率的
889
．
倍 图形相似的保密判定问
，
、
题是一个全新的安全多方计算几何问题 本文研究成果可应用在分子生物学 机械工程和地形匹配等领域
．
:
;
;
;
;
关键词
中图分类号
URL: http: / /www． ejournal． org． cn
密码学 安全多方计算 计算几何 图形相似 图形同构
TP302
0372-2112 ( 2017) 09-2184-06
DOI: 10． 3969 /j． issn． 0372-2112． 2017． 09． 019
:
:
A
:
文章编号
文献标识码
电子学报
Privacy-Preserving Graphical Similarity Determination
1
1
1
1
1
1，2
LI Shun-dong ，YANG Xiao-li ，ZUO Xiang-jian ，ZHOU Su-fang ，KANG Jia ，LIU Xin
( 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 simi-
larity 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 i-
somorphic，and whether two graphics are similar． We prove the security of the protocols，implement them on a personal com-
puter 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 iso-
morphism
［7］
tional Geometry，SMCG)
，
主
是安全多方计算的新领域
1
引言
，
要研究计算几何的信息安全问题 尤其是分布式系统
，SMCG
安全多方计算由图灵奖获得者姚期智教授首次提
．
中合作用户的隐私数据保护问题 具体地说
问
出［1］ 经过了
等人的发展
［2，3］
，
Goldreich，Micali
，
成为近
，
题的研究就是要设计出相应的协议 使用户能够保密
年密码学研究的热点问题之一［4 ～ 6］ 安全多方计算是信
．
．
地解决某些计算几何问题
，
息社会隐私保护的重要技术 它使拥有私有数据的参
，
［7，8］
在保密的计算几何方面 文献 提出了安全多
，
与者能够合作利用这些私有数据进行某些联合计算
、
;
［9］
方点包含问题 两个凸多边形相交问题 文献 研究
，
同时又不泄露自己的私有数据 因而使人们能够最大
;
［10］
了两方的点包含问题 文献 研究了保密的几何距
．
限度地利用私有数据而不破坏数据的隐私性
;
［11］
;
离计算问题 文献 研究了多边形的点包含问题 文
( Secure Multiparty Computa-
保护隐私的计算几何
［12］ ［13］
;
献
研究了安全的多边形面积计算问题 文献
: 2016-08-07;
: 2016-10-19; :
责任编辑 覃怀银
收稿日期
修回日期
:
( No． 61272435) ;
( No． 2017MS0602) ;
( No．
中央高校基本科研业 务费专项资金资助
基金项目 国家自然科学基金
内蒙古自然科学基金
( No． NJZY17164)
2016TS061) ;
内蒙古自治区高等学校科学研究项目
2185
9
:
李顺东 保护私有信息的图形相似判定
第
期
．
研究了多边形相似问题 但关于相似问题的安全多方
b，
a
b．
有一个数 他们想保密比较 是否等于 即如果
a
≠
b， a，b
比较过程不泄露
．
;
的任何信息
计算研究仍然是初步的 关于几何图形的相似问题仅
限于多边形的相似［13］ 而一般几何图形相似的问题还
: Alice Bob
r
．
具体方案如下
m
和
分别任意选择随机数
c = a
n
{ 0，1} ，s { 0，1} ( m，n ＞ 64) ，Alice
∈
r，
⊕
．
没有研究 但一般几何图形的相似有更广泛的应用
．
∈
计算
Bob; Bob
d = b s，
⊕ 发送给
'
Alice; Alice
发送给
计算
r，Bob
计算
，
随着几何图形检索技术迅速发展 其实用价值逐
'
a = d
r = b
s
b = c
s = a
r s．
⊕
⊕
⊕
计算
⊕
⊕ ⊕
'
，
、
、
步显现 在生物分子 机械零件 地形匹配等领域都得到
了广泛应用［14］ 都用到了图形相似问题的判定 要进行
'
'
Alice
Bob
a ，b
，
hash( a ) ，
和
'
分别对
进行哈希运算 得到
，
．
'
'
hash( b )
．
hash( a ) = hash( b ) ， a = b;
那么
并交换 如果
，a b． :
为叙述简单定义一个二元谓词如下
，
，
保密几何图形检索 就要保密判断图形是否相似 用判
否则
≠
断是否全等来判断是否为同一个对象将得出非同一对
0，
如果
a = b;
a b.
．
，
象的错误结论 因此 研究保密判断图形相似的问题是
P( a，b) =
{
1，
如果 ≠
．
十分必要的
2
预备知识
1
协议
保密数相等判定协议
字母表与连接运算［15］
2. 1
: Alice
a，Bob
输入
b.
输入
输出
输入
M，M
n
字母表是对象的有穷非空集合
中符号的
元
: P( a，b) .
( 1) Alice
m
{ 0，1} ，s { 0，1}
∈
n
M
组称作 上的字或字符串
*
，M
中所有字符串的全体记
Bob
r
和
分别任意选择随机数
∈
( m，n ＞ 64) ，
计算
c = a
r，d = b
s， c，d．
并交换
⊕
⊕
'
a = d
M ， 0，1，2，···，9
，
作
例如 所有的自然数都是 字母
'
( 2) Alice
Bob
r = b
s
r，b = c
⊕
s = a
和
分别计算
⊕
⊕
⊕
，
0，1
字母表上的字
表上的字符串 所有的二进制数都是
r
s．
⊕
⊕
，
符串 字符串的连接定义如下
1
:
'
'
'
( 3) Alice
Bob
a ，b
， hash( a ) ，
进行哈希运算 得到
和
分别对
Concat ( u) = u，
m + 1
'
n
hash( b )
( 4)
．
并交换
{
∈
'
'
Concat ( u ，…，u ，u ) = zu
.
hash( a ) = hash( b ) ，
输出
P( a，b) = 0;
，
否则 输出
如果
n
1
m
m + 1
m + 1
m
P( a，b) = 1．
z = Concat ( u ，…，u ) ，
其中
对于给定的字符串
n
1
m
*
m
u ，…，u
M ，Concat ( u ，…，u )
u ，
就是把字符串
1
m
n
1
m
1
1
1
保密数相等判定协议 是安全的
．
定理
…，u
．
一个接着一个放在一起所得到的新的字符串
m
( 1)
( 2)
成立的模拟器
证明 通过构造使等式
和
2. 2
安全性定义
S 、S
1
．
证明本定理
2
半诚实参与者［16］本文方案均假设安全多方计算的
在本方案中
π
． ，
参与者为半诚实参与者 简单地说 所谓半诚实参与者
'
'
'
view ( a，b) = ( a，r，d，a ，( hash( a ) ，hash( b ) ) ，P( a，b) )
1
是指参与者在协议执行过程中将不折不扣地执行协
π
π
f ( a，b) = f ( a，b) = output ( a，b) = output ( a，b) = P( a，b)
1
2
1
2
，
议 但他们也会保留计算的中间结果试图推导出其他
: a，b
Alice
Bob
，r Alice
的输入 是 选
其中
分别是
和
．
参与者的输入
［3］
'
'
，a ，hash ( a )
Alice
，d，
计 算 的 结 果
择的 随 机 数
hash( b') Bob
π
是
1
(
)
定义
f，
半诚实参与者的保密性
对于一个函
S (
也称这样
Alice
．
的数 首先构造
S
是
发送给
( 1)
来模拟
1
S
数
如果存在概率多项式时间算法
与
1
2
view ( a，b)
．
:
使得式
成立 模拟过程如下
f ( a，b) ，
的值 选
1
)
的多项式时间算法为模拟器 使得
c
( 1)
( a，f ( a，b) ) ，
接受输入
根据
1
1
π
π
{ S ( x，f ( x，y) ) ，f ( x，y) }
{ view ( x，y) ，output ( x，y) }
x，y
≡
1
1
2
x，y
x，y
1
2
b ，
f ( a，b ) = f ( a，b) = P( a，b) ，
定数
使得
m
选择随机数
1
1
1
1
'
'
'
( 1)
s
{ 0，1} ，S
c = a
r，d = b
s ．
∈
计算
'
⊕
⊕
1
1
c
'
'
'
'
π
π
( 2) S
a = d
1
r = b
s
r，hash( a ) ，b =
⊕
计算
⊕
⊕
{ f ( x，y) ，S ( y，f ( x，y) ) }
{ output ( x，y) ，view ( x，y) }
x，y
≡
1
1
1
1
1
2
2
1
2
'
'
'
c
s = a
r
s ，hash( b ) ．
⊕
'
⊕
⊕
( 2)
1
'
c
( 3) S
hash( a )
hash( b )
通过比较
和
是否相等来
1
1
1
．
其中≡表示计算上不可区分 则认为 π 保密地计算
f．
a
b
．
是否相等 令
比较
和
1
，
要证明一个多方计算方案是保密的 就必须构造
'
'
'
'
S ( a，f ( a，b) ) = { a，r，d ，a ，( hash( a ) ，hash( b ) ) ，
1
1
1
1
1
( 1) ( 2)
和
S
S ．
2
满足式
的模拟器
与
1
P( a，b) } ，
3
图形相似协议
因为
c
c
c
c
'
'
'
'
'
'
'
3. 1
d
d ，a a ，hash( a ) hash( a ) ，hash( b ) hash( b ) ，
基于对称加密算法的保密数相等判定协议
Alice
a，Bob
≡
≡
≡
≡
1
1
1
比较两个数是否相等问题
有一个数
所以
更多>>
最新上传
- 打赏
- 30日榜单
-
21ic小能手 打赏10.00元 2天前
-
21ic小能手 打赏10.00元 2天前
-
cai0603 打赏3.00元 3天前
用户：CJQ_ENJOY
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
cai0603 打赏3.00元 3天前
用户：dongshao
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
21ic下载 打赏310.00元 3天前
用户：gsy幸运
-
21ic下载 打赏310.00元 3天前
用户：zhengdai
-
21ic下载 打赏310.00元 3天前
用户：小猫做电路
-
21ic下载 打赏310.00元 3天前
用户：liqiang9090
-
21ic下载 打赏270.00元 3天前
用户：kk1957135547
-
21ic下载 打赏160.00元 3天前
用户：w178191520
-
21ic下载 打赏160.00元 3天前
用户：w1966891335
-
21ic下载 打赏50.00元 3天前
用户：w993263495
-
21ic下载 打赏40.00元 3天前
用户：w993263495
-
21ic下载 打赏90.00元 3天前
用户：cooldog123pp
-
21ic下载 打赏30.00元 3天前
用户：sun2152
-
21ic下载 打赏40.00元 3天前
用户：xzxbybd
-
21ic下载 打赏40.00元 3天前
用户：铁蛋锅
-
21ic下载 打赏30.00元 3天前
用户：happypcb
-
21ic下载 打赏50.00元 3天前
用户：forgot
-
21ic下载 打赏10.00元 3天前
用户：xuzhen1
-
21ic下载 打赏20.00元 3天前
用户：wanglu6666
-
21ic下载 打赏5.00元 3天前
用户：人间留客
-
21ic下载 打赏5.00元 3天前
用户：jyxjiyixing
-
21ic下载 打赏5.00元 3天前
用户：akae_du
-
21ic下载 打赏5.00元 3天前
用户：ouyang_56
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
xlhtracy 打赏10.00元 3天前
-
xlhtracy 打赏10.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
xlhtracy 打赏5.00元 3天前
-
czmhcy 打赏1.00元 3天前
资料：bitboy
全部评论(0)