安全两方线段求交协议及其在保护隐私凸包交集中的应用

doi:1000-436X(2013)01-0030-13

摘要/Abstract

摘要：

研究了现有安全多方计算几何协议，提出了安全多方计算几何的模型和框架，从数学模型、安全模型和通信模型 3个维度展开描述。针对现有安全两方线段关系判定协议都忽略求解交点坐标的问题，在半诚实模型下基于Paillier同态加密技术提出了安全两方线段求交协议，使用Goldreich证明法进行了理论安全性分析，并在恶意模型下进行了推广。分析结果表明，该半诚实模型下的算法在效率上优于现有算法。作为安全两方线段求交协议的应用，结合 O’Rourke 算法提出了保护隐私的凸包求交集协议，弥补了安全计算几何领域仅实现了凸包并集算法的缺陷。

关键词: 密码学, 安全多方计算几何, 安全两方线段求交, 保护隐私, 凸包交集

Abstract:

The model and framework of secure multi-party computational geometry were presented based on the existing protocols.The new framework has three dimensions,the math model,the security model and the communication model.Using the new model and framework,a secure two-party line segments intersection protocol based on Paillier homomorphic encryption scheme is proposed.This protocol solves the problem that the existing secure two party intersect-determination schemes of line segments cannot output the exact coordinates of the intersection.The security of the protocol is demonstrated using Goldreich method.The results show that this protocol has better efficiency than the existing ones.In addition,the secure two-party line segments intersection in malicious model is also designed.As an application,a privacy-preserving convex hull intersection protocol is proposed based on the O’Rourke scheme.This application makes up for the gap in privacy-preserving convex hull intersection protocol in the area of secure multi-party computational geometry.

Key words: cryptography, secure multi-party computational geometry, secure two-party line segments intersection scheme, privacy-preserving, convex hull intersection scheme

孙茂华,罗守山,辛阳,杨义先. 安全两方线段求交协议及其在保护隐私凸包交集中的应用[J]. 通信学报, 2013, 34(1): 30-42.

Mao-hua SUN,Shou-shan LUO,Yang XIN,Yi-xian YANG. Secure two-party line segments intersection scheme and its application in privacy-preserving convex hull intersection[J]. Journal on Communications, 2013, 34(1): 30-42.

图/表 16

表1

图

图4

表2

表3

表4

表5

图5

图6

图7

图8

图9

图10

表6

参考文献 28

[1]	GOLDWASSER S . Multi-party computations:past and present[A]. Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing[C]. USA, 1997. 21-24.
[2]	YAO A C . Protocols for secure computations[A]. Proceedings of 23th Annual IEEE Symposium on Foundations of Computer Science[C]. Chicago,USA, 1982. 160-164.
[3]	GOLDREICH 0 . Phishing[EB/OL]. , 1998.
[4]	SANTOS M A S , MARGI C B . A secure multi-party protocol for sharing valuable information in public safety networks[A]. 2011 IEEE 8th International Conference on Mobile Ad Hoc and Sensor Systems[C]. Valencia, 2011. 935-940.
[5]	TANG C M , SHI G H , YAO Z A . Secure multi-party commputation protocol for sequencing problem[J]. Science China Information Sciences, 2011,54(8): 1654-1662.
[6]	刘文, 罗守山, 陈萍 . 利用 ElGamal密码体制解决安全多方数据排序问题[J]. 通信学报, 2007,28(10): 1-5. LIU W , LUO S S , CHEN P . Solution of secure multi-party multi-data ranking problem based on ELGamal encryption[J]. Journal on Communications, 2007,28(10): 1-5.
[7]	程柏良, 曾国荪, 揭安全 . 基于安全多方计算的可信防共谋协议模型[J]. 通信学报, 2011,32(8): 23-30. CHENG B L , ZENG G S , JIE A Q . Trusted coalition-proof protocol model based on secure multi-part computing[J]. Journal on Communications, 2011,32(8): 23-30.
[8]	MAHESHWARI N , KIYAWAT K . Structural framing of protocol for secure multiparty cloud computation[A]. The Fifth Asia Modelling Symposium[C]. Kuala Lumpur, 2011. 187-192.
[9]	DIMA A , NOMAN M , BENJAMIN C M ,et al. Secure distributed framework for achieving -differential privacy[A]. Privacy Enhancinge Technologies[C]. Berlin: Springer-Verlag, 2012. 120-139.
[10]	WANG X M , WANG A , BIAN S Q . Secure multi-party computation-an important theory in electronic technology[A]. Advances in Mechanical and Electronic Engineering[C]. Berlin: Springer-Verlag, 2012. 605-608.
[11]	GOLDREICH O , MICALI S A , WIGDERSON A . How to play any mental game[A]. The 19rd Annual ACM Conference on Theory of Computing[C]. New York,USA, 1987. 218-229.
[12]	ATALLAH M J , DU W L . Secure multi-party computational geometry[A]. Algorithms and Data Structures[C]. Berlin:Spr nger, 2001. 165-179.
[13]	李顺东, 司天歌, 戴一奇 . 集合包含与几何包含的多方保密计算[J]. 计算机研究与发展, 2005,42(10): 1647-1653. LI S D , SI T G , DAI Y Q . Secure multi-party computation of set-inclusion and graph-inclusion[J]. Journal of Computer Research and Development, 2005,42(10): 1647-1653.
[14]	LUO Y L , HUANG L S , ZHONG H ,et al. A secure protocol for determining whether a point is inside a convex polygon[J]. Chinese Journal of Electronic, 2006,15(4): 578-582.
[15]	王涛春, 罗永龙 . 不同坐标系下点圆关系的安全判定协议[J]. 计算机工程, 2012,38(1): 105-108. WANG T C , LUO Y L . Secure determination protocol of po nt-circle relationship under different coordinates[J]. Computer ngineering, 2012,38(1): 105-108.
[16]	李顺东, 戴一奇, 王道顺 ,等. 几何相交问题的多方保密计算[J]. 清华大学学报, 2007,47(10): 1692-1695. LI S D , DAI Y Q , WANG D S ,et al. Secure multi-party computations of geometric intersections[J]. Journal of Tsinghua Uni rsity, 2007,47(10): 1692-1695.
[17]	罗永龙, 黄刘生, 徐维江 ,等. 一个保护私有信息的多边形相交判定协议[J]. 电子学报, 2007,35(4): 685-691. LUO Y L , HUANG L S , XU H J ,et al. A protocol for privacy-preserving intersect-determination of two polygons[J]. ACTA Electronica Sinica, 2007,35(4): 685-691.
[18]	方兴, 仲红, 张守奇 ,等. 保护私有信息的最近点对协议[J]. 计算机技术与发展, 2008,18(12): 153-158. FANG X , ZHONG H , ZHANG S Q ,et al. A protocol for privacy-preserving closet-pair of points[J]. Computer Technology and Development, 2008,18(12): 153-158.
[19]	仲红, 孙彦飞, 燕飞飞 ,等. 保护私有信息的空间最近点对协议[J]. 计算机工程与应用, 2011,48(4): 87-89. ZHONG H , SUN Y F , YAN F F ,et al. Protocol for privacy-preserving space closet-pair of points[J]. Computer Engineering and Applications, 2011,48(4): 87-89.
[20]	逯绍锋, 罗永龙 . Graham 算法求解凸包问题中的隐私保护[J]. 计算机工程与应用, 2008,44(36): 130-133. LU S F , LUO Y L . Privacy-preserving in graham algorithm for finding convex hulls[J]. Computer Engineering and Application, 2008,44(36): 130-133.
[21]	WANG Q , LUO Y L , HUANG L S . Privacy- preserving protocols for finding the convex hulls[A]. ARES’08[C]. Washington,USA, 2008. 727-732.
[22]	罗永龙, 黄刘生, 荆巍巍 ,等. 保护私有信息的叉积协议及其应用[J]. 计算机学报, 2007,30(2): 248-254. LUO Y L , HUANG L S , JING W W ,et al. Privacy-preserving cross product protocol and its application[J]. Chinese Journal of Computers, 2007,30(2): 248-254.
[23]	LUO Y L , HUANG L S , CHEN G L ,et al. Privacy-preserving distance measurement and its application[J]. Chinese Journal of Electionics, 2006,15(2): 237-241.
[24]	PAILLIER P . Public-key cryptosystems based on composite degree residuosity classes[A]. Cryptology-EUROCRYPT'99[C]. Berlin: SpringerVerlag, 1999. 223-238.
[25]	BLAKE I F , KOLESNIKOV V . Strong conditional oblivious transfer and computing on intervals[A]. AISACRYPT 2004[C]. 2004. 515-529.
[26]	刘文, 罗守山, 陈萍 . 保护私有信息的点线关系判定协议及其应用[J]. 北京邮电大学学报, 2008,31(2): 72-75. LIU W , LUO S S , CHEN P . Privacy-preserving point-line relation determination protocol and its application[J]. Journal o Beijing University of Posts and Telecommunications, 2008,31(2): 72-75.
[27]	周培德 . 计算几何算法设计与分析[M]. 北京: 清华大学出版社, 2008. ZHOU P D . Computational Geometry Algorithm Design and Analysis[M]. Beijing: Tsinghua University PressPress, 2008.
[28]	O’ROURKE J . Computational Geometry in C[M]. Cambridge University Press, 1998.

类别	文献	原理	主要贡献
类别	12]	利用点积协议和向量控制协议判断2条线段是否相交，进而判断2个多边形是否相交	首次提出了安全多方计算几何问题并给出了解决方案
	13]	基于Monte Carlo方法和Cantor编码	可以判断任意几何图形的相交、包含关系
安全多方多边形相交问题	16]	基于茫然传输协议	可以判定2个任意多边形以及2个任意几何图形的相交关系
	17]	基于线段相交判定协议	文章算法是一个蒙特卡洛偏真算法；文章首次实现了安全多方计算几何领域中协议的实验分析
安全多方凸包求解问题	22]	基于安全两方叉积协议判断线段是否相交	文献给出了安全两方点线叉积协议，该协议是安全多方计算几何的常用协议
安全多方凸包求解问题	20][21]	基于Graham算法、安全叉积协议、姚氏百万富翁协议基于裹包法、姚氏百万富翁协议、叉积协议	基于Graham算法解决了安全凸包问题基于裹包法解决了安全凸包问题

符号名称	符号意义
A_i	Alice在本地执行第i步
B_i	Bob在本地执行第i步
A_i\|B_i	Alice和Bob各自在本地执行第i步
A_i^B_i	Alice和Bob共同协作执行第i步
Generate	构造一个对象
Compute	执行一个基本操作
Send(A-＞B,s₁,…,s_m)	A向B发送消息s₁…,,s_m
Receive(A-＞B,s₁,…,s_m)	B接收A发送的消息s₁…,,s_m

符号名称	符号意义
T_a	百万富翁协议的算法复杂度
T_c	保护隐私的点线叉积协议的算法复杂度
T_h	加同态加密操作的复杂度
T_d	加同态解密操作的复杂度
C_a	百万富翁协议的通信次数
C_c	保护隐私的点线叉积协议的通信次数

文献	计算复杂度（一般化）	计算复杂度（实例化）	通信次数
本文	O(rlo gN)	O(rlo gN)	4+3C_a
17]	O(n²)	O(n²)	6
22]	4T_a+4T_c	O(nlo gN+n²)	4C_a+4C_c
26]	4(4T_h+3T_d+T_a)	O(Clo gN)	8+12C_a

文献	计算交点坐标	判断出图3(a)~图3(c)	判断出图3(d)~图3(i)
本文	是	是	是
17]	否	是	是
22]	否	是	是
26]	否	是	否