隐私保护的点与任意多边形位置关系判定

作     者：张明武 冷文韬 沈华 ZHANG Ming-Wu;LENG Wen-Tao;SHEN Hua

作者机构：湖北工业大学计算机学院武汉430068 桂林电子科技大学计算机与信息安全学院桂林541004 智能地学信息处理湖北省重点实验室武汉430074 

基　　金：国家自然科学基金(61672010,61702168,61701173) 湖北省自然科学基金面上项目(2017CFB596) 湖北省教育厅重点项目(D20181402) 交通物联网技术湖北省重点实验室(武汉理工大学)(WHUTIOT-2017B001) 广西密码学与信息安全重点实验室(GCIS201717) 智能地学信息处理湖北省重点实验室开放课题(KLIGIP-2017A11)~~ 

出 版 物：《密码学报》 (Journal of Cryptologic Research)

年 卷 期：2019年第6卷第4期

页      码：443-454页

摘      要：点与多边形位置关系判定的保密计算是一种非常有用的安全多方计算几何应用,目前已有的方案仅支持凸多边形的关系判定.本文提出一种有效隐私保护的点与任意多边形位置关系判定方案.该方案使用模拟射线的判定法将点与任意多边形位置关系的判定问题转化为任意一条过点的射线与多边形相交点数的奇偶性判定问题.设计中首先提出一种精简高效的叉积协议,该协议利用符号位编码将明文空间划分为两个不相交的子空间,分别用于点的正负坐标到明文空间的映射空间从而实现了支持负数的叉积运算,然后基于该叉积协议并利用同态加密方案设计一种隐私保护下的点与多边形位置关系的判定协议,以计算射线与多边形的相交点数,最后利用模拟范例证明该协议的安全性.现有点与多边形位置关系判定方案通常只适用于凸多边形的情况,本文方案不仅能支持对凸多边形的判定且能支持对凹多边形的判定.模拟实验显示本文提出的叉积协议的运行效率相对于已有的叉积协议提高了67.5%.由于避免使用了复杂的密码原语,本文提出的判断方案获得了线性的计算复杂度和通信开销.

主 题 词：安全多方计算 叉积协议 点与多边形关系 同态加密 

学科分类：0808[工学-自动化类] 0809[工学-计算机类] 08[工学] 0839[0839] 0714[0714] 0835[0835] 0701[理学-数学类] 0811[工学-水利类] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.13868/j.cnki.jcr.000313

馆 藏 号：203776664...