密码学报 ISSN 2095-7025 C N 10-1195/TN Journal of Cryptologic Rearch^ 2021, 8(1): 40-54 ©《密码学报》编辑部版权所有.
E-m a i l:j c r@c a c r n e t.o r g.c n h t t p://w w w.j c r.c a c r n e t.o r g.c n
T e l/Fax: +86-10-82789618
隐私保护的两方几何圆位置关系判定+
张明武张依梦'谌刚1
1.湖北工业大学计算机学院，武汉430068
2.密码科学技术国家重点实验室，北京100878
3.桂林电子科技大学计算机与信息安全学院，桂林541004
通信作者：张明武，E~mail: *******************
摘要：两圆间的位置关系判定问题是常见的几何计算问题之一.在保护两方各自输入圆信息的条件下，本文设计了一个隐私保护的两方几何圆位置关系判定方案，以实现在半诚实模型下安全地求解两圆间五种
位置关系.本文运用P a illie r同态加密技术实现了圆心间欧几里德距离的保密计算，通过将P a illie r明文 空间划分为两等长区间以实现解密结果在明文空间中正确映射的方法，提出隐私保护的欧几里德距离计算 协议.此外，基于该协议我们设计了一个隐私保护的两圆间位置关系判定协议，在未泄露两圆半径与圆心 等敏感信息的前提下提高了两方的计算效率.本文给出了方案具体的设计步骤、详细的安全性分析和实际 的性能測试.实验结果表明，在两圆相距较近和相距较远的情况下判定两圆相离、外切、相交、内切和内 含五种位置关系时，本方案均适用.同时，我们的方案具有计算复杂度不高及通信开销低等优势.
关键词：安全两方计算；隐私保枋；两圆位置判定；同态加密；欧几里德距离
中图分类号：TP309.7 文献标识码：A DOI: 10.13868/j.c n k i.j c r.000418
中文引用格式：张明武，张依梦，谌刚.隐私保护的两方几何圆位置关系判定丨J].密码学报，2021, 8(1): 40-54. [DOI: 10.ki.jcr.000418]
英文引用格式：ZHANG M W, ZHANG Y M, SHEN G, A privacy-prerving positional determining protocol for two geometry circles[J]. Journal of Cryptologic Rearch, 2021，8(1): 40-54. [DOI: 10.ki.jcr.000418]
A P riv a c y-P re s e rv in g P o s itio n a l D e te rm in in g P r o to c o l for Tw o
G e o m e tr y C ircles
Z H A N G Ming-W u1’2’3,Z H A N G Yi-Meng1，
2，SHEN Gang1
1.School of Compu t e r Science, Hubei University of Technology, W u h a n430068, China
2.State K e y Laboratory of Cryptology, Beijing 100878, China
3.School of Computer Science and Information Security, Guilin University of Electronic Technology, Guilin 541004, China
Corresponding author: Z H A N G Ming-Wu,E-mail:********************
*基金项目：国家自然科学基金（62072134, U2001205)；密码科学技术国家重点实验室开放课题；广西自然科学基金重点项目（2019JJD170020)；信息安全国家重点实验室开放课题（2020-MS-05)
Foundation: National Natural Science Foundation of China (62072134, U2001205); O pe n Fund of State Key Laboratory of Cryptology; Key Program of the Natural Science Foundation of Guangxi Pro
vince of China (2019JJD170020); Ope n Fund of State Key Laboratory of Information Security (2020-MS-05)
收稿日期•2020-01-16 定稿日期：202CM32-20
张明武等：隐私保护的两方几何圆位置关系判定41
Abstract:T he determ ination of the position relationship betw een two circles is one of th e com m on geometric calculation problems. In order to protect the privacy of the position inform ation of two parties, this paper designs a privacy-prerving scheme to determ ine the position relationship of two geometric circles which can solve the five position relations betw een two circles under th e m i-honest model. The propod schem e em ploys the Paillier encryption m ethod to com pute Euclidean distance of the centers cretly, then a privacy prerving com putation protocol of Euclidean distance is propod by dividing the plaintext space into two equal length intervals. T he protocol can achieve the correct mapping of the decrypted result in the plaintext space. In addition, a privacy-prerving com putation protocol of Euclidean distance is propod and a privacy-prerving positional determ ining protocol is propod for two geom etry circles, which improves the com putational efficiency o f both parties w ithout divulging the nsitive information such as the radius an
d center of the two circles. T his paper gives the specific design steps, detailed curity analysis and performance test o f the schem e. T he experim ental results show that, regardless whether the two circles are clo or far apart, the propod schem e is applicable to determ ine the five positional relations of two circles, i.e., being parated, circum scribed, intercted, inscribed, and contained. M eanwhile, the propod schem e has low com putational com plexity and low com m unication overhead.
Key words:cure two-party com putation; privacy protection; positional determ ination; hom om orphic encryption; Euclidean distance
i引言
几何位置关系的判定在实际中应用非常广泛.在军事系统中，两雷达在不同范围半径进行位置探测, 二者需要知道彼此探测区域的关系以判定是否彼此探测覆盖；另外，在社交网络中，基于地理位置信息进 行好友推荐，并判断用户间的位置关系是社交网络的重要因素[11.随着大数据和人工智能等技术的发展, 用户彼此间交互的信息量急速增加，这可能造成用户信息的泄露12,31.因此，在参与多方有效判定各种位 置关系的同时保护各自信息不被泄露是个不可忽视的问题141.
安全多方计算（S e c u r e M u l t i-p a r t y Computation,S M C)为隐私保护的位置判定问题提供了有
效 的解决思路，也为大多数学者的研宄提供了一个重要方法.安全统计分析[6'71、安全几何计算18'91以及安 全科学计算t l C)1等是常见的安全多方计算问题，而隐私保护的几何位置关系判定问题，是安全几何计算问 题的核心问题之一.针对该问题，提出了具体的点与圆（多边形”8，11-141、点与直线[15'161、及点与平面 间1^1等位置判定的解决方案.Li等人M l提出隐私保护的点与凸（凹）多边形位置关系判定协议，首
先提出的安全两方三角形面积计算协议，然后通过判定三角形面积的符号位来解决凸多边形中的点包含问 题.基于文献丨14]中利用三角形面积判定的思想，Chen等人W提出了点与凸多边形位置判定协议，基 于内积协议解决安全两方三角形面积计算问题，然而该协议仅适用于解决凸多边形点包含问题.而Zhang 等人1111提出利用高效的叉积协议以解决点与多边形的位置关系判定问题中，其多边形可为任意多边形.文献丨13]中提出隐私保护的判定点与圆、点与凸多边形位置关系的协议，用来秘密判定好友位置关系，即用户选择任意范围，通过与朋友进行安全的联合计算判断朋友是否在自己所选范围内，且该协议采用安全 两方余弦值计算协议，避免了复杂的密码算法.在解决隐私保护的点与直线间位置关系判定问题时，利用 安全内积协议来实现秘密点与秘密有向线间的位置判定由Yang等人1151提出，而同态加密算法增加了其 计算复杂度.Zhang等人1161提出保密判定点与线的位置关系协议，该协议基于判定点是否为一个方程的 解的思想并结合保密内积协议来解决该问题，保密内积协议主要通过构造一个不可逆的矩阵来保护点与直 线的隐私安全.在解决隐私保护的平面间位置关系判定
问题时，Li等人W给出了隐私保护的判断点与平 面的距离、直线与平面、以及两平面间的位置关系等问题的解决方案.
隐私保护的两圆位置关系判定中，参与两方各自输入秘密的圆的半径和圆心等信息，联合判定二方的 位置关系且不会泄露各自输入的信息.该类问题具有重要意义，例如，不同用户的社交圈中，在不泄露自身 好友信息的情况下判定是否具有共同社会交集且实现各用户社交信息的保密1181.为解决保密计算两圆公
42JoumaZ 〇/Crj/pfoiojic ■R eorc/i 密码学报 Vol.8, No.1，Feb.2021
切线问题，W a n g等人提出了安全计算两圆间的公切线协议，并实现隐私保护的路径规划问题.Y e等 人|2()1给出了计算两秘密输入的相交圆交点的协议.文献[21]提出了隐私保护椭圆相交判定方案.Liu等 人1221基于安全两数和平方、安全两实数关系判定和安全两点距离计算等三个子协议提出安全两方圆计 算协议，然而，他们只解决两圆相交、相离、外切三种关系的判定问题.另外，该协议需要多次调用子协议，所以这增加了系统的计算复杂度与通信开销.针对以上提出的问题，本文提出了一种新的方案以解决隐私 保护的两圆间位置关系判定问题.
1.1本文贡献
基于对传统的两圆位置判定方法的改进，本文设计一个隐私保护的两方几何圆位置关系判定协议以实 现安全的求解两圆间五种位置关系.本文的主要贡献如下：
(1) 给出了隐私保护的欧几里德距离计算协议.结合将P a i l l i e r明文空间划分的思想以实现对解密结
果进行正确映射，提出了隐私保护的欧几里德距离计算协议，提高了两方的计算效率.
(2) 提出一个隐私保护的两方几何圆位置判定协议.基于隐私保护的欧几里德距离计算协议，本文提
出高效解决隐私保护的判定两圆位置关系问题的方案，与相关方案采用不经意传输和内枳协议相 比，本文方案具有较低的计算复杂度和通信开销.
(3) 支持判定两圆的五种位置关系.除判定两圆相离、相切、相交三种位置，本文协议还支持判定两
圆内切、内含等位置关系.
2预备知识
2.1符号定义
为便于读者理解，本节给出本文所用的基本符号.
K：系统安全参数
P i：协议参与方（i =a，6)
(pka，s k a):Pa 的P a i l l i e r 公私钥对
fm]：消息m的密文
(sa,sb y.半诚实模型下pa，n的模拟器
C i：乃拥有的几何圆
〇i：Ci的圆心
Vi：Ci的半径
(x i,y i)：圆心 〇i
2.2两圆位置关系
如图1所不，两圆C a=<〇a，r a>与C6=<O f),r6>有以下五种位置关系，其中n是C i的半 径，〇i = (Zi,
=a,6)是C i的圆心.圆心距记为d=i/(x a —Xb)2+(ya—Vb)2，两圆间位置关系可由 以下（不）等式判定：
(1) 相离：d>r a+r b;
(2) 外切：c i=?•〇 +n>;
(3) 相交：|r a —n>| <<r a+r t;
(4) 内切：d= |r a —r b|;
(5) 内含：d< |r a —r f c|.
为方便比较，本方案将转化为计算d2 =(a:a-办)2+(j/a -j/b)2.
2.3安全模型
在安全多方计算协议中，敌手模型主要分为半诚实敌手模型与恶意敌手模型123].由于本协议的参与 方是半诚实的，本文只给出半诚实模型及安全性定义.
(1)半诚实模型：在半诚实模型下，参与者能正确地执行协议，在协议执行期间能得到所有中间结果，
并试图根据所得的中间结果得到额外信息.
张明武等：隐私保护的两方几何圆位置关系判定43
图1两圆位置关系
Figure 1 Positional relationship of two circles
Ca
(5)内含
(2)半诚实模型下的安全性定义：设有两个参与者P a 和P 6，输入分别为I 和y ，/ : {0, 1}* X {0,1}* {0,1丨* X
是一个概率性函数，7T 表示计算/的两方协议，协议7T 执行的过程中，和n 共同计算 /(z ,y
) = (/4〇;,2/)，/6(2：,2/))，计算结束后，Pa 得到 /a (a ;,j /)，尸6 得到 /6(:e , y ). V IE W J (;r ,y )和 V IEW ?〇r ，y )分别表示P a 和n 在7T 执行期间的视图，O U T P U T J (a :,y )和O U TP U TT (;r ,y )分别表示 &和幵的输出.若下列等式成立，称协议tt 安全地计算/，若存在两个多项式时间的模拟器和氏，
{S a (x , f a (x , y )), f b (x , v )}x ,y 6{o ,i }- = {V I E W ：(x , y ), O U T P U T ?(x , y )}x ,ye {o,iy
⑴{Sb (y , f b (x , y )), /a (x , j /)}x ,ye {o ,i }* s {V I E W ?(x , y ), O U T P U T ；(x , y )}x ,s 6{〇,i }>
⑵其中，i 是计算上不可区分的表示符号.
2.4同态加密算法
PaJllier 加密算法是一种常用的加法同态加密算法对于明文空间的任意两个消息r m 和m 2的密 文I r m l 和|[m 2l ，以及随机数€ Z d ，该算法满足以下面性质：
[m i ] ■ I m 2| = [mi + m 2l ， Jm]Q = [q • m ]
Paillier 加密算法包括三部分，具体描述如下：
•密钥生成算法（G e n )：给定安全参数为K ，生成两个大素数p 和g , |p | = |g | = k ，且n = pg ，计 算A = lcm(p — 1，g — 1)，其中lcm (a , b )表不两数a 和6的最大公约数.随机选取a € 置 p = 1 + a n (m o d n 2)，定义函数 Z /(;r ) = (a : — l )/n .置公钥 pk = (n ,g )和密钥 sk =入.
•加密算法（E n c )：对明文消息m e ，随机选取r e 加密算法输出：
c = gm ■ rn (m o
d n 2)
•解密算法（D e c )：对密文c ，首先判定c £ Z ；；2是否成立，若成立则解密算法利用密钥sk = A 计 算：
L (cx (m o d n 2))L (gA (m o d n 2))
(m o d n )定理1 1251 Paillier 加密方案中不能直接对负数进行加密.
给出对负数加密的简单说明：设m £
r 6 Z :，_m 表示负数值.根据Paillier 加密方案直接加密
—m 得：[-m ] = (l + f c n )-m r "(modn 2)= ^g ^^(m 〇dn
2)
44Jowma/ 〇//?earc/i 密码学报 Vol.8, No.1，Feb. 2021调用解密算法得到:
Dec(c= [—mj’s k=A):L(c入(m od n2)),」、
Z^(m〇d,(m o d")
((i+C)^°d m〇d n i) ~l)(m〇d n2)
((1 +kn)x —l)(m o d n2)
l)(m o d n2)
、(1 +入fcmn)( mod n2)
A f c n(modn2)
-m(modn2)
(modn)
(modn) (1 +Afcmn)(modn2)
(modn)
若要恢复出一m，则需满足1 +A/cmn=l(modn2).
由于gcd(A，n) = 1，则要求n|Afcm.通常A: /尹Kg，所以当m=0(modn)才能正确解密消息，这与m为负数相矛盾.
本文采用以下方法实现P a i l l i e r中的负数表示及加密：设明文空间为丨0，n]，将其划分为两等长区间 [0，(n—1)/2]和[(n+l)/2，n]，将[0，(n—1)/2]内代表正数，[(n+l)/2，n]内代表负数.对于待加密明文 范围是卜(n-l)/2,(n-I)/2]，若待加密明文范围是[-(n— 1)/2,0]，则转化为加密-m+n=n—m.
则加密过程表示为：
[n — m] =(1 +kn)n~m rn(modn2)
解密过程表示为:
Dec(c=[n—m],s k=A)=[(1 + fcn)入(n_mV入n _l](m o d n2)
((1 +kn)x—l)(m o d n2)
(modn) =n—m
2.5隐私保护的欧几里德距离计算协议
给定两点（a：a，ya)和（16,2/6)，欧几里德距离即计算d=v/(xa —叽)2 + (j/a —讥)2，隐私保护的欧几 里德距离计算是指存在两方凡和巧，PQ拥有点（％，如)，n拥有点（办，讲)，二者在不泄露各自点信息 的前提下，共同计算出d.为简化协议，这里转化为计算欧几里德距离平方d2.
结合P a i l l i e r加密算法，明文空间为[0,n]，记m = -2:r a；C6 +4 — 2ya讲+队2，且范围在[-(n —l)/2，（n- 1)/2]内.本协议采用以下编码方式正确得到解密结果m：将明文空间分成两等长部分[0,(n—I)/2]和[(n+l)/2,n】，并规定正数空间[0，(n-l)/2]和负数空间[(n+l)/2，n j•若m在[-(n-l)/2,0)范 围内，则解密后将映射到负数空间[(n+l)/2,n]，则将[m]]的解密结果减上n即可；若m在[0，(n-l)/2] 范围内，则解密后将映射到正数空间[0,(n-l)/2]，则〖m〗的解密结果不变.
协议1隐私保护的欧几里德距离协议，具体协议如图2所示.
在初始阶段，朽通过安全参数k产生一对P a i l l i e i■公私钥对（Pka，s k a；)，将公钥pka发给保留私钥 s k a.
注解1：在本协议中，为保证在密文上计算，设两点（〜，办)、（办，讥）的范围在[0,LvG/4」）内.
隐私保护的欧几里德距离计算协议分析：该协议的目标是计算下式
d2=(x〇-x b)2+(ya-yb)2
根据定理1及扩展，分别加密-2;c a，-2糾，将密文〖n-2^1和〖r z-2y a]|发送给A.
n得到：
c=[n-.|[n-2ya]M .lyf]] =|[(n-2a:a)xb +4 +(n — 2ya)y6+(3)
