点和区间关系的全隐私保密判定

《点和区间关系的全隐私保密判定》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中国科学:信息科学2018年第48卷第2期:187–204SCIENTIASINICAInformationis论文点和区间关系的全隐私保密判定1,2,3*4151陈振华,李顺东,陈立朝,黄琼,张卫国1.西安科技大学计算机科学与技术学院,西安7100542.中国科学院信息工程研究所信息安全国家重点实验室,北京1000933.桂林电子科技大学广西可信软件重点实验室,桂林5410044.陕西师范大学计算机科学学院,西安7100625.华南农业大学数学与信息学院,广州510642*通信作者.E-mail:chenzhenhua@snnu.edu.cn收稿日期:2017–6–13;接受日期

2、:2017–9–13;网络出版日期:2018–01–08国家自然科学基基金(批准号:61272435)、信息安全国家重点实验室开放课题基金(批准号:2016-MS-19)、广西可信软件重点实验室研究课题资助(批准号:kx201614)和陕西省自然科学基础研究计划面上项目(批准号:2017JM6069)资助摘要点和区间关系的保密判定在范围查询中应用非常广泛,但目前已存的解决方案大多只保护了一方的隐私,而另一方的隐私并未得到保护.此外,已存方案给出的点和区间都是离散的整数(或有理数)范围.针对这些问题,本文利用安全多方计算的思想设计了保密判定点和区间关系的2种协议,不但同时保护了两方的

3、隐私,而且将数域推广到连续的实数.本文首先利用0-1编码并结合Goldwasser-Micali同态加密给出了全隐私判定一个整数点是否在一个离散整数区间上的协议1;然后利用函数的单调性和Paillier同态加密给出了全隐私判定一个实数点是否在一个连续实数区间的协议2.最后,给出了本文协议的一个应用实例.理论和实验分析显示:本文的两个协议在取得较优通信效率的同时都取得了全隐私性.此外,协议2相比以往的方案,第一次给出点和连续实数区间的判定方法,在保持较优效率和良好性能的同时取得了通用性.关键词点和区间,全隐私,安全多方计算,实数,同态加密1引言安全多方计算最早由Yao[1]提出,是指

4、在不泄漏各方的输入数据(隐私性)的条件下,正确完成输入数据的函数计算(正确性).现实问题中涉及到保护隐私的合作计算都可以归结到安全多方计算的范围.因此它在保护隐私的质量评估[2]、定位查找[3]、数据挖掘[4]、数据查询[5]、外包计算[6]等方面有着广泛的应用.点和区间关系的保密判定,是指在保护一方(或两方)隐私的情况下,判断一方的点是否包含在另一方区间中.这个问题是密文搜索中常需嵌入的属性关系问题,在保护隐私的范围查询或定位搜索中引用格式:陈振华,李顺东,陈立朝,等.点和区间关系的全隐私保密判定.中国科学:信息科学,2018,48:187{204,doi:10.1360/N11

5、2017-00025ChenZH,LiSD,ChenLC,etal.Fullyprivacy-preservingdeterminationofpoint-rangerelationship(inChinese).SciSinInform,2018,48:187{204,doi:10.1360/N112017-00025⃝c2018《中国科学》杂志社www.scichina.cominfocn.scichina.com陈振华等:点和区间关系的全隐私保密判定有着非常广泛的应用.例如,2007年,Boneh等[7]提出了一种搜索加密方案,只有满足一定大小关系的目标密文才可以被搜索到.这

6、个方案推广后可以进行区间查询,即只有满足点和区间包含关系的目标密文才可以被搜索到,从而进一步解密目标密文.但这个方案中,只有点的隐私得到了保护,而区间隐私并没有得到保护.2013年,Wen等[8]提出了一种可以直接进行区间查询的搜索方案,应用在智能电网中.这个方案中点和区间的隐私都得到了保护,但却和Boneh等[7]的方案一样,所判断的点和区间都是离散的整数.若在以上方案中能进行点和区间关系的全隐私保密判定,即在判定点和区间关系时,两方(点和区间)的隐私都得到保护,就能提高方案中用户的隐私性.与此同时,将点和区间的范围从离散的整数推广到连续的实数,就能更好地扩大这些方案的应用,从而

7、丰富公钥密码学的体制和应用.因此,本文对点和区间关系进行全隐私的保密判定,有着重要的研究意义.点和区间关系的全隐私保密判定,是指在不泄漏双方隐私的情况下,保密地判断一方的点是否包含在另一方区间中.这个问题的解决归属于安全多方计算的研究领域,是安全多方计算问题的一个分支.因此以安全多方计算的思想解决该问题,恰好符合了两方,即点和区间隐私都需要保护的要求.本文正是基于这一点,利用了安全多方计算的思想去研究这个问题.1.1相关工作针对点和区间关系的保密判定问题,目前的方案[