PDF《两个保密位置判断问题的新解法》

第4 1卷第2期2018年2月计算机学报CH I N E S EJ OUR NA LO FC OMP UT E R S V o l .

4 1 N o .

2 F e b .

2 0

1 8 收稿日期:

2 0

1 6

0 9

2 8 ;

在线出版日期:

2 0

1 7

0 5

1 0 . 本课题得到国家自然科学基金(

6 1

4 7

2 1

4 6 ) 、 陕西 省自然科学基础研究计划面上项目(2017JM6069)、信息安全国家重点实 验室开放课题基金(2016MS19) 、 广西可信软件重点实验室研究课题资助(kx201614) 资助. 陈振华, 女,

1 9

7 6年生, 副教授, 硕士生导师, 研究领域为密码学与信息安全. E m a i l : c h e n z h e n h u a @s n n u. e d u. c n. 李顺东, 男,

1 9

6 3年生, 教授, 博士生导师, 主要研究领域为密码学和信息安全. 黄琼, 男,

1 9

8 2年生, 教授, 硕士生导师, 主要研究领域为密码学和信息安全. 董立红, 女,

1 9

6 8年生, 教授, 硕士生导师, 主要研究领域为系统工程. 陈娓, 女,

1 9

9 2年生, 硕士研究生, 主要研究方向为密码学和信息安全. 两个保密位置判断问题的新解法 陈振华1) ,

2 ) , 3) 李顺东4 ) 黄琼5 ) 董立红1 ) 陈娓1 ) 1) ( 西安科技大学计算机科学与技术学院 西安

7 1

0 0

5 4 ) 2) ( 中国科学院信息工程研究所信息安全国家重点实验室 北京

1 0

0 0

9 3 ) 3) ( 桂林电子科技大学广西可信软件重点实验室 广西 桂林

5 4

1 0

0 4 ) 4) ( 陕西师范大学计算机科学学院 西安

7 1

0 0

6 2 ) 5) ( 华南农业大学数学与信息学院 广州

5 1

0 6

4 2 ) 摘要保护隐私的位置判断是一种具体的安全多方计算几何问题, 这种问题是指各个参与者位于平面或者空间 中的一个位置, 在保持各自输入隐私的条件下, 判断他们之间的相对位置. 点包含问题是保密判断一个点是否落在 一个凸多边形的内部;

两组数据对应成比例问题可保密判断空间中两个平面或直线是否平行, 这两个问题同属于 安全多方几何计算中保护隐私的位置判断问题. 目前该两个问题的已存方案由于转化方法的问题, 并不太高效, 因 此研究如何构造高效协议有着重要的意义. 针对这个问题, 该文首先将点包含问题转化为三角形面积问题;

将两组 数据对应成比例问题转化为向量共线问题, 然后基于内积协议解决了这两个问题. 最后, 将该文的两个协议作为基 础协议, 分别给出了三个应用: 保密判断凸多边形包含、 三角形相似、 空间几何对象的相对位置. 最后的分析显示, 相比以往的方案, 作者的转化技巧是全新的, 避免了以往方案中多个基础协议的使用和循环语句的不断调用的缺 陷, 这使得方案更加简洁, 效率得到了提高. 关键词 安全多方计算;

点包含;

数据对应成比例;

内积;

位置关系判断 中图法分类号 T P

3 0

9 珊

1 0.

1 1

8 9

7 / S P. J .

1 0

1 6.

2 0

1 8.

0 0

3 3

6 荦骼 镒 樽 镒椽镒 樽樽 CHE NZ h e n H u a

1 ) ,

2 ) , 3) L IS h u n D o n g

4 ) HUANG Q i o n g

5 ) D ONGL i H o n g

1 ) CHE N W e i

1 ) 1) ( 犁 蚶 遄 状 枳, '

嶙 状 胬 遄 状 枳, '

嶙710054)2) ( 犁 状镒蠢 , 勺 状镒 状樽樽, 樽 胬 遄, 樽100093)3) ( 嶙 淅 , 樽 状 镒 枳, 樽, 嶙541004)4) ( 犁 蚶 遄, 犁嶙檐 状, '

嶙710062)5) ( 状 状, 犁 樽 状, 嶙510642)Privacypreservingl o c a t i o n r e l a t i o nd e t e r m i n a t i o na sas p e c i f i cs e c u r ec o m p u t a t i o n g e o m e t r y i s s u er e f e r st ot h a te a c hp a r t i c i p a n tl o c a t e sa tac e r t a i np o s i t i o ni nt h ep l a n eo rt h e s p a c e ,w h oc a nd e t e r m i n e t h e r e l a t i v e l o c a t i o na m o n g t h e m, w h i l ek e e p i n g i n d i v i d u a l p r i v a t e i n p u t s . P r i v a c y p r e s e r v i n g l o c a t i o n r e l a t i o nd e t e r m i n a t i o na s a ne s s e n t i a l f i e l d i ns e c u r e c o m p u t a t i o ng e o m e t r y h a sm a n ya p p l i c a t i o n si nr e a lw o r l da n dl o c a t i o n b a s e ds e r v i c e s m e a n w h i l ep r o t e c t i n g u s e r '