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

Fully privacy-preserving determination of point-range relationship

作　　者：陈振华[1,2,3] 李顺东 陈立朝[1] 黄琼 张卫国[1] 

机构地区：[1]西安科技大学计算机科学与技术学院,西安710054 [2]中国科学院信息工程研究所信息安全国家重点实验室,北京100093 [3]桂林电子科技大学广西可信软件重点实验室,桂林541004 [4]陕西师范大学计算机科学学院,西安710062 [5]华南农业大学数学与信息学院,广州510642

出　　处：《中国科学：信息科学》2018年第2期187-204,共18页Scientia Sinica(Informationis)

基　　金：国家自然科学基基金(批准号:61272435);信息安全国家重点实验室开放课题基金(批准号:2016-MS-19);广西可信软件重点实验室研究课题资助(批准号:kx201614);陕西省自然科学基础研究计划面上项目(批准号:2017JM6069)资助

摘　　要：点和区间关系的保密判定在范围查询中应用非常广泛,但目前已存的解决方案大多只保护了一方的隐私,而另一方的隐私并未得到保护.此外,已存方案给出的点和区间都是离散的整数(或有理数)范围.针对这些问题,本文利用安全多方计算的思想设计了保密判定点和区间关系的2种协议,不但同时保护了两方的隐私,而且将数域推广到连续的实数.本文首先利用0-1编码并结合Goldwasser-Micali同态加密给出了全隐私判定一个整数点是否在一个离散整数区间上的协议1;然后利用函数的单调性和Paillier同态加密给出了全隐私判定一个实数点是否在一个连续实数区间的协议2.最后,给出了本文协议的一个应用实例.理论和实验分析显示:本文的两个协议在取得较优通信效率的同时都取得了全隐私性.此外,协议2相比以往的方案,第一次给出点和连续实数区间的判定方法,在保持较优效率和良好性能的同时取得了通用性.The privacy-preserving determination of point-range relationship is widely applied to range queries, However, most existing solutions only protect one party＇s privacy but not the other party＇s; moreover, they only cover integers or rational numbers. Focusing on these problems, we design two protocols with the notion of secure multiparty computation. We first present the fully privacy-preserving protocol 1, which can determine whether an integer is in a discrete integer interval using the 0-1 coding in combination with the Goldwasser-Micali homomorphic encryption. Subsequently, we present the fully privacy-preserving protocol 2, which can determine whether a real number is in a continuous real number interval using the monotonic function in combination with Paillier＇s homomorphic encryption. Finally, we present a practical example based on our protocol. Theoretical and experiential analyses show that both of our protocols achieve a low communication cost, while preserving the full privacy of two parties. In addition, protocol 2 in this paper first gives a solution to privately determine whether a real number is in a continuous real number interval, while showing higher efficiency and better performance.

关 键 词：点和区间 全隐私 安全多方计算 实数 同态加密 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]