曼哈顿距离的保密计算*

方乐笛,李顺东,窦家维

1.陕西师范大学 计算机科学学院,西安710119

2.陕西师范大学 数学与信息科学学院,西安710119

1 引言

随着互联网、物联网和大数据技术的迅速发展与日益普及,隐私信息与机密信息极易泄露,这使得隐私保护变得尤为重要.安全多方计算(secure multiparty computation,SMC)作为隐私保护的核心技术,成为了国际密码学界的研究热点[1].安全多方计算最初于1982年由Yao[2]以百万富翁问题提出,它由两个参与者组成,之后Ben-or和Goldwasser[3]将其扩展到了多个参与者,学术界统称为安全多方计算.安全多方计算的奇妙之处就在于可以使参与者在不泄露自己隐私数据的情况下,保密地使参与者利用自己的隐私数据联合进行某种运算,从而达到合作共赢的目的,也最大限度的平衡了参与者隐私性与合作性的需求.

安全多方计算的研究在计算科学领域、密码学与信息安全中有着举足轻重的作用,是信息社会隐私保护的核心技术,其主要可分为以下几类:(1)保密的科学计算问题[4–13];(2)保密的计算几何问题[14–18];(3)保密的统计分析问题;(4)保密的数据挖掘问题[19];(5)保密的数据库查询问题;(6)其他安全多方计算问题.虽然人们已经研究了很多安全多方计算问题,并提出了这些问题的解决方案,但这些方案的效率都亟待提高,此外还有很多新的问题需要研究,曼哈顿距离问题就是需要研究的新问题。

曼哈顿距离(Manhattan distance,MD)又称出租车距离,是指两个垂直方向上的距离之和.P(x1,y1)和Q(x2,y2)之间的曼哈顿距离MD=|x1−x2| +|y1−y2|.保密计算两点间曼哈顿距离的问题是安全多方计算中一个很有趣的问题,它在保密科学计算、保密信息过滤,计算机图形学的保密计算、保密生物信息学计算等方面有重要的应用.

要保密计算曼哈顿距离MD,首先要保密计算|x1−x2|,即保密计算两个数之差的绝对值.也可看做直线上的曼哈顿距离.然后再保密计算|x1−x2|+|y1−y2|.但根据安全多方计算的安全性要求,这个计算过程不能泄露|x1−x2|和|y1−y2| 的值,即不能分别保密计算|x1−x2|和|y1−y2| 的值后再相加,因为这将泄露|x1−x2|和|y1−y2| 的值.因此曼哈顿距离的保密计算不是绝对值保密计算的简单推广.

由于|x1−x2| 的安全多方计算和|x1−x2|+|y1−y2| 的安全多方计算都没有见到报道,因此曼哈顿距离的安全多方计算是一个全新的问题,而且曼哈顿距离的保密计算不是绝对值保密计算的平凡推广,实际上是两个独立的问题.保密计算两点间曼哈顿距离的关键是双方如何在经过运算后直接得到两点间的曼哈顿距离,而不是分别计算横纵坐标差的绝对值之和.本文便巧妙地解决了这一关键问题.我们首先设计了一种编码方法,用这种编码和Goldwasser-Micali 公钥加密算法将原问题化为了保密计算两个比特串的海明距离.我们的编码方法也可以直接解决绝对值的保密计算问题,两个比特串的海明距离问题,以及其他安全多方计算问题.

我们证明了这些协议在半诚实模型下是安全的,但是一个恶意的参与者可能会在关键的环节进行欺骗.为了防止这种欺骗的发生,我们又设计了另一种编码方法,这种编码方法与Paillier 加密算法相结合可以保密计算两点间曼哈顿距离问题,而且可以防止恶意参与者在关键环节进行欺骗.当然,这种编码方法也可直接解决绝对值的保密计算问题.最后,我们对设计的协议进行了理论分析与实验仿真.通过理论分析和仿真表明,我们所设计的协议是高效的.

1.1 本文贡献

(1)本文首次研究了关于保密计算两点间曼哈顿距离的问题.这是一个全新的安全多方计算问题,它在保密科学计算、保密信息过滤、生物信息学保密计算等方面具有重要的理论意义与应用价值.为了高效地解决此问题,设计了两种新的编码方法,将原本复杂而抽象的问题化为了简单具体的问题.通过不同的编码方法,参与者将自己的数据编码成了一个向量,并且经过运算后可直接得到两点间的曼哈顿距离,避免了分别计算横纵坐标差的绝对值之和导致的信息泄露.

(2)结合Goldwasser-Micali 加密算法,将保密计算两点间曼哈顿距离的问题化为保密计算两向量海明距离的问题,设计出了协议1.我们的编码方法也可以直接解决绝对值的保密计算问题,两个比特串的海明距离问题,以及其他安全多方计算问题.

(3)我们又设计了另一种编码方法,这种编码方法与Paillier 加密算法相结合可以保密计算两点间曼哈顿距离问题,设计出了协议2,而且结合数字承诺的思想可以防止恶意参与者在关键环节进行欺骗.当然,这种编码方法也可直接解决绝对值的保密计算问题.

(4)将保密计算两点间曼哈顿距离的问题应用到了实际生活中,给出了保密计算两点间曼哈顿距离的问题的应用与扩展.由于使用编码方法,使得协议具有很高的效率,并通过理论分析与实验数据证明了协议的高效性.

1.2 本文结构

本文第2 节介绍预备知识; 第3–4 节分别设计了一个关于保密计算两点间曼哈顿距离的协议,并用模拟范例证明了协议是安全的; 第5 节给出了曼哈顿距离的应用及扩展; 第6 节理论分析了协议的效率,并进行了实验仿真.第7 节为本文总结与展望.

2 预备知识

2.1 安全性定义

半诚实模型:所谓半诚实参与者是指参与者在协议执行过程中将不折不扣地执行协议,但他们会保留计算的中间结果,在协议结束后试图推导出其他参与者的输入.如果所有参与者都是半诚实参与者,这样的模型称为半诚实模型[20].

本文所设计的协议是在半诚实模型下安全的计算协议.

一些记号:假设参与保密计算的双方分别为Alice和Bob,且Alice 拥有数据x,Bob 拥有数据y,他们希望在保证x,y隐私性的前提下,合作计算概率多项式时间函数f(x,y)=(f1(x,y),f2(x,y)).记π为计算f的协议,表示Alice 在执行协议的过程中所得到的信息序列.其中r1表示Alice 所选随机数;表示Alice 收到的第i个信息.执行协议π后,Alice 得到的输出结果为f1(x,y).Bob 得到的信息序列可以类似定义[20].

定义1假设f(x,y)=(f1(x,y),f2(x,y))是一个两方计算函数,x(y)表示第一(二)方输入的变量,f1(x,y)(f2(x,y))表示两方各自获得的函数值,π是计算f的一个两方计算协议.如果存在概率多项式时间算法S1,S2使得:

则称协议π保密地计算了函数f.其中表示计算不可区分.

2.2 Goldwasser-Micali 公钥加密系统

Goldwasser-Micali 加密方案具体描述如下[21]:

密钥生成:随机选取大素数p,q,计算N=pq,并选取一个正整数则公钥为(N,y),私钥为(p,q).将加密算法记为E,解密算法记为D.

加密:对明文m∈{0,1},选择随机数r:1≤r≤N−1,计算得密文c=E(m)

解密:对密文c,按下面方式计算得明文m=D(c)

异或同态性:由于下面性质成立

因此,Goldwasser-Micali 加密方案具有异或同态性.

2.3 Paillier 同态加密算法

Paillier 加密方案具体描述如下[22].

密钥生成选取两个大素数p,q,计算N=pq,λ=lcm(p−1,q−1).定义函数随机选择一个生成元使得gcd(L(gλmodN2),N)=1.则加密方案的公钥为(g,N),私钥为λ.

加密过程对于明文m

解密过程对密文c,计算得明文m=D(c)

加法同态性:由于下面性质成立

因此,Paillier 加密算法具有加法同态性.

2.4 单向散列函数

单向散列函数定义[23]:对于函数f,如果存在多项式时间算法A使得A(x)=f(x)但不存在多项式时间算法B使得B(y)=x′∧f(x′)=y,那么我们称f是一个单向函数.

如果一个单向函数f对于任意的|x1|=|x2|,都有|f(x1)|=|f(x2)|,我们就称它为单向散列函数.

单向散列函数具有下面的性质[20]:(1)给定消息M,很容易计算h=hash(M);(2)给定h=hash(M),根据h计算其逆M=hash−1(h)很难;(3)给定M,要找到另一个消息M′,使得hash(M)=hash(M′)很难;(4)找出两个随机的消息M和M′,使得hash(M)=hash(M′)很难;(5)如果对x作微小改变,即使只改变一个比特,hash(x)的值也会发生惊人改变.

2.5 数字承诺

数字承诺[23],简单地说,可以理解为一个有两方参与的两阶段协议,这两方分别为承诺者与接收者.第一个阶段称为承诺阶段(commitment phase),第二个阶段称为承诺揭示阶段(reveal phase 或open phase).通过这个协议承诺者能够实现自己与一个数字的绑定.这种绑定要满足保密性(secrecy)与确定性(binding).所谓保密性是指承诺者作出承诺后,接收者无法获得有关承诺者所承诺数字的任何知识; 所谓确定性是指,接收者只接受承诺者所发送的合法数字,若承诺者进行欺骗,接收者可以发现并拒绝接收.

当然,协议也应该是可靠的(viable),即如果双方都遵守协议,那么在协议的第二阶段接收者应该能够获得一个承诺者所承诺的唯一的数字.要求一个承诺方案必须保证承诺者在承诺阶段不会向接收者泄露有关承诺值的任何信息,而且也使承诺者在承诺之后无法再改变自己的承诺值.而且还要保证这样的协议应该是可行的,即协议应该能够在概率多项式时间内完成.而在揭示阶段,承诺者可能需要向接收者提供很复杂的信息,也可能仅仅提供他自己的承诺的数值与在承诺阶段所选择的随机数值供接收者验证.只有利用相应的承诺值与相应的随机数能够导出在承诺阶段接收者所收到的全部信息时.接收者才接受相应的承诺值.

3 半诚实模型下曼哈顿距离协议

本节首先设计一种新的编码方法,以此为基础,结合应用Goldwasser-Micali 加密方案,设计构造两点间曼哈顿距离的保密计算协议.

问题描述:假设Alice和Bob 在平面上分别拥有私密点P(x1,y1)和Q(x2,y2),他们想保密计算两点间的曼哈顿距离,即保密计算函数f(P,Q)=|x1−x2| +|y1−y2|.在下文中,我们也将点P(x1,y1),Q(x2,y2)看作两个二维向量.

编码方法1:为了保密计算曼哈顿距离,首先设计编码方法如下:

给定全集U={u1,··· ,un},其中ui,i∈[1,n]={1,2,··· ,n} 为n个连续的整数,满足u1

以x1为例.根据x1和全集U构造一个n维数组A1=(a11,··· ,a1n),构造方法如下:假设x1=uk,则令a11=,··· ,=a1k=1,a1(k+1)=,··· ,=a1n=0.即数组的前k维元素为1,后n−k维元素0.对于y1以完全相同的方式构造其对应的数组,记为A2=(a21,··· ,a2n),那么定义P(x1,y1)在全集U之下对应的编码数组为

例1假设全集为U={−3,−2,··· ,4,5},对于点P(5,3),根据编码方法1,将横坐标5 编码为A1=(1,1,1,1,1,1,1,1,1).将纵坐标3 编码为A2=(1,1,1,1,1,1,1,0,0),进而可得

类似地,对于点Q(−3,−2),根据编码方法1 可得

计算原理1:在下面计算中,假设全集为U={u1,··· ,un},Alice和Bob 分别拥有点P(x1,y1)和Q(x2,y2),满足x1,y1,x2,y2∈U,在全集U之下,点P(或Q)按照编码方式1 对应的向量记为

关于两点P和Q之间的曼哈顿距离,有下面的结论.

命题1点P和Q间的曼哈顿距离可由下式计算:

证明:(i)我们首先证明

首先设x1≥x2,并记x1在全集U中的位置为k1,x2在全集U中的位置为s1,这时显然有

按照编码方式1 编码后,x1对应的向量为

x2编码为

对A1和B1的对应分量进行异或,得到

显然,将C1的各分量相加,得到

当x2>x1时,完全类似得到

3.1 具体协议

以上面计算原理为基础,结合Goldwasser-Micali 加密算法,我们设计构造两点间曼哈顿距离的保密计算协议.

协议1半诚实模型下安全计算两点间的曼哈顿距离

输入Alice 输入私密点P(x1,y1),Bob 输入私密点Q(x2,y2).

输出f1(P,Q)=f2(P,Q)=|x1−x2|+|y1−y2|.

准备工作Alice 根据编码方法1 构造P对应的向量A=(a11,··· ,a1n,a21,··· ,a2n); Bob 根据编码方法1 得到Q对应的向量B=(b11,··· ,b1n,b21,··· ,b2n).Alice 运行Goldwasser-Micali 加密方案,生成公钥/私钥对pk/sk,将公钥pk 发送给Bob.

(1)Alice 用公钥加密向量A(分别对每个分量加密),得到E(A)

并将E(A)发送给Bob.

(2)Bob 加密向量B的每个分量,并计算

再将R的n个分量进行随机置换,得到新的向量,记为,并将发送给Alice.

计算y=d11+···+d2n,并将y发给Bob.

(4)Alice和Bob 输出y.

3.2 方案分析

正确性分析由协议的第(2)步,结合加密算法的异或同态性可知

根据前面的计算原理,即证得y=|x1−x2|+|y1−y2|.即协议1是正确性的.

安全性分析关于协议的安全性,我们有下面的结论.

定理1协议1能够保密地计算两点间的曼哈顿距离.

证明:通过构造使式(1)和(2)成立的模拟器S1和S2证明本定理.

S1的模拟过程如下.

(1)接受输入(P,f1(P,Q))后,S1随机选择使得f1(P,Q′)=f1(P,Q).并按照编码方法1 对(P,Q′)进行编码,得到相应的向量

(2)S1加密向量B′得到E(B′),并计算

再将R′的分量进行随机置换,得到.

(3)S1解密′,得到

(4)S1计算

类似地,S2的模拟过程如下.

(1)接受输入(Q,f2(P,Q))后,S2随机选择使得f2(P′,Q)=f2(P′,Q).并按照编码方法1 对(P′,Q)进行编码,得到相应的向量

(2)S2加密向量A′得到E(A′),并计算

再将R′的分量进行随机置换,得到

(3)S2解密得到

(4)S2计算

由于E(A)是由Alice 加密得到的,Bob 没有私钥,根据加密算法的语义安全性,对于Bob 来说,E(A′),进一步由于f2(P,Q)=f1(P′,Q),故有

因此,协议1能够保密计算两点间的曼哈顿距离.

4 增强的曼哈顿距离协议

众所周知,双方在半诚实模型下联合计算的结果都会由拥有私钥的一方(假设为Alice)进行解密,之后再将解密结果发给另一方(假设为Bob).即Bob 所得最后结果完全是由Alice 单方面发来的.而之前双方进行联合计算的目的也是为了得到这个最后结果.

我们设想,如果在协议1中,当Alice 得到了两点间的曼哈顿距离y以后,她可能因为自己的私利发送给Bob 一个不同于y的值,Bob 却无法判断得到的结果是否正确,这对Bob 显然是不公平的.为了解决这个问题,我们将设计一个新的编码方法,使一方参与者改用新的编码方法编码,如此可将计算两点曼哈顿距离的问题转化为两个向量内积问题,以此为基础,并结合Paillier 加密方案和数字承诺思想设计构造防欺骗场景下的安全计算协议,保证两个参与者获得相同的计算结果(若有一方试图欺骗,另一方即可发现).所谓的数字承诺,简单地说,可以理解为一个有两方参与的两阶段协议,这两方分别为承诺者与接收者.通过这个协议承诺者能够实现自己与一个数字的绑定.这种绑定要满足保密性与确定性.所谓保密性是指承诺者作出承诺后,接收者无法获得有关承诺者所承诺数字的任何知识; 所谓确定性是指,接收者只接受承诺者所发送的合法数字,若承诺者有所欺骗,接收者可以发现并拒绝接收.

编码方法2:与编码方法1 类似,我们在全集U={u1,··· ,un} 之下构造编码方法,其中ui∈[1,n]具有与编码方法1 中完全相同的性质.对于任一点P(x1,y1)∈U2,在全集U之下计新的编码方法如下.

以x1为例.根据x1和全集U构造n维数组V1=(v11,··· ,v1n),构造方法如下:

假设x1=uk,则令v11=,··· ,=v1k=0,v1(k+1)=,··· ,=v1n=1.

即该数组的前k维元素为0,后n−k维元素为1.对于y1以完全相同的方式构造其对应的数组,记为V2=(u21,··· ,u2n),进一步构造向量

并称V(P)为在全集U之下应用编码方法2 获得的P(x1,y1)的对应编码向量.

例2假设全集为U={−3,−2,··· ,4,5},对于点P(−3,−2),应用编码方式2,将x1=−3 编码为V1=(0,1,1,1,1,1,1,1,1),将y1=−2 编码为V2=(0,0,1,1,1,1,1,1,1),并得到P(−3,−2)应用编码方法2 对应的向量V(P)=(0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1).

计算原理 2:在下面计算中,总假设全集为U={u1,··· ,un},Alice和 Bob 分别拥有点P(x1,y1),Q(x2,y2),满足x1,y1,x2,y2∈U,在全集U之下,对点P(或Q)先按照编码方式1(或编码方式2)进行编码,再按照编码方式2(或编码方式1)进行编码,对应的向量记为

关于两点P和Q间的曼哈顿距离,下面结论成立.

命题2点P和Q的曼哈顿距离等于向量A和V的内积.即有下式成立

证明:(i)我们首先证明

首先假设x1≥x2,x1先按照编码方式1 编码,x2按照编码方式2 编码,记x1在全集U中的位置为在全集U中的位置为这时显然有

按照编码方式1 编码后,x1对应的向量为

按照编码方式2 编码后,x2编码为

x1再按照编码方式2 编码,x2按照编码方式1 编码,并记x1在全集U中的位置为在全集U中的位置为这时显然有

按照编码方式2 编码后,x1对应的向量为

按照编码方式2 编码后,x2编码为

当x2>x1时,完全类似得到

4.1 具体协议

根据上面所述的计算原理,并结合应用Paillier 加密方案和数字承诺思想可设计构造防欺骗场景下计算两点间曼哈顿距离的安全计算协议2.具体协议如下.

协议2防欺骗场景下安全计算两点间的曼哈顿距离

输入Alice 输入私密点P(x1,y1),Bob 输入私密点Q(x2,y2).

输出f1(P,Q)=f2(P,Q)=|x1−x2|+|y1−y2|.

准备工作Alice和Bob 根据上例分别按照编码方法1 以及编码方法2 对点P和Q进行编码,得到4n维向量A(P)=(a1,··· ,a4n)以及V(Q)=(v1,··· ,v4n),双方再商定一个哈希函数.在下面,将Paillier 加密及解密算法分别记为加密及解密算法分别记为以及

(1)Alice 加密向量A(P)(逐分量加密),得到

(2)Bob 选择随机数s,计算v=hash(s),利用Paillier 加密算法加密得到(s),进一步计算

Bob 将v以及T发送给Alice.

(3)Alice 解密T得到并将发送给Bob.

(4)Bob 计算d=−s,并将d发给Alice.

4.2 方案分析

正确性分析由Paillier 加密算法的加法同态性,协议第(3)步Alice 解密可得到再由Bob 在第(4)步中计算可知,由命题2,正确性得证.

安全性分析完全类似于协议1的证明方法可知协议2 在半诚实模型下是安全的.在协议2中Alice 不再是最早得到计算结果的一方,从而避免了Alice 篡改结果的欺骗行为.计算结果是由Bob 在协议第(4)步率先得到,但为了防止Bob 的欺骗行为,在协议的第(2)步已经将随机数s的Hash 值v发给了Alice,从而对y进行了承诺.根据不可能找到两个不同的消息生成相同的单向散列函数值以及单向散列函数一个比特变化就会导致单向散列函数值约一半比特的比特发生变化的这两个特殊性质,迫使Bob 最后只能公布真实的结果.若Bob 想修改结果,则Alice 在协议第(5)步验证hash(−d)=v时就会发现Bob的欺骗行为.即Alice 将该值与原先收到的值和随机数进行匹配,如果匹配,则承诺有效; 反之,承诺无效,Alice 可以拒绝接受Bob 所发来的结果.本承诺的理论基础就是根据单向散列函数这两个特殊性质决定的.故通过由Bob 选择随机数s及对s进行Hash 运算这些技巧,既保证了协议2 的正确性以及安全性(在半诚实模型下),进一步,当Bob 把计算结果发送给Alice时,Alice 可以检验收到的结果是否为正确结果,从而保证了两个参与者获得相同的计算结果.

5 应用及推广

5.1 应用

(1)中国象棋

众所周知,在中国象棋中,卒在两点间所行走的距离可以看做是计算两点间的曼哈顿距离; 象在两点间所行走的距离可以看做两点间以斜对角(即斜45 度)为坐标轴的曼哈顿距离.科学研究与工程实践中的许多约束优化问题可以抽象为中国象棋问题.在现实生活中,大多数实际问题是包含约束条件的.这使得约束优化问题与实际生活息息相关.但随着网络的迅速发展,人们越来越看重个人隐私,这使得隐私保护变得尤为重要,但如何在不降低安全性的前提下,保密地解决约束优化的问题呢? 这就需要保密计算两点间的曼哈顿距离.

(2)生物信息学

在生物信息学中,保密计算两者间的曼哈顿距离可以评估离散频率分布的差别.即RNA 拼接随机引物的位置分布可以用曼哈顿距离表示.每一个位置分布可以用一个向量进行表示,该向量的每一项代表了随机引物在某一个核苷酸开始的概率.两向量间的曼哈顿距离越大,则表明它们之间的分布差距越大; 两向量间的曼哈顿距离越小,则表明它们之间就有相似的分布,从而对患病概率,新病种了解有着举足轻重的作用.在现实生活中,患者并不想公开自己的患病信息,医疗机构彼此之间也不想透漏自己的商业机密,这使得如何在不泄露私有信息的情况下保密地了解某种新的病种与已知病种间相似度的问题变得尤为重要.保密计算计算两点间的曼哈顿距离便可以解决此问题.

5.2 推广

(1)有理数域下保密计算两点间的曼哈顿距离.

首先双方商定精度,假设将有理数保留至小数点后一位.之后沿用思想1 或思想2,将全集按照0.1进行划分.利用同样的方法便可保密计算有理数域下两点间的曼哈顿距离.

(2)整数集下保密计算多点的曼哈顿距离.

问题描述Alice,Bob 分别在平面上拥有多个私密点(u1,u2),··· ,(ul−1,ul)和(v1,v2),··· ,(vl−1,vl),且这些私密点的全集已知,他们想保密求这些点间的曼哈顿距离,即保密计算(|u1−v1|+|u2−v2|)+···+(|ul−1−vl−1|+|ul−vl|)的值.

解决思路在多点对的情况下,我们同样可以沿用协议1或者协议2的思想.以协议1思想为例,Alice,Bob 可以分别将自己l个私密点编码,将其分别化为ln维向量L1,L2.之后再保密计算向量L1,L2间的海明距离即可.

(3)保密计算两点间的切比雪夫距离.

问题描述Alice,Bob 分别在平面上拥有一个私有点(t1,t2)和(w1,w2),他们想保密求这两点间的切比雪夫距离,即保密计算max{|t1−w1|,|t2−w2|},为了进一步满足安全性的需求,这里我们稍作改变,即输出结果只输出是横坐标差的绝对值大还是纵坐标差的绝对值大,但不泄露具体数值.

解决思路将保密计算两点间切比雪夫距离的问题化为保密计算两向量内积的问题.

双方首先进行编码,双方规则不同.Alice 先将自己的数据按照编码方式1 进行编码,即该数及其之前的数均编为1,其余编为0.(或Bob 先将该数及其之前的数均编为0,其余编为1 或−1(对于横坐标编为1,纵坐标标为−1).)

例3假设Alice 拥有点(5,3); Bob 拥有点(−3,−2).全集为{−3,−2,··· ,4,5}.

Alice 将横坐标5 进行编码,得到向量T1=(1,1,1,1,1,1,1,1,1),将纵坐标3 进行编码,得到向量T2=(1,1,1,1,1,1,1,0,0).进而Alice 可以得到向量T′=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0).

Bob 将横坐标−3 进行编码,得到向量W1=(0,1,1,1,1,1,1,1,1),再将纵坐标−2 进行编码,得到向量W2=(0,0,−1,−1,−1,−1,−1,−1,−1).进而 Bob 可以得到向量W′=(0,1,1,1,1,1,1,1,1,0,0,−1,−1,−1,−1,−1,−1,−1).

Alice 再将自己的数据按照编码2 进行编码,即该数及其之前的数均编为0,其余编为1.(或Bob 先将该数及其之前的数均编为1,其余编为0.)

例4Alice 对横坐标5 进行编码,得到=(0,0,0,0,0,0,0,0,0),纵坐标3 进行编码,得到=(0,0,0,0,0,0,0,1,1).从而可得向量T′′=(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1).Bob 对横坐标−3进行编码,得到=(1,0,0,0,0,0,0,0,0),对纵坐标−2 进行编码,得到=(1,1,0,0,0,0,0,0,0).从而可得向量=(1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0).

至此,双方分别得到向量

与

最后,双方利用Paillier 同态加密算法保密求得T,W两向量的内积,即保密地将

与

6 协议的效率分析

6.1 计算复杂性与通信复杂性分析

计算复杂性由于目前没有任何关于保密计算两点间曼哈顿距离的协议,因此只对本文提出的协议进行效率分析.协议1 中,Alice 加密了2n次(n为全集的势),解密2n次; Bob 需要进行2n次加密运算和2n次模乘运算.加密一次需要进行2 次模乘运算,解密一次需要lgp次模乘运算,因此协议1 需进行10n+2nlgp次模乘运算.协议2中,Alice 需加密4n次,解密1 次; Bob 最多需进行4n次模乘运算,由于哈希运算速度极快,我们忽略哈希运算所进行的时间,故协议2 最多需进行2(6n+1)次模乘运算.

通信复杂性我们使用通信轮数来进行分析.协议1和协议2均需要2 轮通信.具体分析见表1.

表1 协议性能比较Table 1 Protocol performance comparison

6.2 实验数据分析

实验测试环境:我们采用java 编程语言对协议进行编程实现.实验测试环境如下:Windows 10 家庭中文版,处理器为Intel(R)Core(TM)i5-6600 3.30 GHz 3.31 GHz,内存为8.00 GB.

实验方法:随机选取两点X,Y,并设定全集的势为n.对于n=5,··· ,23(间隔为2)的每个设定值进行进行1000 次实验并取其平均时间.实验所选取的Goldwasser-Micali 加密算法的加密密钥为512 比特,Paillier 加密算法的加密密钥为512 比特,选取随机数长度为64 比特.图1 描述了保密计算两点间曼哈顿距离的时间随着n值增长的变化规律.

图1 协议执行时间随着n 值增长的变化规律Figure 1 Execution time of protocol varies with growth of n

实验结果表明,保密计算两点间曼哈顿距离的时间随着n的增加大致呈线性增长.协议1与协议2均可以高效且安全地计算两点间曼哈顿距离.

7 结论

保密计算两点间的曼哈顿距离是密码学中一个新的问题,在信息过滤,生物信息学方面有着重要的理论价值.本文用新的方法来解决这个新的问题,设计了两种不同的编码方法,利用该编码和同态加密算法将原问题分别化为保密计算两向量的海明距离与保密计算两向量的内积,经过运算后可直接得到两点间的曼哈顿距离,避免了分别计算横纵坐标差的绝对值之和导致的信息泄露,并用模拟器证明了协议是安全的.与此同时,我们将原问题扩展至三个方面,形成了三个新问题(有理数域下保密求两点间的曼哈顿距离; 整数集下保密计算多点的曼哈顿距离; 保密计算两点间的切比雪夫距离).最后,通过理论分析和实验显示,我们的方案可以高效安全地计算两点之间的曼哈顿距离.本文所设计的协议均是在半诚实模型下进行的,在后面的工作中,我们将探讨恶意模型下保密计算两点间曼哈顿距离的问题.