第30卷第5期2013年5月计算机应用研究
Application Research of Computers Vol．30No．5May 2013
空间两平行直线间距离的保密计算协议
辛
摘
*
欣，郝林，汤瑜
(云南大学信息学院，昆明650091)
要：针对半诚实模型提出了空间两平行直线间距离的保密计算协议。确保互不信任的参与方分别输入各
自隐私信息合作计算，同时保持各自信息的隐私性，并且不能通过中间结果计算出其他参与方输入的隐私信息，最终准确得到两平行线间距离，并且在理论上证明了协议的正确性和安全性。关键词：安全多方计算; 点积协议; 保护隐私的计算几何中图分类号：TP309
文献标志码：A
文章编号：1001-3695(2013) 05-1530-03
3695．2013．05．064doi ：10．3969/j．issn．1001-
Privacy-preserving computational protocol on minimum distance
between two three-dimension parallel straight line
XIN Xin ，HAO Lin ，TANG Yu
（School of Information Science ＆Engineering ，Yunnan University ，Kunming 650091，China ）
Abstract ：This paper proposed a privacy-preserving computational protocol on the minimum distance between two three-dimension parallel straight lines based on semi-honesty model．Every participant in semi-honesty model inputted his informa-tion and no one tend to leak the information to others．They could not get others ’private information by the intermediate re-sults except sharing the output．Finally ，this protocol outputs the distance between two parallel straight lines correctly．It gave the correctness and security proof．
Key words ：secure multiparty computation （SMC ）；dot product protocol ；privacy-preserving computational geometry （PPCG ）
0引言
Alice 拥有秘密输入向量X =（x 1，x 2，…，假设有两个参与者，
x n ），Bob 拥有秘密输入向量Y =（y 1，y 2，…，y n ），他们希望进行协作计算并在协议结束后Alice 得到值W A =X i ·Y i +r B （r B 是Bob 选取的一个随机值）。同时要保证Alice 不能从W A 中得
也不能从已知的信息中推出任何有关Y i 的信到有关的r B 值，
Bob 不能得到W A 的值，息；同理，也不能推出有关X i 的信息。大多数安全多方计算问题的解决都需要保密点积协议，因此它
在密码学协议中占有一席之地。1. 2
半诚实模型(semi-honest model)
一般来说，在安全多方计算过程中，半诚实的参与方能严格执行协议的各个步骤，不会中途强行退出或恶意掺入虚假数据，但同时可能保留所有能够收集到的中间数据，试图通过这些数据推测其他参与方的秘密输入。1. 3
空间两平行直线间距离
［10］
近几年安全多方计算（SMC ）问题成为国际密码学界一个
［1］
研究热点。SMC 最初是被Yao 提出并进行了研究，随后
［2］
Goldreich 等人作了进一步研究。随着合作计算与隐私保护
SMC 被引入到了各个应用领域，越来越受到人们重视，保护隐
私的计算几何就是其中之一。
保护隐私的计算几何（PPCG ）是指互不信任的参与方分别
线、多边形等）以求解某几何问题，同时输入隐私信息（如点、
保持各自信息的隐私性，并且不能通过中间结果计算出其他参
与方输入的隐私信息。PPCG 主要用来研究计算几何中的信息安全问题，尤其是分布式计算中合作用户的隐私保护问题。Atallah 等人［3］首次将安全多方计算引入计算几何领域。目前
4］在半诚实模型下设计了有一些研究成果已经发表。文献［
保护私有信息的叉积协议，可用于解决很多其他的保护私有信
5］研究了两点间距离和点与圆形、息的计算几何问题；文献［
6］椭圆区域的关系问题；文献［研究了安全多方信息比较相等7］协议及其应用；文献［研究了有关保护私有信息的三角不等8］研究了恶意模型下公平的安全两方计算式判定问题；文献［
协议。
L 2，空间两条平行线L 1、其方程分别为
L 1：L 2：
{{
π1：a 1x +b 1y +c 1z +d 1=0π2：a 2x +b 2y +c 2z +d 2=0π3：a 3x +b 3y +c 3z +d 3=0π4：a 4x +b 4y +c 4z +d 4=0|A a 1·n 1+A a 2·n 2|
两条平行线的距离为d ：
d =
|b 3c 4－b 4c 3|·|n 1·n 2|
1
1. 1
背景知识
保密点积协议
9］该问题最初被Du 等人在文献［中提出，协议概述如下：
收稿日期：2012-07-21; 修回日期：2012-09-09
=
（（a 1A a 1+a 2A a 2，b 1A a 1+b 2A a 2，c 1A a 1+c 2A a 2））/
（|b 3c 4－b 4c 3|
b 1c 2－b 2c 1）+（c 1a 2－c 2a 1）
+（a 1b 2－a 2b 1））
基金项目：云南省自然科学基金资助项目(2010ZC160)
作者简介：辛欣(1987-) ，女(蒙古族) ，内蒙古赤峰人，硕士，主要研究方向为信息安全(xinxin_0224@163．com ) ; 郝林(1955-) ，男，教授，主要研究方向为信息安全; 汤瑜(1986-) ，男，硕士，主要研究方向为信息安全．
第5期
其中：A a 1是行列式|A |的代数余子式：
b 2
A a 1=
b 3b 4
c 2c 3c 4
d 2
d 3，A a 2=d 4
辛欣，等:空间两平行直线间距离的保密计算协议
Bob 有一条私有直线L 2：
·1531·
b 1b 3b 4
c 1c 3c 4
d 1d 3d 4
{
输出
2
π3ʒ a 3x +b 3y +c 3z +d 3=0π4ʒ a 4x +b 4y +c 4z +d 4=0
Alice 与Bob 合作计算距离d 。
2
n 1是平面πi 的法向量。
d 2=（（a 1A a 1+a 2A a 2）
（c 1a 2－c 2a 1）
2
2
a ）①Alice 计算：
+（b 1A a 1+b 2A a 2）
+
2
f 1=（（a 1b 2+a 2b 1）
+
（（b 1c 2－b 2c 1）
2
+（2b 1b 2）
22
+（b 2c 1+b 1c 2）2）/+（a 1b 2－a 2b 1）2）
（c 1A a 1+c 2A a 2）2）/（（b 3c 4－b 4c 3）2（（b 1c 2－b 2c 1）
+（a 1b 2－a 2b 1）2））
+（c 1a 2－c 2a 1）
…，r 1m ｝，Alice 计算F 1i =f 1+r 1i 并生成随机序列R 1i =｛r 11，
（i =1，2，3，…），并将序列F 1i 发送给Bob 。
22
W 1i =F 1i ·e 1+t 1②Bob 计算e 1=（c 3d 4）/（b 3c 4－b 4c 3），
1. 4
［］
不经意传输（oblivious transfer ）11
不经意传输协议简称为OT 协议，是一种可保护隐私的双方通信协议，可以使通信双方以一种选择模糊化的方式进行。通常情况下，不经意传输协议有两个参与者，即发送方A 和接A 掌握n 个秘密：s 1，s 2，s 3，…，s n 。一个不经意传输协收方B ，
议要满足以下要求：
a ）如果A 和B 诚实地执行协议，那么最后B 得到秘密s i ，B 对A 可以把i 理解为它的一个选择，并且要求除了s i 以外，…，s i －1，s i +1，…，s n 一无所知。的其他秘密s 1，
b ）协议完成后，A 对B 的选择i 一无所知，也就是A 不知道B 到底选择了哪个秘密。
（i =1，2，3，…）。其中t 1是Bob 生成的随机数，Bob 将序列W 1i 发给Alice 。
③Alice 用OT m 不经意传输选择。
W 1K =F 1K ·e 1+t 1
1
b ）①Bob 计算e 2=（b 4c 3）2/（b 3c 4－b 4c 3）2，并生成随机序…，t 2m ｝，Bob 计算W 2i =e 2+t 2i （i =1，2，3，…），列T 2i =｛t 21，并将序列W 2i 发给Alice 。
②Alice 计算：
f 2=（（a 1c 2+a 2c 1）
2
+（b 1c 2+b 2c 1）
2
2
+（2c 1c 2）2）/
2
2. 1
空间两平行直线间距离的保密计算协议
问题描述和基本思想问题描述
Alice 有一条私有直线L 1：假设有两个参与方，
（（b 1c 2－b 2c 1）2）+（c 1a 2－c 2a 1）+（a 1b 2－a 2b 1）2）
F 2i =W 2i ·f 2+h 1（i =1，2，3，…），其中h 1是Alice 生成的随机数。Alice 将序列F 2i 发送给Bob 。
1
③Bob 用OT m 不经意传输选择F 2k =W 2k ·f 2+h 1。
2. 1. 1
c ）①Alice 计算
f 3=（（a 1d 2+a 2d 1）（（b 1c 2－b 2c 1）
22
{{
距离d ：
π1ʒ a 1x +b 1y +c 1z +d 1=0π2ʒ a 2x +b 2y +c 2z +d 2=0π3ʒ a 3x +b 3y +c 3z +d 3=0π4ʒ a 4x +b 4y +c 4z +d 4=0
+（b 1d 2+b 2d 1）
2
2
+（c 1d 2+c 2d 1）2）/
+（c 1a 2－c 2a 1）+（a 1b 2－a 2b 1）2）
Bob 有一条私有直线L 2：
…，r 3m ｝，Alice 计算F 3i =f 3+r 3i 并生成随机序列R 3i =｛r 31，
（i =1，2，3，…），并将序列F 3i 发送给Bob 。
②Bob 计算
e 3=（b 3c 4－b 4c 3）2/（b 3c 4－b 4c 3）W 3i =F 3i ·e 3+t 2（i =1，2，3，…）
2
且L 1与L 2平行，在不泄露各自信息的情况下计算两条直线的
|A a 1·n 1+A a 2·n 2||b 3c 4－b 4c 3|·|n 1·n 2|
d ==
Bob 将序列发给Alice 。其中t 3是Bob 生成的随机数，
1
③Alice 用OT m 不经意传输选择W 3K =F 3K ·e 3+t 2。
（（a 1A a 1+a 2A a 2，b 1A a 1+b 2A a 2，c 1A a 1+c 2A a 2））/
（|b 3c 4－b 4c 3|
（b 1c 2－b 2c 1）+（c 1a 2－c 2a 1）
d ）Bob 计算e 4=c 3d 4b 4d 3/（b 3c 4－b 4c 3）2，并生成随机序列T 4i =｛t 41，…，t 4m ｝，Bob 计算W 4i =e 4+t 4i （i =1，2，3…），并将序列W 4i 发给Alice 。
②Alice 计算
2
f 4=2（a 21b 2c 2+a 1a 2b 2c 1+a 1a 2b 2c 2+a 2b 1c 1+
2222
2b 21c 2+2b 1b 2c 1+2b 2c 1c 2+2b 1c 1c 2）/
+（a 1b 2－a 2b 1））
2. 1. 2协议的主要思想
距离计算协议基于前面介绍的基本协议和基本几何知识秘密地判定两条空间直线间的距离。基于Alice 的私有信息b 1，c 1，d 1，a 2，b 2，c 2，d 2｝，Bob 产生一个产生一个向量A =｛a 1，
b 3，c 3，d 3，a 4，b 4，c 4，d 4｝，Alice 只计算函数f i ，运用向量B =｛a 3，
b 1等隐藏，并且Bob 不点积协议构造一系列的函数将元素a 1、
能计算出这些元素。Bob 只计算e i ，运用点积协议构造一系列b 3等隐藏，的函数将元素a 3、并且Alice 不能计算出这些元素。
1
Alice 和Bob 分别选择出W i 和T i 即为符通过运用OT m 协议，
（（b 1c 2－b 2c 1）
2
+（c 1a 2－c 2a 1）
2
+（a 1b 2－a 2b 1）2）
2，3…）。并生成随机序列F 4i =W 4i ·f 4+h 2（i =1，
h 2是Alice 生成的随机数，Alice 将序列F 4i 发送给Bob 。其中，
1
③Bob 用OT m 不经意传输选择F 4k =W 4k ·f 4+h 2。
e ）①Alice 计算
22
f 5=2（a 21b 2d 2+a 1a 2b 2d +a 2b 2d 1+2b 1b 2d 2+222b 1b 22d 1+b 2c 1d 2+b 2c 1c 2d 1+b 1c 1c 2d 2+b 1c 2d 1）/
合要求的元素。最后通过Alice 和Bob 分别计算辅助数据Q 、n 、P 、s 。将d 通过上述过程还原为d =2. 2
安全空间两平行直线的距离计算协议输入：Alice 有一条私有直线L 1：
（（b 1c 2－b 2c 1）
2
+（c 1a 2－c 2a 1）
2
+（a 1b 2－a 2b 1）2）
…，r 5m ｝，Alice 计算F 5i =f 5+r 5i 并生成随机序列R 5i =｛r 51，
（i =1，2，3，…），并将序列F 5i 发送给Bob 。
W 5i =F 5i ·e 5+t 3（i =1，②Bob 计算e 5=c 3d 4/（b 3c 4－b 4c 3），
{
π1ʒ a 1x +b 1y +c 1z +d 1=0π2ʒ a 2x +b 2y +c 2z +d 2=0
·1532·
计算机应用研究第30卷
2，3，…），Bob 将序列发给Alice 。其中t 2是Bob 生成的随机数，
1
③Alice 用OT m 不经意传输选择W 5K =F 5K ·e 5+t 3
（a 1b 2－a 2b 1）2）］·［（b 4c 3）2/（b 3c 4－b 4c 3）2］+［2（a 21b 2c 2+
2222a 1a 2b 2c 1+a 1a 2b 2c 2+a 22b 1c 1+2b 1c 2+2b 1b 2c 1+2b 2c 1c 2+
f ）①Bob 计算e 6=b 4d 3/（b 3c 4－b 4c 3），并生成随机序列T 6i =｛t 61，…，t 6m ｝，Bob 计算w 6i =e 6+t 6i （i =1，2，3，…），并将序列W 6i 发给Alice 。
②Alice 计算
22
f 6=2（2c 21c 2d 2+2c 1c 2d 1+a 1c 2d 2+
22
a 1a 2c 2d 1+a 1a 2c 2d 2+a 22c 1d 2+b 1b 2c 2d 1d 2+b 1b 2c 1d 1d 2）/
2b 1c 1c 22/（（b 1c 2－b 2c 1）
2
+（c 1a 2－c 2a 1）
2
+（a 1b 2－a 2b 1）2］·
2
［（c 3d 4b 4d 3）/（b 3c 4－b 4c 3）2］+［2（2c 21c 2d 2+2c 1c 2d 1+22a 21c 2d 2+a 1a 2c 2d 1+a 1a 2c 2d 2+a 2c 1d 2+b 1b 2c 2d 1d 2+
b 1b 22c 1d 1d 2）/（（b 1c 2－b 2c 1）［（2b 1b 2）2（c 3d 4）
2
2
+（c 1a 2－c 2a 1）
2
+
（a 1b 2－a 2b 1）2）］·［（b 4d 3）/（b 3c 4－b 4c 3）］=
2
+（b 1c 2+b 2c 1）2b 24d 3+
2
（（b 1c 2－b 2c 1）
2
+（c 1a 2－c 2a 1）
2
+（a 1b 2－a 2b 1）2）
（b 1d 2+b 2d 1）2（b 3c 4－b 4c 3）
+
F 6i =W 6i ·f 6+h 3（i =1，2，3，…）
2（b 1b 2）c 3d 4（a 1d 2+a 2d 1）（b 1d 2+b 2d 1）+
2（b 1b 2）c 3d 4（b 1c 2+b 2c 1）b 4d 3+
2（b 1c 2+b 2c 1）b 4d 3（b 1d 2+b 2d 1）（b 3c 4－b 4c 3）］/［（b 3c 4－b 4c 3）2·（（b 1c 2－b 2c 1）
2
Alice 将序列F 6i 发送给Bob 。其中h 3是Alice 生成的随机数，
1
③Bob 用OT m 不经意传输选择F 6k =W 6k ·f 6+h 3。
g ）根据点积协议Alice 得Q 1=r 1k e 1+n 1，其中r 1k 是步骤a ）中选择W 1K 时的随机数，同理Alice 可以得到Q 2=r 3k e 3+n 2和Q 3=r 5k e 5+n 3。
h ）同理Bob 得到P 1=t 2k ·f 2+S 1，其中t 2k 是步骤b ）中选择F 2时的随机数，同理可以得到P 2=t 4k ·f 4+s 2和P 3=t 4k ·f 4+s 3。
i ）Bob 计算n =n 1+n 2+n 3，Alice 计算并把n 发给Alice ，s =s 1+s 2+s 3，并把s 发给Bob 。
j ）Alice 计算
M =W 1k +W 3k +W 5k －Q 1－Q 2－Q 3+n =（F 1K ·e 1+t 1）+（F 3K ·e 3+t 2）+（F 5K ·e 5+t 3）－
（r 1k e 1+n 1）－（r 3k e 3+n 2）－（r 5k e 5+n 3）+（n 1+n 2+n 3）=（f 1·e 1+f 3·e 3+f 5·e 5）
+（c 1a 2－c 2a 1）
2
2
+
（a 1b 2－a 2b 1）2）］+［（a 1b 2+a 2b 1）2（c 3d 4）
+
2
22
（a 1c 2+a 2c 1）2b 24d 3+（a 1d 2+a 2d 1）（b 3c 4－b 4c 3）
+
2（a 1b 2+a 2b 1）c 3d 4（a 1d 2+a 2d 1）（b 3c 4－b 4c 3）+
2（a 1b 2+a 2b 1）c 3d 4（a 1c 2+a 2c 1）b 4d 3+2（a 1c 2+a 2c 1）b 4d 3（a 2d 1+a 2d 1）（b 3c 4－b 4c 3）］/［（b 3c 4－b 4c 3）2·（（b 1c 2－b 2c 1）
2
+（c 1a 2－c 2a 1）
22
2
+
（a 1b 2－a 2b 1）2）］+［（b 2c 1+b 1c 2）2（c 3d 4）
22
（2c 1c 2）2b 24d 3+（c 1d 2+c 2d 1）（b 3c 4－b 4c 3）
++
2（b 2c 1+b 1c 2）c 3d 4（c 1d 2+c 2d 1）（b 3c 4－b 4c 3）+
2（b 2c 1+b 1c 2）c 3d 4（2c 1c 2）b 4d 3+2（c 1d 2+c 2d 1）b 4d 3（c 1c 2）（b 3c 4－b 4c 3）］/
［（b 3c 4－b 4c 3）2·（（b 1c 2－b 2c 1）
（（a 1A a 1+a 2A a 2）（c 1a 2－c 2a 1）
222
+（c 1a 2－c 2a 1）
2
+（a 1b 2－a 2b 1）2］=
2
+（b 1A a 1+b 2A a 2）
+
2
k ）Bob 计算
N =F 2k +F 4k +F 6k －P 1－P 2－P 3+s =（W 2i ·f 2+h 1）+（W 4k ·f 4+h 2）+（W 6k ·f 6+h 3）－（t 2k ·f 2+s 1）－（t 4k ·f 4+s 2）－（t 4k ·f 4+s 3）+
（s 1+s 2+s 3）=f 2·e 2+f 4·e 4+f 6·e 6
（c 1A a 2+c 2A c 2）2）/（（b 3c 4－b 4c 3）2（b 1c 2－b 2c 1）
+（a 1b 2－a 2b 1）2））
+
2. 3. 2安全性证明
在该协议中，对于Alice 和Bob 来说，通过自己知道的中间Alice 结果是无法推算出对方私有信息的。例如在步骤a ）中，W 1K =F 1K ·e 1+t 1，知道f 1，但是Alice 不知道t 1，无法计算e 1，同样地Bob 并不知道Alice 选择的第k 项是什么，所以也无法即便Bob 把m 种可能都进行猜想，把m 个W 1K 值分别获知f 1，
W 12=（f 2+r 12）·e 1+计算，得到W 11=（f 1+r 11）·e 1+t 1，t 1，…，W 1m =（f 1+r 1m ）·e 1+t 1，即m 个（m +1）元一次方程组，
l ）Alice 把M 发给Bob 计算d =同时Bob 把N 发
给Alice 计算d ，各自得到计算结果。2. 32. 3. 1
协议分析正确性证明
M +N =（（a 1A a 1+a 2A a 2）
2
2
由于协议最后的结果是M +N 只需证明：
+（b 1A a 1+b 2A a 2）
2
2
+
2
由线性代数
+
［12］
的知识可知无法得到唯一确定的f 1，同理也无
（c 1A a 1+c 2A a 2））/（（b 3c 4－b 4c 3）（b 1c 2－b 2c 1）
（c 1a 2－c 2a 1）
2
f 5。同样地，Alice 无法获得e 2、e 4、e 6。法得到f 3、
步骤j ） l ）也用此原理保证计算的安全性。
Alice 和Bob 只知道自己的直线位置最终协议执行结束，
只能推算出以自己的直线为轴、以距离d 旋和与对方的距离，
+（a 1b 2－a 2b 1）2））
即可知道协议是正确的。
d =M +N =
f 1·e 1+f 3·e 3+f 5·e 5+f 2·e 2+f 4·e 4+f 6·e 6=［（（a 1b 1+a 2b 1）（（b 1c 2－b 2c 1）
2
2
2
2
+（2b 1b 2）
2
22
+（b 2c 1+b 1c 2））/+（a 1b 2－a 2b 1）2）］·
2
2
转出的曲面上所有直线，而不知道对方的直线具体是哪一条。
+（c 1a 2－c 2a 1）
3结束语
本文假设参与双方都处于半诚实模型，提出了一种关于空
［（c 3d 4）/（b 3c 4－b 4c 3）］+［（（a 1d 2+a 2d 1）（b 1d 2+b 2d 1）（c 1a 2－c 2a 1）
22
+
2
+（c 1d 2+c 2d 1）2）/（（b 1c 2－b 2c 1）
+
+（a 1b 2－a 2b 1）2）］·［（b 3c 4－b 4c 3）2/间两平行直线间距离的安全计算协议。在双方各持有一条私有空间直线的前提下，安全计算两条空间平行直线的距离，本协议可以保证双方在计算得到正确结果的前提下，依旧无法获得对方的输入。若双方持有多条直线，可重复调用该协议。但
22
2
（b 3c 4－b 4c 3）2］+［2（a 21b 1d 1+a 1a 2b 2d 1+a 2b 2d 1+
22
2b 21b 2d 2+2b 1b 2d 1+b 2c 1d 2+b 2c 1c 2d 1+
b 1c 1c 2d 2+b 1c 22d 1）/（b 1c 2－b 2c 1）（b 1c 2+b 2c 1）
2
2
2
+（c 1a 2－c 2a 1）
2
2
+
++
（a 1b 2－a 2b 1）2］·［（c 3d 4/（b 4c 3－b 4c 3）］+［（（a 1c 2+a 2c 1）
+（2c 1c 2））/（（b 1c 2－b 2c 1）
+（c 1a 2－c 2a 1）
协议的交互次数多，降低了计算效率。这也是以后工作的主要研究方向。
(下转第1535页)
第5期能伪造的。
定理2证明
刘志远:一个安全的无证书签密方案
参考文献：
基于DL 问题困难性假设，本文的签密方案对于假定敌手拥有系统的主私钥s ，但是没有替换用户
·1535·
［1］DIFFIE W ，HELLMAN M E．New directions in cryptography ［J ］．
IEEE Trans on Information Theory ，1976，22(6) :644-654．［2］SHAMIR A．Identity-based cryptosystems and signatures schemes
［C ］//Procof CRYPTO on Advances in Cryptology．Berlin :Springer-Verlag ，1985:47-53．
［3］AL-RIYAMI S S ，PATERSON K G．Certificateless public key cryptog-C ］//Procof the 9th International Conference on the Theory raphy ［
and Application of Cryptology and Information Seaurity．Berlin :Spring-er-Verlag ，2003:452-473．
［4］ZHENG Yu-liang．Digital signcryption or how to achieve cost (signa-ture ＆encryption ) ＜＜cost (signature ) +cost (encryption ) ［C ］//Proc of the 17th Annual International Cryptology Conference．Berlin :Springer-Verlag ，1997:165-179．
［5］BARBOSA M ，FARSHIM P．Certificateless signcryption ［C ］//Procof
第二类攻击者是安全的。
公钥的能力。由于敌手拥有系统的主私钥s ，所以他可以很容易地计算用户A 的部分私钥D ID 。但是要伪造密文σ，敌手必这相当于在群G 1求解离散对须使用户的部分公钥P ID part =xP ，
计算V =rH 1（ID A ）+hS A 得到的密文数问题。而敌手伪造x w ，
W ，h ，V ）是不能通过Bob 的检验的。因此本文的方案σw =（c ，
是能够抵御第二类攻击的。3. 3
效率分析
本文将运算（p ）、点乘运算（mul ）和指数运算（exp ）三个方12］进行了比较。比较结果如表1所示。面的计算量与文献［
表1
方案12］文献［本文方案
方案的计算开销比较
Unsigncrypt
mul 32
exp 01
p 33
mul 30
Signcrypt exp 02
p 11
ACM Symposium on Infomation ，Computer and Communications Secu-2008:369-372．rity．New York :ACM Press ，
［6］ARANHA D ，CASTRO R．Efficient certificateless signcryption ［EB /
OL ］．(2008) ．http ://sbseg2008．inf．ufrgs．br /proceedings/data/pdf /st03_Ol_resumo．pdf．
［7］WU C H ，CHEN Z X．A new efficient cenificateless signcryption
C ］//Procof ISISE．2008:66l-664．scheme ［
［8］SHARMILA D S ，VIVEK S S ，PANDU R C．On the security of certif-Report 2009/298［R ］．［S．l．］:Cryp-icateless signcryption schemes ，tology ePrint Archive ，2009．
［9］LI Fa-gen ，SHIRASE M ，TAKAGI T．Certificateless hybrid signcryp-tion ［C ］//Procof the 5th International Conference on Information Se-Verlag ，2009:112-curity Practice and Experience．Berlin :Springer-123．
［10］张磊，张福泰．一类无证书签名方案的构造方法［J ］．计算机学
2009，32(5) :940-945．报，
［11］刘文浩，许春香．无双线性配对的无证书签密方案［J ］．软件学
2011，22(8) :1918-1926．报，
［12］陈明，．计算机应用吴开贵，何盼．一种新的无证书签密方案［J ］
2011，28(10) :3799-3802，3822．研究，
在有预计算的情况下，从表1可以看出，本文的方案在指12］在点乘运算方面总但文献［数运算方面虽然有三次运算，
10］构共比本文的方案多4次，并且本文的方案是基于文献［12］其签密长度比文献［更短，因此本文方案能更好造而成的，
地适应计算量受限的环境。
4结束语
无证书密码体制很好地克服了基于身份密码体制中固有
的密钥托管问题和消除了基于传统公钥基础设施中公钥证书的复杂性管理问题，近年来得到了广泛的应用。本文提出了一个安全的无证书签密方案，在较强的安全模型下对用该方法所本文方案是能够构造的方案的安全性进行了证明。结果表明，
抵御保密性、不可伪造性和可否认性等攻击的。进一步提高无证书签密方案的安全性能以及设计能很好地适应对计算量受限的环境（如Ad hoc 网络环境）的无证书签密方案，将是笔者需要重点研究的课题。
(上接第1532页)
参考文献：
［1］YAO A C．Protocols for secure computations ［C ］//Procof the 23rd
Annual Symposium on Foundations of Computer Science．Washington DC :IEEE Computer Society ，1982:160-164．
［2］GOLDREICH O ，MICALI S ，WIGDERSON A．How to play any mental
game ［C ］//Procof the 19th Annual ACM Conference on Theory of Computing．New York :ACM Press ，1987:218-229．
［3］ATALLAH M J ，DU Wen-liang．Secure multi-party computational ge-ometry ［C ］//Procof the 7th International Workshop on Algorithms Verlag ，2001:165-179．and Data Structures．Berlin :Springer-［4］罗永龙，黄刘生，荆巍巍，等．保护私有信息的叉积协议及其应用
［J ］．计算机学报，2007，30(2) :248-254．
［5］LI Shun-dong ，DAI Yi-qi．Secure two-party computational geometry
［J ］．Journal of Computer Science and Technology ，2005，20(2) :258-263．
［6］刘文，．电子学王永滨．安全多方信息比较相等协议及其应用［J ］
2012，40(5) :871-876．报，［7］程文娟，董莹莹，汪庆，等．有关保护私有信息的三角不等式判定
J ］．合肥工业大学学报:自然科学版，2012，35(5) :625-问题研究［
628．
［8］徐滨，．贵州大彭长根．恶意模型下公平的安全两方计算协议［J ］
2012，29(1) :75-78，87．学学报:自然科学版，［9］DU Wen-liang ，ATALLAH M J．Secure multi-party computation prob-lems and their applications :a review and open problems ［C ］//Procof 2001:Workshop on New Security Paradigms．New York :ACM Press ，11-20．
［10］杨锦钜．用一般方程表示的空间两平行直线间的距离公式［J ］．1990，8(4) :81-87．佛山大学佛山师专学报:理工版，
［11］BRASSARD G ，CREPEAU C ，ROBERT J M ，All-or-nothing disclo-sure of secrets ［C ］//Procof CRYPTO on Advances in Cryptology．Berlin :Springer-Verlag ，1986:234-238．
［12］王萼芳，石生明．高等代数［M ］．3版．北京:高等教育出版社，
2003．
第30卷第5期2013年5月计算机应用研究
Application Research of Computers Vol．30No．5May 2013
空间两平行直线间距离的保密计算协议
辛
摘
*
欣，郝林，汤瑜
(云南大学信息学院，昆明650091)
要：针对半诚实模型提出了空间两平行直线间距离的保密计算协议。确保互不信任的参与方分别输入各
自隐私信息合作计算，同时保持各自信息的隐私性，并且不能通过中间结果计算出其他参与方输入的隐私信息，最终准确得到两平行线间距离，并且在理论上证明了协议的正确性和安全性。关键词：安全多方计算; 点积协议; 保护隐私的计算几何中图分类号：TP309
文献标志码：A
文章编号：1001-3695(2013) 05-1530-03
3695．2013．05．064doi ：10．3969/j．issn．1001-
Privacy-preserving computational protocol on minimum distance
between two three-dimension parallel straight line
XIN Xin ，HAO Lin ，TANG Yu
（School of Information Science ＆Engineering ，Yunnan University ，Kunming 650091，China ）
Abstract ：This paper proposed a privacy-preserving computational protocol on the minimum distance between two three-dimension parallel straight lines based on semi-honesty model．Every participant in semi-honesty model inputted his informa-tion and no one tend to leak the information to others．They could not get others ’private information by the intermediate re-sults except sharing the output．Finally ，this protocol outputs the distance between two parallel straight lines correctly．It gave the correctness and security proof．
Key words ：secure multiparty computation （SMC ）；dot product protocol ；privacy-preserving computational geometry （PPCG ）
0引言
Alice 拥有秘密输入向量X =（x 1，x 2，…，假设有两个参与者，
x n ），Bob 拥有秘密输入向量Y =（y 1，y 2，…，y n ），他们希望进行协作计算并在协议结束后Alice 得到值W A =X i ·Y i +r B （r B 是Bob 选取的一个随机值）。同时要保证Alice 不能从W A 中得
也不能从已知的信息中推出任何有关Y i 的信到有关的r B 值，
Bob 不能得到W A 的值，息；同理，也不能推出有关X i 的信息。大多数安全多方计算问题的解决都需要保密点积协议，因此它
在密码学协议中占有一席之地。1. 2
半诚实模型(semi-honest model)
一般来说，在安全多方计算过程中，半诚实的参与方能严格执行协议的各个步骤，不会中途强行退出或恶意掺入虚假数据，但同时可能保留所有能够收集到的中间数据，试图通过这些数据推测其他参与方的秘密输入。1. 3
空间两平行直线间距离
［10］
近几年安全多方计算（SMC ）问题成为国际密码学界一个
［1］
研究热点。SMC 最初是被Yao 提出并进行了研究，随后
［2］
Goldreich 等人作了进一步研究。随着合作计算与隐私保护
SMC 被引入到了各个应用领域，越来越受到人们重视，保护隐
私的计算几何就是其中之一。
保护隐私的计算几何（PPCG ）是指互不信任的参与方分别
线、多边形等）以求解某几何问题，同时输入隐私信息（如点、
保持各自信息的隐私性，并且不能通过中间结果计算出其他参
与方输入的隐私信息。PPCG 主要用来研究计算几何中的信息安全问题，尤其是分布式计算中合作用户的隐私保护问题。Atallah 等人［3］首次将安全多方计算引入计算几何领域。目前
4］在半诚实模型下设计了有一些研究成果已经发表。文献［
保护私有信息的叉积协议，可用于解决很多其他的保护私有信
5］研究了两点间距离和点与圆形、息的计算几何问题；文献［
6］椭圆区域的关系问题；文献［研究了安全多方信息比较相等7］协议及其应用；文献［研究了有关保护私有信息的三角不等8］研究了恶意模型下公平的安全两方计算式判定问题；文献［
协议。
L 2，空间两条平行线L 1、其方程分别为
L 1：L 2：
{{
π1：a 1x +b 1y +c 1z +d 1=0π2：a 2x +b 2y +c 2z +d 2=0π3：a 3x +b 3y +c 3z +d 3=0π4：a 4x +b 4y +c 4z +d 4=0|A a 1·n 1+A a 2·n 2|
两条平行线的距离为d ：
d =
|b 3c 4－b 4c 3|·|n 1·n 2|
1
1. 1
背景知识
保密点积协议
9］该问题最初被Du 等人在文献［中提出，协议概述如下：
收稿日期：2012-07-21; 修回日期：2012-09-09
=
（（a 1A a 1+a 2A a 2，b 1A a 1+b 2A a 2，c 1A a 1+c 2A a 2））/
（|b 3c 4－b 4c 3|
b 1c 2－b 2c 1）+（c 1a 2－c 2a 1）
+（a 1b 2－a 2b 1））
基金项目：云南省自然科学基金资助项目(2010ZC160)
作者简介：辛欣(1987-) ，女(蒙古族) ，内蒙古赤峰人，硕士，主要研究方向为信息安全(xinxin_0224@163．com ) ; 郝林(1955-) ，男，教授，主要研究方向为信息安全; 汤瑜(1986-) ，男，硕士，主要研究方向为信息安全．
第5期
其中：A a 1是行列式|A |的代数余子式：
b 2
A a 1=
b 3b 4
c 2c 3c 4
d 2
d 3，A a 2=d 4
辛欣，等:空间两平行直线间距离的保密计算协议
Bob 有一条私有直线L 2：
·1531·
b 1b 3b 4
c 1c 3c 4
d 1d 3d 4
{
输出
2
π3ʒ a 3x +b 3y +c 3z +d 3=0π4ʒ a 4x +b 4y +c 4z +d 4=0
Alice 与Bob 合作计算距离d 。
2
n 1是平面πi 的法向量。
d 2=（（a 1A a 1+a 2A a 2）
（c 1a 2－c 2a 1）
2
2
a ）①Alice 计算：
+（b 1A a 1+b 2A a 2）
+
2
f 1=（（a 1b 2+a 2b 1）
+
（（b 1c 2－b 2c 1）
2
+（2b 1b 2）
22
+（b 2c 1+b 1c 2）2）/+（a 1b 2－a 2b 1）2）
（c 1A a 1+c 2A a 2）2）/（（b 3c 4－b 4c 3）2（（b 1c 2－b 2c 1）
+（a 1b 2－a 2b 1）2））
+（c 1a 2－c 2a 1）
…，r 1m ｝，Alice 计算F 1i =f 1+r 1i 并生成随机序列R 1i =｛r 11，
（i =1，2，3，…），并将序列F 1i 发送给Bob 。
22
W 1i =F 1i ·e 1+t 1②Bob 计算e 1=（c 3d 4）/（b 3c 4－b 4c 3），
1. 4
［］
不经意传输（oblivious transfer ）11
不经意传输协议简称为OT 协议，是一种可保护隐私的双方通信协议，可以使通信双方以一种选择模糊化的方式进行。通常情况下，不经意传输协议有两个参与者，即发送方A 和接A 掌握n 个秘密：s 1，s 2，s 3，…，s n 。一个不经意传输协收方B ，
议要满足以下要求：
a ）如果A 和B 诚实地执行协议，那么最后B 得到秘密s i ，B 对A 可以把i 理解为它的一个选择，并且要求除了s i 以外，…，s i －1，s i +1，…，s n 一无所知。的其他秘密s 1，
b ）协议完成后，A 对B 的选择i 一无所知，也就是A 不知道B 到底选择了哪个秘密。
（i =1，2，3，…）。其中t 1是Bob 生成的随机数，Bob 将序列W 1i 发给Alice 。
③Alice 用OT m 不经意传输选择。
W 1K =F 1K ·e 1+t 1
1
b ）①Bob 计算e 2=（b 4c 3）2/（b 3c 4－b 4c 3）2，并生成随机序…，t 2m ｝，Bob 计算W 2i =e 2+t 2i （i =1，2，3，…），列T 2i =｛t 21，并将序列W 2i 发给Alice 。
②Alice 计算：
f 2=（（a 1c 2+a 2c 1）
2
+（b 1c 2+b 2c 1）
2
2
+（2c 1c 2）2）/
2
2. 1
空间两平行直线间距离的保密计算协议
问题描述和基本思想问题描述
Alice 有一条私有直线L 1：假设有两个参与方，
（（b 1c 2－b 2c 1）2）+（c 1a 2－c 2a 1）+（a 1b 2－a 2b 1）2）
F 2i =W 2i ·f 2+h 1（i =1，2，3，…），其中h 1是Alice 生成的随机数。Alice 将序列F 2i 发送给Bob 。
1
③Bob 用OT m 不经意传输选择F 2k =W 2k ·f 2+h 1。
2. 1. 1
c ）①Alice 计算
f 3=（（a 1d 2+a 2d 1）（（b 1c 2－b 2c 1）
22
{{
距离d ：
π1ʒ a 1x +b 1y +c 1z +d 1=0π2ʒ a 2x +b 2y +c 2z +d 2=0π3ʒ a 3x +b 3y +c 3z +d 3=0π4ʒ a 4x +b 4y +c 4z +d 4=0
+（b 1d 2+b 2d 1）
2
2
+（c 1d 2+c 2d 1）2）/
+（c 1a 2－c 2a 1）+（a 1b 2－a 2b 1）2）
Bob 有一条私有直线L 2：
…，r 3m ｝，Alice 计算F 3i =f 3+r 3i 并生成随机序列R 3i =｛r 31，
（i =1，2，3，…），并将序列F 3i 发送给Bob 。
②Bob 计算
e 3=（b 3c 4－b 4c 3）2/（b 3c 4－b 4c 3）W 3i =F 3i ·e 3+t 2（i =1，2，3，…）
2
且L 1与L 2平行，在不泄露各自信息的情况下计算两条直线的
|A a 1·n 1+A a 2·n 2||b 3c 4－b 4c 3|·|n 1·n 2|
d ==
Bob 将序列发给Alice 。其中t 3是Bob 生成的随机数，
1
③Alice 用OT m 不经意传输选择W 3K =F 3K ·e 3+t 2。
（（a 1A a 1+a 2A a 2，b 1A a 1+b 2A a 2，c 1A a 1+c 2A a 2））/
（|b 3c 4－b 4c 3|
（b 1c 2－b 2c 1）+（c 1a 2－c 2a 1）
d ）Bob 计算e 4=c 3d 4b 4d 3/（b 3c 4－b 4c 3）2，并生成随机序列T 4i =｛t 41，…，t 4m ｝，Bob 计算W 4i =e 4+t 4i （i =1，2，3…），并将序列W 4i 发给Alice 。
②Alice 计算
2
f 4=2（a 21b 2c 2+a 1a 2b 2c 1+a 1a 2b 2c 2+a 2b 1c 1+
2222
2b 21c 2+2b 1b 2c 1+2b 2c 1c 2+2b 1c 1c 2）/
+（a 1b 2－a 2b 1））
2. 1. 2协议的主要思想
距离计算协议基于前面介绍的基本协议和基本几何知识秘密地判定两条空间直线间的距离。基于Alice 的私有信息b 1，c 1，d 1，a 2，b 2，c 2，d 2｝，Bob 产生一个产生一个向量A =｛a 1，
b 3，c 3，d 3，a 4，b 4，c 4，d 4｝，Alice 只计算函数f i ，运用向量B =｛a 3，
b 1等隐藏，并且Bob 不点积协议构造一系列的函数将元素a 1、
能计算出这些元素。Bob 只计算e i ，运用点积协议构造一系列b 3等隐藏，的函数将元素a 3、并且Alice 不能计算出这些元素。
1
Alice 和Bob 分别选择出W i 和T i 即为符通过运用OT m 协议，
（（b 1c 2－b 2c 1）
2
+（c 1a 2－c 2a 1）
2
+（a 1b 2－a 2b 1）2）
2，3…）。并生成随机序列F 4i =W 4i ·f 4+h 2（i =1，
h 2是Alice 生成的随机数，Alice 将序列F 4i 发送给Bob 。其中，
1
③Bob 用OT m 不经意传输选择F 4k =W 4k ·f 4+h 2。
e ）①Alice 计算
22
f 5=2（a 21b 2d 2+a 1a 2b 2d +a 2b 2d 1+2b 1b 2d 2+222b 1b 22d 1+b 2c 1d 2+b 2c 1c 2d 1+b 1c 1c 2d 2+b 1c 2d 1）/
合要求的元素。最后通过Alice 和Bob 分别计算辅助数据Q 、n 、P 、s 。将d 通过上述过程还原为d =2. 2
安全空间两平行直线的距离计算协议输入：Alice 有一条私有直线L 1：
（（b 1c 2－b 2c 1）
2
+（c 1a 2－c 2a 1）
2
+（a 1b 2－a 2b 1）2）
…，r 5m ｝，Alice 计算F 5i =f 5+r 5i 并生成随机序列R 5i =｛r 51，
（i =1，2，3，…），并将序列F 5i 发送给Bob 。
W 5i =F 5i ·e 5+t 3（i =1，②Bob 计算e 5=c 3d 4/（b 3c 4－b 4c 3），
{
π1ʒ a 1x +b 1y +c 1z +d 1=0π2ʒ a 2x +b 2y +c 2z +d 2=0
·1532·
计算机应用研究第30卷
2，3，…），Bob 将序列发给Alice 。其中t 2是Bob 生成的随机数，
1
③Alice 用OT m 不经意传输选择W 5K =F 5K ·e 5+t 3
（a 1b 2－a 2b 1）2）］·［（b 4c 3）2/（b 3c 4－b 4c 3）2］+［2（a 21b 2c 2+
2222a 1a 2b 2c 1+a 1a 2b 2c 2+a 22b 1c 1+2b 1c 2+2b 1b 2c 1+2b 2c 1c 2+
f ）①Bob 计算e 6=b 4d 3/（b 3c 4－b 4c 3），并生成随机序列T 6i =｛t 61，…，t 6m ｝，Bob 计算w 6i =e 6+t 6i （i =1，2，3，…），并将序列W 6i 发给Alice 。
②Alice 计算
22
f 6=2（2c 21c 2d 2+2c 1c 2d 1+a 1c 2d 2+
22
a 1a 2c 2d 1+a 1a 2c 2d 2+a 22c 1d 2+b 1b 2c 2d 1d 2+b 1b 2c 1d 1d 2）/
2b 1c 1c 22/（（b 1c 2－b 2c 1）
2
+（c 1a 2－c 2a 1）
2
+（a 1b 2－a 2b 1）2］·
2
［（c 3d 4b 4d 3）/（b 3c 4－b 4c 3）2］+［2（2c 21c 2d 2+2c 1c 2d 1+22a 21c 2d 2+a 1a 2c 2d 1+a 1a 2c 2d 2+a 2c 1d 2+b 1b 2c 2d 1d 2+
b 1b 22c 1d 1d 2）/（（b 1c 2－b 2c 1）［（2b 1b 2）2（c 3d 4）
2
2
+（c 1a 2－c 2a 1）
2
+
（a 1b 2－a 2b 1）2）］·［（b 4d 3）/（b 3c 4－b 4c 3）］=
2
+（b 1c 2+b 2c 1）2b 24d 3+
2
（（b 1c 2－b 2c 1）
2
+（c 1a 2－c 2a 1）
2
+（a 1b 2－a 2b 1）2）
（b 1d 2+b 2d 1）2（b 3c 4－b 4c 3）
+
F 6i =W 6i ·f 6+h 3（i =1，2，3，…）
2（b 1b 2）c 3d 4（a 1d 2+a 2d 1）（b 1d 2+b 2d 1）+
2（b 1b 2）c 3d 4（b 1c 2+b 2c 1）b 4d 3+
2（b 1c 2+b 2c 1）b 4d 3（b 1d 2+b 2d 1）（b 3c 4－b 4c 3）］/［（b 3c 4－b 4c 3）2·（（b 1c 2－b 2c 1）
2
Alice 将序列F 6i 发送给Bob 。其中h 3是Alice 生成的随机数，
1
③Bob 用OT m 不经意传输选择F 6k =W 6k ·f 6+h 3。
g ）根据点积协议Alice 得Q 1=r 1k e 1+n 1，其中r 1k 是步骤a ）中选择W 1K 时的随机数，同理Alice 可以得到Q 2=r 3k e 3+n 2和Q 3=r 5k e 5+n 3。
h ）同理Bob 得到P 1=t 2k ·f 2+S 1，其中t 2k 是步骤b ）中选择F 2时的随机数，同理可以得到P 2=t 4k ·f 4+s 2和P 3=t 4k ·f 4+s 3。
i ）Bob 计算n =n 1+n 2+n 3，Alice 计算并把n 发给Alice ，s =s 1+s 2+s 3，并把s 发给Bob 。
j ）Alice 计算
M =W 1k +W 3k +W 5k －Q 1－Q 2－Q 3+n =（F 1K ·e 1+t 1）+（F 3K ·e 3+t 2）+（F 5K ·e 5+t 3）－
（r 1k e 1+n 1）－（r 3k e 3+n 2）－（r 5k e 5+n 3）+（n 1+n 2+n 3）=（f 1·e 1+f 3·e 3+f 5·e 5）
+（c 1a 2－c 2a 1）
2
2
+
（a 1b 2－a 2b 1）2）］+［（a 1b 2+a 2b 1）2（c 3d 4）
+
2
22
（a 1c 2+a 2c 1）2b 24d 3+（a 1d 2+a 2d 1）（b 3c 4－b 4c 3）
+
2（a 1b 2+a 2b 1）c 3d 4（a 1d 2+a 2d 1）（b 3c 4－b 4c 3）+
2（a 1b 2+a 2b 1）c 3d 4（a 1c 2+a 2c 1）b 4d 3+2（a 1c 2+a 2c 1）b 4d 3（a 2d 1+a 2d 1）（b 3c 4－b 4c 3）］/［（b 3c 4－b 4c 3）2·（（b 1c 2－b 2c 1）
2
+（c 1a 2－c 2a 1）
22
2
+
（a 1b 2－a 2b 1）2）］+［（b 2c 1+b 1c 2）2（c 3d 4）
22
（2c 1c 2）2b 24d 3+（c 1d 2+c 2d 1）（b 3c 4－b 4c 3）
++
2（b 2c 1+b 1c 2）c 3d 4（c 1d 2+c 2d 1）（b 3c 4－b 4c 3）+
2（b 2c 1+b 1c 2）c 3d 4（2c 1c 2）b 4d 3+2（c 1d 2+c 2d 1）b 4d 3（c 1c 2）（b 3c 4－b 4c 3）］/
［（b 3c 4－b 4c 3）2·（（b 1c 2－b 2c 1）
（（a 1A a 1+a 2A a 2）（c 1a 2－c 2a 1）
222
+（c 1a 2－c 2a 1）
2
+（a 1b 2－a 2b 1）2］=
2
+（b 1A a 1+b 2A a 2）
+
2
k ）Bob 计算
N =F 2k +F 4k +F 6k －P 1－P 2－P 3+s =（W 2i ·f 2+h 1）+（W 4k ·f 4+h 2）+（W 6k ·f 6+h 3）－（t 2k ·f 2+s 1）－（t 4k ·f 4+s 2）－（t 4k ·f 4+s 3）+
（s 1+s 2+s 3）=f 2·e 2+f 4·e 4+f 6·e 6
（c 1A a 2+c 2A c 2）2）/（（b 3c 4－b 4c 3）2（b 1c 2－b 2c 1）
+（a 1b 2－a 2b 1）2））
+
2. 3. 2安全性证明
在该协议中，对于Alice 和Bob 来说，通过自己知道的中间Alice 结果是无法推算出对方私有信息的。例如在步骤a ）中，W 1K =F 1K ·e 1+t 1，知道f 1，但是Alice 不知道t 1，无法计算e 1，同样地Bob 并不知道Alice 选择的第k 项是什么，所以也无法即便Bob 把m 种可能都进行猜想，把m 个W 1K 值分别获知f 1，
W 12=（f 2+r 12）·e 1+计算，得到W 11=（f 1+r 11）·e 1+t 1，t 1，…，W 1m =（f 1+r 1m ）·e 1+t 1，即m 个（m +1）元一次方程组，
l ）Alice 把M 发给Bob 计算d =同时Bob 把N 发
给Alice 计算d ，各自得到计算结果。2. 32. 3. 1
协议分析正确性证明
M +N =（（a 1A a 1+a 2A a 2）
2
2
由于协议最后的结果是M +N 只需证明：
+（b 1A a 1+b 2A a 2）
2
2
+
2
由线性代数
+
［12］
的知识可知无法得到唯一确定的f 1，同理也无
（c 1A a 1+c 2A a 2））/（（b 3c 4－b 4c 3）（b 1c 2－b 2c 1）
（c 1a 2－c 2a 1）
2
f 5。同样地，Alice 无法获得e 2、e 4、e 6。法得到f 3、
步骤j ） l ）也用此原理保证计算的安全性。
Alice 和Bob 只知道自己的直线位置最终协议执行结束，
只能推算出以自己的直线为轴、以距离d 旋和与对方的距离，
+（a 1b 2－a 2b 1）2））
即可知道协议是正确的。
d =M +N =
f 1·e 1+f 3·e 3+f 5·e 5+f 2·e 2+f 4·e 4+f 6·e 6=［（（a 1b 1+a 2b 1）（（b 1c 2－b 2c 1）
2
2
2
2
+（2b 1b 2）
2
22
+（b 2c 1+b 1c 2））/+（a 1b 2－a 2b 1）2）］·
2
2
转出的曲面上所有直线，而不知道对方的直线具体是哪一条。
+（c 1a 2－c 2a 1）
3结束语
本文假设参与双方都处于半诚实模型，提出了一种关于空
［（c 3d 4）/（b 3c 4－b 4c 3）］+［（（a 1d 2+a 2d 1）（b 1d 2+b 2d 1）（c 1a 2－c 2a 1）
22
+
2
+（c 1d 2+c 2d 1）2）/（（b 1c 2－b 2c 1）
+
+（a 1b 2－a 2b 1）2）］·［（b 3c 4－b 4c 3）2/间两平行直线间距离的安全计算协议。在双方各持有一条私有空间直线的前提下，安全计算两条空间平行直线的距离，本协议可以保证双方在计算得到正确结果的前提下，依旧无法获得对方的输入。若双方持有多条直线，可重复调用该协议。但
22
2
（b 3c 4－b 4c 3）2］+［2（a 21b 1d 1+a 1a 2b 2d 1+a 2b 2d 1+
22
2b 21b 2d 2+2b 1b 2d 1+b 2c 1d 2+b 2c 1c 2d 1+
b 1c 1c 2d 2+b 1c 22d 1）/（b 1c 2－b 2c 1）（b 1c 2+b 2c 1）
2
2
2
+（c 1a 2－c 2a 1）
2
2
+
++
（a 1b 2－a 2b 1）2］·［（c 3d 4/（b 4c 3－b 4c 3）］+［（（a 1c 2+a 2c 1）
+（2c 1c 2））/（（b 1c 2－b 2c 1）
+（c 1a 2－c 2a 1）
协议的交互次数多，降低了计算效率。这也是以后工作的主要研究方向。
(下转第1535页)
第5期能伪造的。
定理2证明
刘志远:一个安全的无证书签密方案
参考文献：
基于DL 问题困难性假设，本文的签密方案对于假定敌手拥有系统的主私钥s ，但是没有替换用户
·1535·
［1］DIFFIE W ，HELLMAN M E．New directions in cryptography ［J ］．
IEEE Trans on Information Theory ，1976，22(6) :644-654．［2］SHAMIR A．Identity-based cryptosystems and signatures schemes
［C ］//Procof CRYPTO on Advances in Cryptology．Berlin :Springer-Verlag ，1985:47-53．
［3］AL-RIYAMI S S ，PATERSON K G．Certificateless public key cryptog-C ］//Procof the 9th International Conference on the Theory raphy ［
and Application of Cryptology and Information Seaurity．Berlin :Spring-er-Verlag ，2003:452-473．
［4］ZHENG Yu-liang．Digital signcryption or how to achieve cost (signa-ture ＆encryption ) ＜＜cost (signature ) +cost (encryption ) ［C ］//Proc of the 17th Annual International Cryptology Conference．Berlin :Springer-Verlag ，1997:165-179．
［5］BARBOSA M ，FARSHIM P．Certificateless signcryption ［C ］//Procof
第二类攻击者是安全的。
公钥的能力。由于敌手拥有系统的主私钥s ，所以他可以很容易地计算用户A 的部分私钥D ID 。但是要伪造密文σ，敌手必这相当于在群G 1求解离散对须使用户的部分公钥P ID part =xP ，
计算V =rH 1（ID A ）+hS A 得到的密文数问题。而敌手伪造x w ，
W ，h ，V ）是不能通过Bob 的检验的。因此本文的方案σw =（c ，
是能够抵御第二类攻击的。3. 3
效率分析
本文将运算（p ）、点乘运算（mul ）和指数运算（exp ）三个方12］进行了比较。比较结果如表1所示。面的计算量与文献［
表1
方案12］文献［本文方案
方案的计算开销比较
Unsigncrypt
mul 32
exp 01
p 33
mul 30
Signcrypt exp 02
p 11
ACM Symposium on Infomation ，Computer and Communications Secu-2008:369-372．rity．New York :ACM Press ，
［6］ARANHA D ，CASTRO R．Efficient certificateless signcryption ［EB /
OL ］．(2008) ．http ://sbseg2008．inf．ufrgs．br /proceedings/data/pdf /st03_Ol_resumo．pdf．
［7］WU C H ，CHEN Z X．A new efficient cenificateless signcryption
C ］//Procof ISISE．2008:66l-664．scheme ［
［8］SHARMILA D S ，VIVEK S S ，PANDU R C．On the security of certif-Report 2009/298［R ］．［S．l．］:Cryp-icateless signcryption schemes ，tology ePrint Archive ，2009．
［9］LI Fa-gen ，SHIRASE M ，TAKAGI T．Certificateless hybrid signcryp-tion ［C ］//Procof the 5th International Conference on Information Se-Verlag ，2009:112-curity Practice and Experience．Berlin :Springer-123．
［10］张磊，张福泰．一类无证书签名方案的构造方法［J ］．计算机学
2009，32(5) :940-945．报，
［11］刘文浩，许春香．无双线性配对的无证书签密方案［J ］．软件学
2011，22(8) :1918-1926．报，
［12］陈明，．计算机应用吴开贵，何盼．一种新的无证书签密方案［J ］
2011，28(10) :3799-3802，3822．研究，
在有预计算的情况下，从表1可以看出，本文的方案在指12］在点乘运算方面总但文献［数运算方面虽然有三次运算，
10］构共比本文的方案多4次，并且本文的方案是基于文献［12］其签密长度比文献［更短，因此本文方案能更好造而成的，
地适应计算量受限的环境。
4结束语
无证书密码体制很好地克服了基于身份密码体制中固有
的密钥托管问题和消除了基于传统公钥基础设施中公钥证书的复杂性管理问题，近年来得到了广泛的应用。本文提出了一个安全的无证书签密方案，在较强的安全模型下对用该方法所本文方案是能够构造的方案的安全性进行了证明。结果表明，
抵御保密性、不可伪造性和可否认性等攻击的。进一步提高无证书签密方案的安全性能以及设计能很好地适应对计算量受限的环境（如Ad hoc 网络环境）的无证书签密方案，将是笔者需要重点研究的课题。
(上接第1532页)
参考文献：
［1］YAO A C．Protocols for secure computations ［C ］//Procof the 23rd
Annual Symposium on Foundations of Computer Science．Washington DC :IEEE Computer Society ，1982:160-164．
［2］GOLDREICH O ，MICALI S ，WIGDERSON A．How to play any mental
game ［C ］//Procof the 19th Annual ACM Conference on Theory of Computing．New York :ACM Press ，1987:218-229．
［3］ATALLAH M J ，DU Wen-liang．Secure multi-party computational ge-ometry ［C ］//Procof the 7th International Workshop on Algorithms Verlag ，2001:165-179．and Data Structures．Berlin :Springer-［4］罗永龙，黄刘生，荆巍巍，等．保护私有信息的叉积协议及其应用
［J ］．计算机学报，2007，30(2) :248-254．
［5］LI Shun-dong ，DAI Yi-qi．Secure two-party computational geometry
［J ］．Journal of Computer Science and Technology ，2005，20(2) :258-263．
［6］刘文，．电子学王永滨．安全多方信息比较相等协议及其应用［J ］
2012，40(5) :871-876．报，［7］程文娟，董莹莹，汪庆，等．有关保护私有信息的三角不等式判定
J ］．合肥工业大学学报:自然科学版，2012，35(5) :625-问题研究［
628．
［8］徐滨，．贵州大彭长根．恶意模型下公平的安全两方计算协议［J ］
2012，29(1) :75-78，87．学学报:自然科学版，［9］DU Wen-liang ，ATALLAH M J．Secure multi-party computation prob-lems and their applications :a review and open problems ［C ］//Procof 2001:Workshop on New Security Paradigms．New York :ACM Press ，11-20．
［10］杨锦钜．用一般方程表示的空间两平行直线间的距离公式［J ］．1990，8(4) :81-87．佛山大学佛山师专学报:理工版，
［11］BRASSARD G ，CREPEAU C ，ROBERT J M ，All-or-nothing disclo-sure of secrets ［C ］//Procof CRYPTO on Advances in Cryptology．Berlin :Springer-Verlag ，1986:234-238．
［12］王萼芳，石生明．高等代数［M ］．3版．北京:高等教育出版社，
2003．