导航：安全管理网>> 安全论文>> 电力安全论文>>正文

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

文档作者：孙茂华1,2 罗守山1,2,3 辛阳1,2 杨义先1,2 文档来源： 1.北京邮电大学 2.北京邮电大学 3.北京安码科技有限公司		点击数：	更新时间： 2021年04月06日
下载地址：点击这里	文件大小： 789.38 KB 共13页	文档格式： PDF	下载点数： 1 点（VIP免费）

全屏查看

内容预览 [文件共13页]

本文件共13页，如需编辑使用，请下载。

注：预览效果可能会出现部分文字乱码（如口口口）、内容显示不全等问题，下载是正常的。

	文件大小：789.38 KB 共13页文件格式：PDF 下载点数：1 点（VIP会员免费）

下一篇：太阳能电池用锗单晶片加工废料综合回收利…

上一篇：基于分离信源信道码的相关信源在有噪广播…

文本预览

仅提取页面文字内容，供快速阅读使用。

2013 年1 月 Journal on Communications January 2013
第34 卷第1 期 通 信 学 报 Vol.34 No. 1
安全两方线段求交协议及其在保护隐私凸包交集中的应用
孙茂华1,2，罗守山1,2,3，辛阳1,2，杨义先1,2
(1.北京邮电大学 信息安全中心，北京 100876；2.北京邮电大学 灾备技术国家工程实验室，北京 100876；
3.北京安码科技有限公司，北京 100876)
摘 要：研究了现有安全多方计算几何协议，提出了安全多方计算几何的模型和框架，从数学模型、安全模型和
通信模型3 个维度展开描述。针对现有安全两方线段关系判定协议都忽略求解交点坐标的问题，在半诚实模型下
基于Paillier 同态加密技术提出了安全两方线段求交协议，使用Goldreich 证明法进行了理论安全性分析，并在恶
意模型下进行了推广。分析结果表明，该半诚实模型下的算法在效率上优于现有算法。作为安全两方线段求交协
议的应用，结合O’Rourke 算法提出了保护隐私的凸包求交集协议，弥补了安全计算几何领域仅实现了凸包并集
算法的缺陷。
关键词：密码学；安全多方计算几何；安全两方线段求交；保护隐私；凸包交集
中图分类号：TN918.1 文献标识码：A 文章编号：1000-436X(2013)01-0030-13
Secure two-party line segments intersection scheme and its
application in privacy-preserving convex hull intersection
SUN Mao-hua1,2, LUO Shou-shan1,2,3, XIN Yang1,2, YANG Yi-xian1,2
(1. Information Security Center，Beijing University of Posts and Telecommunications, Beijing 100876, China;
2. National Engineering Laboratory for Disaster Backup and Recovery, Beijing University of Posts and Telecommunications, Beijing 100876, China;
3. Beijing Safe-Code Technology Co.,Ltd. , Beijing 100876, China)
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
1 引言
随着信息技术的推广，越来越多的机构采用信
息技术实现办公和通信。不同机构之间利用信息技
术进行合作，但是，在合作过程中，出于利益考虑，
机构往往不愿意透露自己的商业信息，这就为合作
的顺利进行带来了不便。考虑如下2 个问题，问题
1：战争期间，A 国和B 国都打算在C 国修建铁路。
在铁路完工之前，修建路线是保密的。为了防止将
来发生火车相撞，A 国和B 国希望在不泄露自己路
收稿日期：2012-07-13；修回日期：2012-11-20
基金项目：国家自然科学基金资助项目（61121061, 61161140320）
Foundation Item: The National Natural Science Foundation of China (61121061, 61161140320)
doi:10.3969/j.issn.1000-436x.2013.01.004
第1 期 孙茂华等：安全两方线段求交协议及其在保护隐私凸包交集中的应用 ·31·
线的前提下，确定2 条路线是否有交汇，并根据交
汇位置进行协商谈判。问题2：跨国公司A 和B 都
打算在C 国拓展新市场，两公司分别拟定了其在C
国展开业务的新区域，并作为一级商业机密保护。
现在，两公司希望在不泄露各自区域信息的前提下
确定新区域是否有重合以及重合区域的信息。
上述问题本质上是在分布式环境下，不同参与
方在不泄露自己私有信息的前提下共同完成某种
计算。为了解决这些问题，安全多方计算(SMC,
secure multi-party computation)应运而生。
安全多方计算是指在分布式网络中，多个用户
在不泄露自己秘密的情况下，以自己的秘密作为输入
共同计算某个函数[1]。Yao 在文献[2]中首次提出了安
全两方计算协议。后来，Goldreich 对SMC 做了比较
完整的总结，并提出了SMC 的安全性定义[3]。近几
年来，安全多方计算取得了众多研究成果[4~20]。文
献[4]中构造了一种安全多方计算协议用于分享公
共安全网络中的秘密信息。文献[5]中利用秘密共享
构造了一种安全多方排序协议，该协议可在一定程
度上同时抵抗主动和被动敌手攻击。刘文等利用
ElGamal 密码体制解决了安全多方数据排序问题[6]。
文献[7]中利用安全多方计算技术，针对可嵌套共
谋，提出可信防共谋协议模型。2011 年，Maheshwari
和Kiyawat 将安全多方计算和云计算结合，提出了
安全多方云计算的概念、应用场景和框架结构[8]。
2012 年，Dima 等利用安全多方计算实现了数据挖
掘中的  differential隐私保护[9]。2012 年，Wang
等研究了安全多方计算中的恶意模型，提出了制约
性反攻击的概念，保证了恶意模型下安全多方计算
协议的安全性[10]。Goldreich 等基于密码学安全模型
提出了可以计算任意函数的安全多方计算协议[11]。
理论上讲，任何安全多方计算问题都可以使用电路
估值方案解决。但是，出于效率和复杂度的考虑，
这种方案在实际应用中并不可行。针对不同应用环
境，需要研究不同的解决方案。
作为安全多方计算在计算几何领域的应用，安
全多方计算几何的概念首先由Mikhail 等提出[12]。安
全多方计算几何是指在分布式环境中多方共同解
决计算几何问题，计算结束后，除了结果信息外各
参与方不能获知额外的信息。目前，安全多方计算
几何主要研究下列四类问题：点包含问题、多边形
相交问题、最近点对问题以及凸包问题。文献[13]
基于Monte Carlo 方法和Cantor 编码分别设计了判
断任意几何图形点包含问题协议以及判断任意几
何图形相交、包含关系的协议。文献[14]提出了安
全两方向量叉积协议和安全两方三点叉积协议，并
在此基础上实现了安全两方点包含协议。文献[15]
基于坐标系秘密交换协议和不同坐标系下两点距
离计算协议，首次解决了不同坐标系下圆是否包含
点的判定问题。文献[16]基于茫然传输实现了可以
判定2 个任意多边形以及2 个任意几何图形相交关
系的协议。文献[17]设计了一个蒙特卡洛偏真算法，
用于判断多边形的位置关系。文献[18]解决了安全
多方最近点对问题，但是引入了茫然第三方，因此
该协议的实用性不高。文献[19]基于向量差最小值
协议和同态加密方案实现了安全多方最近点对协
议，协议效率高于文献[18]，且不需要茫然第三方
的参与。文献[20]基于Graham 算法、安全叉积协议、
姚氏百万富翁协议设计了一个安全两方凸包求解
算法。文献[21]基于裹包法、姚氏百万富翁协议、
叉积协议解决了安全两方凸包问题。
文献[12, 13, 16, 17, 22]虽然给出了安全多方线段
求相交协议，但是只能判断线段是否有交点，无法计
算交点的坐标信息。因此，不能完全解决问题1。从
文献[20]和文献[21]可以看出，目前在凸包运算的隐
私保护研究中，主要解决凸包并集操作，还没有实现
凸包交集操作的隐私保护。因此，无法解决问题2。
表1 分析了近几年来提出的安全多方多边形相
交协议和安全多方凸包求解协议的原理和贡献。
本文首先研究安全多方计算几何模型和框架，
从数学模型、安全模型、通信模型3 个维度展开描
述。为了解决问题1，本文分别提出了半诚实模型
和恶意模型下的安全两方线段求交协议，不仅可以
确定2 条线段是否有交点，还可以输出交点坐标信
息；为了解决问题2，本文首先利用O’Rourke 算法
将求解凸包交集问题转换为求解2 个凸多边形相交
边的交点问题，然后利用本文提出的安全两方线段
求交协议给出具体的交点坐标。
2 预备知识
2.1 Goldreich 安全证明法
Goldreich 给出了半诚实模型下安全性证明方法，
被广泛应用在安全多方计算几何的安全性分析中。
定义1 （Goldreich 安全证明法）[3]
设* * '* '*
1 1 :{0,1} {0,1} {0,1} {0,1} m m f L   L  ，其
中， 1 2 ( , , , ) i m f x x L x 是 1 2 ( , , , ) m f x x L x 的第 i个元素。
·32· 通 信 学 报 第34 卷
定义
1 2 1 1 2 1 ( , , , ) { ( , , , ), , ( , I m i m ij f x x L x  f x x L x L f x 2x ,L ,
)} m x 其中， 1 2 { , , , } {1,2, , } j I  i i L i  L m 。设 为计
算f 的 m 方协议，当输入为1 2 ( , , , ) m x  x x L x 时，
第i 方在执行 的过程中得到信息序列
1 2 ( , , i , i , , i )
i i k x r m m L m ，记为 ( ) i view x ，其中 ri 表示
第i 方独立的掷币输出； i
j m 表示第i 方收到第j 次
的信息。当输入为1 2 ( , , , ) m x  x x L x 时，执行协议
以后，第 i 方的输出结果记为output (x) i
 。对于一个
函数f，如果存在概率多项式时间算法（或者称为
模拟器 S），使得对于所有的I [m]，有
1 2 1 ({0,1}* ) { ( , ( , , , ), ( )), ( )} t m
c
i i i x S I x x x f x f x  L 
({0,1}* ) { (), ()} i x m view x output x

则认为 秘密计算了f，其中
c
表示多项式电路计
算不可区分。要证明一个安全多方计算协议是安全
的，就必须构造满足上述条件的模拟器S。
该定义可以直观地理解为对于一个半诚实参
与者，如果可以直接利用自己的输入与协议的输出
通过单独模拟整个协议的执行过程而得到在执行
协议过程中所能得到的任何信息，那么协议就能保
证输入的私密性。如果一个计算协议能被这样模
拟，参与者就不能从协议的执行过程中得到有价值
的信息，这样的协议就是安全的。
目前，在安全多方计算协议领域，Goldreich 证
明法是公认的一种安全性证明方式。本文亦采用这
种方法进行安全性证明。
2.2 保护隐私的基础协议
2006 年，罗永龙等在文献[23]中提出了保护隐
私的向量叉积问题，并给出了解决方案，该解决方
案被称为是保护隐私的向量叉积协议CPP_V(cross
product protocol for two vector)。
2007 年，罗永龙等又在文献[22]中提出了保护
隐私的点线叉积问题，并给出了解决方案，该解决
方案被称为是保护隐私的点线叉积协议CPP_PL
(cross products protocol for a point with a line)。
罗永龙等在文献[14]中给出了一个安全两方点
包含协议PIP (point inclusion protocol)。该协议的原
理是如果一个点在一个多边形内，假设多边形的边
按逆时针方向排序，则该点在这个多边形每一条边
的左侧。因此只需要利用安全叉积协议，即可判断
点是否在多边形内。
2.3 Paillier 加密方案
Paillier 加密方案[24]的安全性依赖于合数剩余
判定假设（DCRA, decisional composite residuosity
assumption），即没有多项式时间算法来区分一个
模数是否是模n2 的n 次剩余。具体描述如下。
系统参数：选取n  pq，其中 p 与q 为2 个大
素数。选取随机整数 g，满足gcd(l(g modn2),n) 1  ，
则公钥为(n, g)，私钥为 (n)  lcm(( p 1),(q 1))，
M 为明文消息。
加密：选择随机数rZ*p，E(M)  gmrn mod n2。
解密：
( ) 2
( ) 2
( mod )mod
( mod )
N
N
M L C n n
L g n

  。
Paillier 加密方案具有加同态特性，即1 1 D(E(m,r )
2 2 1 2 E(m , r ))  m  m 。
3 安全多方计算几何模型和框架
安全多方计算几何模型（如图1 所示）可以
描述为一个黑盒子。从盒子外看，各参与方输入
自己的信息，仅能得到函数的输出结果。而在盒
子内部，各参与方进行交互操作，共同计算函数
的输出。
一个安全多方计算几何协议可以从数学模型、
安全模型、通信模型3 个维度展开描述。
表1 安全多方计算几何相关研究
类别 文献 原理 主要贡献
安全多方多边
形相交问题
[12] 利用点积协议和向量控制协议判断2 条线段是否相交，
进而判断2 个多边形是否相交
首次提出了安全多方计算几何问题并给出了解决方案
[13] 基于Monte Carlo 方法和Cantor 编码 可以判断任意几何图形的相交、包含关系
[16] 基于茫然传输协议 可以判定2 个任意多边形以及2 个任意几何图形的相交关系
[17] 基于线段相交判定协议 文章算法是一个蒙特卡洛偏真算法；文章首次实现了安全
多方计算几何领域中协议的实验分析
[22] 基于安全两方叉积协议判断线段是否相交 文献给出了安全两方点线叉积协议，该协议是安全多方计
算几何的常用协议
安全多方凸包
求解问题
[20] 基于Graham 算法、安全叉积协议、姚氏百万富翁协议基于Graham 算法解决了安全凸包问题
[21] 基于裹包法、姚氏百万富翁协议、叉积协议 基于裹包法解决了安全凸包问题
第1 期 孙茂华等：安全两方线段求交协议及其在保护隐私凸包交集中的应用 ·33·
图1 计算模型
数学模型是指运用数学的语言和方法，通过抽
象、简化建立能近似刻画并“解决”实际问题的一
种模型。在安全多方计算几何领域，常用的数学模
型有：多边形求交点模型、多边形相似的模型、最
近点对模型以及凸包并集模型。
安全模型分为半诚实模型和恶意模型[3]。这2
种安全模型是按照参与者的不同来区分的。在安全
计算几何协议中，参与者分为诚实参与者、半诚实
参与者和恶意参与者。诚实参与者在协议执行过程
中，完全按照协议要求完成各个步骤，同时保密自
己的所有输入、输出以及中间结果。半诚实参与者
在协议执行过程中，完全按照协议要求完成各个步
骤，不会中途强行退出或恶意掺入虚假数据，但在
协议执行过程中，他们可能会保留所有可以收集到
的关于其他参与者的信息，以期望在协议结束后推
断出对方的输入信息或泄露给攻击者。恶意参与者
在协议的执行过程中，完全按照攻击者的意志执行
协议的各个步骤，他不但将自己的所有输入、输出
以及中间结果泄露给攻击者，还可以根据攻击者的
意图改变输入信息、中间结果信息，甚至终止协议。
如果所有参与者都是半诚实或诚实的，称此模型为
半诚实模型。半诚实模型中的攻击者都是被动的。
存在恶意参与者的模型称为恶意模型。恶意模型中
的攻击者是主动的。
目前，在安全多方计算协议的研究中，几乎所
有的协议都是建立在半诚实模型下。同时，半诚实
模型下的各种安全多方计算协议也具有很强的应
用背景。本文首先在半诚实模型下进行讨论，然后
将协议推广到恶意模型下。
通信模型：安全多方计算几何协议中使用的通
信模型包括同步和异步2 种模型。同步通信模型是
指所有参与方共同使用一个时钟服务器，同时接收
或发送消息；异步通信模型是指各参与方按照不同
的时钟周期接收或者发送消息。
可以用如图2 所示表示一个安全多方计算几何
协议的框架。
图2 安全几何计算框架
4 安全两方线段求交协议
4.1 问题分析
问题1 中的路线如果是线段，则问题1 可以描
述为：Alice 拥有线段 A: y  a1 x  b1 1 (m ≤x
1 ≤n ) ，Bob 拥有线段 2 2 B : y  a x  b 2 (m ≤x
2 ≤n )。Alice 和Bob 希望计算2条线段的交点。计
算结束后，除了交点的坐标信息，对方不能获知其
他任何信息。上述问题称为安全两方线段求交点问
题。解决该问题的协议称为安全两方线段求交协
议，记作STPP_IL(secure two party protocol for intersection
of line)。
在二维空间中，2 条线段的位置关系有如下几
种情况：图3(a)中，2 条线段相交于一点；图3(b)
中，2 条线段所在的直线相交于一点，但是2 条线
段无交点；图3(c)中，2 条线段平行，无交点；图3(d)
中，2 条线段在同一条直线上，且满足n2  m1 ，此时
线段无交点；图3(e)中，2 条线段在同一条直线上，
且满足1 2 n ≤m ，此时线段无交点；图3(f)中，2 条
线段在同一条直线上，且满足1 2 2 1 m ≤m ,m ≤n ,
1 2 n ≤n ，此时线段的交构成一条线段： 1 1 y  a x  b
2 1 (m ≤x≤n )；图 3(g)中，2 条线段在同一条直线
上，且满足2 1 1 2 m ≤m ,n ≤n ，此时线段的交构成一
条线段： 1 1 1 1 y  a x  b (m ≤x≤n )，图 3(h)中，2
条线段在同一条直线上，且满足2 1m ≤m , 1 2m ≤n ,
2 1 n ≤n ，此时线段的交构成一条线段： 1 1 y  a x  b
1 2 (m ≤x≤n )；图 3(i)中，2 条线段在同一条直线
上，且满足1 2m ≤m , 2 1 n ≤n ，此时线段的交构成
·34· 通 信 学 报 第34 卷
一条线段： y  a1 x  b1 2 2 (m ≤x≤n )。
图3 二维空间中的线段位置关系
安全两方线段求交点问题的数学模型就是已知2
条线段求交点，归属于多边形求交点模型一类。下面
使用异步通信模型和半诚实安全模型设计解决该问
题的协议。图4 中用灰色表示本节协议使用的模型。
图4 SP_IL 框架
4.2 协议描述
本文使用Luo 等在文献[23]中提出的SMC协议
的符号，如表2 所示。
系统参数：Alice 拥有Paillier 同态加密系统的
密钥对(pk,sk)，公钥pk 是公开的。
STPP_IL(A,B):
{
A1:
Compute: E(a1 ),E(b1 ) ;
//Alice 使用公钥加密a1 和  b1
表2 系统符号
符号名称 符号意义
Ai Alice 在本地执行第i 步
Bi Bob 在本地执行第i 步
Ai|Bi Alice 和Bob 各自在本地执行第i 步
Ai ^ Bi Alice 和Bob 共同协作执行第i 步
Generate 构造一个对象
Compute 执行一个基本操作
Send(A->B,s1,…,sm) A 向B 发送消息s1,…,sm
Receive(A->B,s1,…,sm) B 接收A 发送的消息s1,…,sm
Send(Alice->Bob, E(a1 ),E(b1 ) );
B2:
Generate: r // Bob 选择随机数r
Compute: [E(a1 )]r E(ra2 )  E(ra1  ra2 )；
Compute: [E(b1 )]r E(rb2 )  E(rb2  rb1 ) ;
Send(Bob -> Alice, E(ra1  ra2 ) , E(rb2  rb1 ) );
A3:
Compute: D(E(ra1  ra2 )) ;
Compute: D(E(rb2  rb1 )) ;
if( ( ( 1 2 )) 0 D E ra  ra  )
{//2 条线段斜率相等
if( D(E(rb2  rb1 ))  0 )
go to A4^B4
//2 条线段在同一条直线上，进入A4^B4
else
{
Send(Alice->Bob, (0,0));
go to B5;
//此时2 条线段平行，进入B5
}
}
else //2 条线段不平行
{
Compute:
1 2
2 1
1 2
2 1
( ( ))
( ( ))
a a
b b
D E ra ra
x D E rb rb





 ;
if( 1 1 m ≤x≤n )
{
Send(Alice->Bob, (x,1));
go to B5;
第1 期 孙茂华等：安全两方线段求交协议及其在保护隐私凸包交集中的应用 ·35·
}
else
{
Send(Alice->Bob, (x,2));
go to B5;
}
}
A4^ B4:
//2 条线段在同一条直线上
if(MillionaireProtocol( m1 ,m2 )==1)
//使用百万富翁协议判断数据的大小，当
// 1 2 m ≥m 时，协议返回1，否则返回0；
{
if(MillionaireProtocol( m1 ,n2 )==1)
End;//图3(d)的情况，无交点；
else
{
if(MillionaireProtocol( n1 , n2 )==1)
{
Send(Alice->Bob, m1 );
Send(Bob-> Alice, n2 );
Alice: 1 1 1 2 y  a x  b (m ≤x≤n ) ;
Bob: 2 2 1 2 y  a x  b (m ≤x≤n ) ;
//图3(h)的情况，交点构成一条线段；
}
else
{
Send(Alice->Bob, m1 ,n1 );
Alice: 1 1 1 1 y  a x  b (m ≤x≤n ) ;
Bob: 2 2 1 1 y  a x  b (m ≤x≤n ) ;
//图3(g)的情况，交点构成一条线段；
}
}
}
else
{// 1 2 m ≤m
if(MillionaireProtocol( m2 , n1 )==1)
End;//图3(e)的情况，无交点；
else
{
if(MillionaireProtocol( 1 2 n ,n )==1)
{
Send(Bob->Alice, m2 , n2 );
Alice: 1 1 2 2 y  a x  b (m ≤x≤n ) ;
Bob: 2 2 2 2 y  a x  b (m ≤x≤n ) ;
//图3(i)的情况，交点构成一条线段；
}
else
{
Send(Alice->Bob, n1 );
Send(Bob-> Alice, m2 );
Alice: 1 1 2 1 y  a x  b (m ≤x≤n ) ;
Bob: 2 2 2 1 y  a x  b (m ≤x≤n ) ;
//图3(f)的情况，交点构成一条线段；
}
}
}
End;
B5:
Receive(Alice->Bob, (x, k1 ) );
if( k1  0 )
End; //2 条线段无交点，协议结束
elseif( k1 1 )
{
if( 2 2 m ≤x≤n )
{
Send(Bob-> Alice, (x,1));
Compute: y  a2 x  b2 ;
}
else
Send(Bob-> Alice, (0,2));
}
A6:
Receive(Bob -> Alice, (x, k2 ) );
if( k2  2 )
End; //2 条线段无交点，协议结束
elseif( k2 1 )
Compute: y  a1 x  b1 ;
End;
}
4.3 性能分析
1) 正确性分析
定理1 半诚实模型下，上述协议是正确的。
证明
·36· 通 信 学 报 第34 卷
上述问题实际上就是求解式(1)在式(2)中的解
1 1
2 2
y a x b
y a x b
   

  
(1)
取值范围： 1 1 m ≤x≤n 并且 2 2 m ≤x≤n （2）
求解式（1 ）的解分为以下几种情况：当
1 2 a  a  0 时 ， 式 （ 1 ） 的 解 为 2 1
1 2
x b b
a a



，
1 1 y  a x  b 。求解 x 的值后验证是否满足式（2）
即可；由于Alice 选用了满足加法同态性的加密系
统，有
[ ( )] ( )
[ ( )] ( )
( ( ))
( ( ))
1 2
1 2
1 2
2 1
1 2
2 1
E a E ra
E b E rb
D E ra ra
D E rb rb
a a
b b
x r
r








 。
当 1 2 0 a  a  时，若b1  b2  0，则此时 2 条线段平
行，无交点；由于Alice 选用了满足加法同态性的
加密系统，此时满足 D([E(a1 )]r E(ra2 ))  0 并且
D([E(b1 )]r E(rb2 ))  0。因此，A1、B2、A3是正确的。
B5 和A6 中Alice 和Bob 进行通信，均发送数据对
(x,k)。其中，当k=0 时，代表2 条直线平行，无交
点；当k=1 时, x 有效并代表式（1）的解，Alice 和
Bob 只要确定x 的值满足式（1）以及式（2）后，通
过各自的线段方程即可确定y 的值；当k=2 时，代表
一方确定x 不在其取值范围内，因此线段无交点。
当2 条线段在同一条直线上时，A4^B4 利用百
万富翁协议比较x 的取值范围，根据4.1 节中讨论
的几种情况进行验证，因此是正确的。
综上所述，上述协议是正确的。
2) 安全性分析
定理2 半诚实模型下，上述协议是安全的。
证明 当2 条线段在同一条直线上时，上述
协议调用百万富翁协议完成计算。由于半诚实模
型下百万富翁协议是安全的，因此本协议也是安
全的。下面证明当2 条线段不在同一条直线上时
的安全性。
Alice 输入线段1 1 1 1 A: y  a x  b (m ≤x≤n )，
Bob 输入线段2 2 2 2 B : y  a x  b (m ≤x≤n )。协议输
出output  (x, y)。Bob 的信息序列
viewI (A,B,M, N)  (B,N, pk,r,E(a1 ),E(b1 ),E(ra1  ra2 ),
E(rb2  rb1 )),(x, k1 ),(x, k2 ),(x, y))
下面构造模拟器S 模拟Bob 的协议执行过程。
步骤 1 S 的输入为(B, N, pk, f1 (A,B,M, N))。其
中， f1 (A, B,M, N)  (r, E(ra1  ra2 ), E(rb2  rb1 ), (x, k2 ),
(x, y))。
步骤2 S 利用系统公钥pk 执行加密操作，可
得 到 ( 2 ), ( 2 )
E' ra E rb 。 则 r
E ra
E ra ra
E a
( )
( )
( )
2
'
1 2
1
'


 ,
'
1 E (b ) 2 1
'
2
( )
( )
r
E rb rb
E rb



。由于半诚实模型下同态加密
系统是安全的，有 ( 1 ) ( 1 )
' E a
c
E a

， ( 1 ) ( 1 )
' E b
c
E b 

 。
步骤 3 S 判断 f1 (A, B,M, N)中(x,y)是否为有效
值，如果是有效值，则 1 '
1  k ;否则 0 '
1k  。易知， 1
'1
k  k 。
综上所述，
( , , , ( , , , )) ( , , , , ( ), ( 1 ))
'
1
'
S B N pk f1 A B M N  B N pk r E a E b
( ), ( ),( , ),( , 2 ),( , ))
'1
E ra1  ra2 E rb2  rb1 x k x k x y 。
因为 f (A, B,M, N)  (x, y) , output  (x, y) ,所以
1 ( , , , ( , , , )) c
S B N pk f A B M N 
{viewI (A, B,M, N),output (A,B,M, N)}
  。
同样地，可以为Alice 构造模拟器。
3) 效率分析
计算复杂度：本协议中，共执行加密操作4 次，
解密操作2 次，加密数据乘法操作2(r+1)次，乘法
操作5 次，加法操作2 次，百万富翁协议至多3 次。
Paillier 加密算法的计算复杂度为O(2logn)，解密算
法的复杂度为O(2logn)，每次自乘操作的复杂度为
O(2logn)[24], 选用基于Paillier 加同态加密方案的百
万富翁协议[25]，则计算复杂度为O(nlogN)。忽略乘
法操作和加法操作，则本协议的计算复杂度为
O(rlogn)。
通信复杂度：本协议中，Alice 和Bob 共通信
4+3Ca 次，Ca 代表百万富翁协议的通信次数。
4.4 算法比较
在安全多方计算几何领域，很多文献给出的协
议都调用了现有的安全多方基础算法，但是没有明
确使用哪个具体的算法。这就为算法的性能比较带
来了不便。本文在进行算法比较时，选用了经典的
基础算法进行比较。表3 是算法比较时使用的符合
说明。
选用基于Paillier 加同态加密方案的百万富翁
协议[25]，则计算复杂度为O(nlogN)。基于点积协议
的保护隐私的点线叉积协议[22] 计算复杂度为
O(n2)。加同态加密系统采用Paillier 协议，加密和
解密操作的计算复杂度[24]均为O(2logn)。
第1 期 孙茂华等：安全两方线段求交协议及其在保护隐私凸包交集中的应用 ·37·
表3 系统符号
符号名称 符号意义
Ta 百万富翁协议的算法复杂度
Tc 保护隐私的点线叉积协议的算法复杂度
Th 加同态加密操作的复杂度
Td 加同态解密操作的复杂度
Ca 百万富翁协议的通信次数
Cc 保护隐私的点线叉积协议的通信次数
通过表4 可以看出，本文提出的方案计算复杂
度低于文献[17, 22]，略高于文献[26]；通信复杂度
低于文献[22, 26]，略高于文献[17]。
表4 复杂度对比
文献
计算复杂度
（一般化）
计算复杂度
（实例化）
通信次数
本文 O(rlogN) O(rlogN) 4+3Ca
[17] O(n2) O(n2) 6
[22] 4Ta+4Tc O(nlogN+n2) 4Ca +4Cc
[26] 4(4Th+3Td+ Ta) O(ClogN) 8+12Ca
表5 将近几年来提出的安全两方线段求交协议
和本文提出的协议进行了功能对比。
表5 功能比较
文献 计算交点坐标 判断出
图3(a)~图3(c)
判断出
图3(d)~图3(i)
本文 是 是 是
[17] 否 是 是
[22] 否 是 是
[26] 否 是 否
4.5 恶意模型下的推广
恶意模型下的安全两方线段求交协议和半诚
实模型下的协议思想是一致的。由于私有数据在进
行交互之前都进行了数据加密，因此，即使对方是
不诚实的，也无法得知对方私密数据。但是，在恶
意模型下一方需要通过验证得知对方是否是恶意
的，一旦发现对方是恶意的，需要及时终止协议。
下面在半诚实模型协议的基础上，Alice 和Bob 需
要进行多次验证性的交互，防止对方提供虚假数
据。Alice 仍然采用Paillier 加密系统，协议的第一
步、第二步和半诚实模型下是一样的。
下面，根据二维空间中线段位置关系的不同分
别进行讨论。
1) 2 条线段平行：Alice计算 ( ( 1 2 )) 0 D E ra  ra 
并且D(E(rb2  rb1 ))  0 后，得知2 条线段平行不相
交，此时通知Bob 结果，双方进行交互性验证,验证
方式如下。
Ai|Bi:
Compute： a
j
A  g j , b
j
B  g j
Generate: u jR Z n
Generate: c jR Zn
Compute: gu
j
K  j
//Alice 计算j=1 的值，Bob 计算j=2 的值；
Send(Alice->Bob, A1 , B1 ,K1 , c1 );
Send(Bob->Alice, A2 ,B2 ,K2 ,c2 );
Ai+1|Bi+1:
Compute: s j  u j  c j a j ;
Compute: t j  u j  c j b j ;
Compute: Ha H(ai) i  ;
Compute: Hb H(bi) i  ;
//Alice 计算j=1 的值，Bob 计算j=2 的值；
Send(Alice->Bob, s t Ha1 Hb1 1 , 1 , , );
Send(Bob -> Alice, s t Ha2 Hb2 2 , 2 , , );
Ai+2:
if(( gs2 K Ac2
 2 2 )&amp;amp;&amp;amp;( 2 ( 1) H H a a  )
&amp;amp;&amp;amp;( gt2 K Bc2
 2 2 )&amp;amp;&amp;amp;( 2 ( 1) H H b b  ))
End;//此时Alice 得知Bob 是诚实的
else
END;//Bob 提供虚假数据，结束协议。
Bi+3:
if(( gs1 K Ac1
 1 1 )&amp;amp;&amp;amp;( 1 ( 2) Ha H a  )
&amp;amp;&amp;amp;( gt1 K Bc1
 1 1 )&amp;amp;&amp;amp;( 1 ( 2) H H b b  ))
End;//此时Alice 得知Bob 是诚实的
else
END;//Bob 提供虚假数据，结束协议。
2) 2 条线段所在直线交于一点：Alice 计算
D(E(ra1  ra2 ))  0后，得知2 条线段所在直线交于一
点，此时通知Bob 结果，双方进行交互性验证,验证
方式如下。
Ai|Bi:
if( j j m ≤x≤n )
{
Compute: y j  a j x  b j
Generate: rj //选择随机数
//Alice 计算j=1 的值，Bob 计算j=2 的值；
Send(Alice->Bob,(x,1), r1 );
·38· 通 信 学 报 第34 卷
Send(Bob->Alice,(x,1), r2 );
}
else
{
Send(Alice->Bob,(0,2),0);
Send(Bob->Alice, (0,2),0);
}
Ai+1|Bi+1:
Receive(Alice->Bob, (x, k1 ), 1 r ) ;
Receive(Bob -> Alice, (x, k2 ), 2 r ) ;
//Alice 计算j=2, i=1 时的值;
//Bob 计算j=1,i=2 时的值；
if( k j ==2)
{
t1 =MillionaireProtocol(x, ) j n ;
t2 =MillionaireProtocol(x, ) j m ;
//调用恶意模型下的百万富翁协议
if( t1 t2  0 )
End; //对方是诚实的，协议结束
else
End;//对方提供虚假数据，协议结束
}
elseif( k j ==1)
{
Compute: yi  ai x  bi ;
Compute: Yi  H(r j yi ) ;
Send(Alice->Bob, Y1 );
Send(Bob -> Alice, Y2 );
}
Ai+2:
Receive(Bob -> Alice, Y2 );
if( ( ) Y2  H r1 y1 )
End;//此时Alice 得知Bob 是诚实的;
else
End; //Bob 提供虚假数据，协议结束
Bi+3:
Receive(Alice -> Bob, Y1 );
if( ( ) Y1  H r2 y2 )
End;//此时Bob 得知Alice 是诚实的;
else
End; //Alice 提供虚假数据，协议结束
3) 2 条线段在同一条直线上：Alice 计算
1 2 D(E(ra  ra ))  0并且 2 1 D(E(rb  rb ))  0 后，得
知2 条线段在同一条直线上，此时通知Bob 结果。
Alice 和Bob 使用2 条直线平行时验证数据ai 的方
法验证a1 是否等于a2，b1 是否等于b2，使用恶意模
型下的百万富翁协议验证2 条线段是否有交点。
5 保护隐私的凸包交集协议
5.1 问题分析
问题2 中的区域如果描述为凸多边形，则问题2
可以表述为：Alice 拥有凸多边形1 P  {p , 2, , n p L p ，
Bob 拥有凸多边形1 2 { , , , } m Q  q q L q ，顶点为逆时针顺
序。Alice 和 Bob 希望求解P Q形成的凸包 new P 。同
时，除了结果之外，Alice 和Bob 不希望对方得到其他
信息。该问题称为保护隐私的凸包交集问题。
保护隐私的凸包交集问题的数学模型是已知2
个凸多边形求交集。本文选用凸包交集模型半诚实
模型和异步通信模型设计保护隐私的凸包交集协
议（如图5 所示）。
图5 保护隐私凸包交集协议框架
5.2 数学原理
定义1 所有内角都小于π 的多边形称为凸多
边形。凸多边形的所有顶点均为凸点[27]。
定理3 如果一个凸多边形的顶点在另一个凸
多边形内，则该顶点也是交集的一个顶点。
证明 假设i p 是凸多边形P的一个顶点，并且i p
在凸多边形Q 内部，则顶点i p 对应的内角1 。
利用反证法，假设pi 不是交集的顶点，存在一
点 t 是交集的顶点，并且nt, tm分别是交集多边形上
逆时针方向的2 条边。由于i p 是凸多边形P 的一个
顶点，并且在凸多边形Q 内部，则( ) ip  P Q 。
因此， i p 在nt,tm的左边。又由于nt, tm都属于凸多
第1 期 孙茂华等：安全两方线段求交协议及其在保护隐私凸包交集中的应用 ·39·
边形 P 内部或边上，因此2是凸多边形 P 的一个
内角，所以2  。但这与1 矛盾。因此，pi
肯定是交集的一个顶点(如图6 所示)。
图6 交集的顶点
得证。
求2 个凸多边形的交集，也就是求出交集顶点
的坐标。考虑如下情况。
图7(a)中，交集的顶点均为两凸多边形的边相交
产生的交点；图7(b)中，除了两凸多边形的边相交产
生的交点外，交集的顶点还包括原凸多边形的某些顶
点，例如4 p ；图7(c)中，交集的顶点就是被包含的凸
多边形的顶点；图7(d)中，交集的顶点是原凸多边形
的一个顶点。即交集的顶点是原凸多边形的顶点或者
是由两凸多边形的边相交产生的交点。
图7 交集的顶点
2 个凸多边形相交，则交集可能是一个点、一
条线段或者一个多边形。
定理4 如果2 个凸多边形的交是一个多边形，
则该多边形为凸多边形。
证明
假设凸多边形1 2 { , , , } n P  p p L p 和凸多边形
1 2 { , , , } m Q  q q L q 相 交 ， 交 集 的 顶 点 坐 标 为
new 1 2 { , , , } k T  t t L t ，k≥1。
对于顶点ti，如果ti 是凸多边形P 或者Q 的一
个顶点(例如ti 是凸多边形P 的顶点pj)，则
ti1ti ti1   pi1 pi pi1。因为 i 1 i i 1 p pp     ，所以
i 1 i i 1 t tt      。
如果ti 不是凸多边形P 或者Q 的一个顶点，则
ti是由 P 和 Q 的边相交形成的交点。假设 p pm n 和
q qa b 相交形成交点 ti，则ti1ti ti1   pmti qa或者
i 1 i i 1 n i a t  t t   p t q 。由于 m i a p t q   ， n i a p t q
  ，因此i 1 i i 1 t tt      （如图8 所示）。
图8 2 条线段的交点
综上所述，交集的每个内角的度数都小于 ，
因此交多边形是一个凸多边形。得证。
由于交集的顶点是原凸多边形的顶点或者是
由两凸多边形的边相交产生的交点，因此，关键问
题是如何确定凸多边形的边何时相交以及交点的
坐标。O’Rourke 在文献[28]中给出了一个高效地确
定两凸多边形的边何时相交的算法，第4 节给出了
如果安全求解线段交点的算法。
假设凸多边形1 2 { , , , } n P  p p L p ，凸多边形
1 2 { , , , } m Q  q q L q ，顶点为逆时针顺序。 i 1 i A p p  
uuuuur
和
j 1 j B q q  
uuuuuur
分别代表2 个多边形上的有向边。
O’Rourke 算法让A 和B 相互追赶，以便在有交点的
时候相遇。有向边“追逐”的几种情况如图9 所示。
1) 有向边B 挡在A 的正前方，此时如果让A
前进，则有可能产生交点；
2) 有向边A 挡在B 的正前方，此时如果让B
前进，则有可能产生交点；
3) 有向边B 在A 的外侧，此时如果让B 前进，
则有可能产生交点；
4) 有向边A 的终点在B 的外侧且A 的起点在
B 的内侧，此时如果让A 前进，则有可能产生交点；
5) 有向边A 的终点在B 的外侧且A 的起点在
B 的外侧，此时如果让A 前进，则有可能产生交点。
用数学语言描述为：令H(A)代表A 的左侧半平
面。如果 A B≥0 且 ( ) j q H A 或者 A B  0 且
( ) i p H B ，则让A前进；如果A B  0且 ( ) i p H B
或者 A B≥0且 ( ) j q H A ，则让 B 前进。
5.3 协议描述
for i=1 to n
·40· 通 信 学 报 第34 卷
{
if(PIP(pi,Q)==1)
Send(Alice->Bob, pi);
}
for i=1 to m
{
if(PIP(qi,P )==1)
Send(Bob->Bob, qi);
}
令i=j=1;
p pi i A 1  和 q q j j B 1  分别为多边形P 和Q 的
第一条边；
do{
STPP_IL(A,B)；//Alice 和Bob 利用安全两方
//线段求交协议计算并输出边A 和B 的交点，
//并插入到各自输出点序列的相应位置。
if(CPP_V(A,B)) >0) //调用保护隐私的向量叉
//积协议，判断向量叉积是否为正
{
if(CPP_PL (qj+1,A)==−1)
// qj+1 在A 的左侧
i=i+1;
else
j=j+1;
}
else
{
if(CPP_PL (pi+1,B)==-1)
// pi+1 在B 的左侧
j=j+1;
else
i=i+1;
}
}while((i

网友评论 more

电力安全论文最新内容

03-05