网上信息比对的隐私保护

◆游永兴

（湖北警官学院 湖北 430034）

0 引言

随着技术的进步和网络的普及，人们的隐私保护变得越来越困难，人们试图得到信息时自己的隐私通常也泄露了出去，如何保护网购时信用卡号、消费习惯等信息不泄露是一个值得研究的问题，尤其是网络攻击的成本越来越低。网络面临着外部攻击和内部攻击的双重威胁，面对外部攻击的研究较多，内部攻击往往意味着合法用户的非法得利，特别是诈骗团伙往往要在内部人的协助下才能得到非法的利益，另外合法用户的权利滥用也是值得警惕的。

在对网络的使用中，网上信息比对是一个经常需要进行的活动，常见的比如身份证号码、银行卡号、QQ账号等都需要在网上利用信息比对才能完成特定的活动，特别是密码和验证码的比对风险相当高，如何在网上信息比对中完成信息的比对时比对双方和第三方都不能够知道除了结果外多余的信息，首先要确保如果比对不一致的话，双方不能知道对方的原始信息。

1 安全计算的由来

1976年W.Diffel和M.Hellman在文[1]中提出了公钥密码的新概念，为密码学的研究开创了一个新的时代；1982年姚期智在文[2]中利用公钥密码设计出了可以实现安全两方计算的协议，其中提到了有名的百万富翁问题：

Alice和Bob是两个百万富翁，Alice有i百万美元，Bob有j百万美元，1

步骤1.Bob选择一个任意的N比特的整数x，并且保密的计算Ea(x)=k；

步骤2.Bob给Alice发送数值k-j+1；

步骤3.Alice保密的计算yu=Da(k-j+u)，其中u=1,2,…10；

步骤4.Alice生成一个N/2比特长的素数p，计算Zu=yu(modp)对于所有的u（如果有两个Zu模p之差小于等于2就重新生成新的p直到满足条件）；

步骤5.Alice将这个素数p和下面的10个数发给Bob：Z1,Z2,…Zi,Zi+1,…，Z10+1，这些数都是模p的结果；

步骤6.Bob找其中的第j个数，如果它等于x模p的话i大于等于j，不然的i小于j；

步骤7.Bob告诉Alice他的结论。

通过协议的过程，Alice和Bob知道了两个人谁更富有，但是不知道对方到底有多少美元，这样就在比较的同时保护了双方的隐私。

可以看出，安全双方计算就是甲乙双方有两个输入信息x和y，通过协议双方计算f(x,y)的值（百万富翁问题就是f(x,y)等于x和 y之间的大小关系），并且甲乙双方都没有办法知道另外一方的输入信息x和y，这样就可以很好的保护双方输入信息的隐私。

1981年Radin提出了不经意传输（Oblivious Transfer，下文中简称为OT协议）：Alice有个信息，Bob通过一定的概率获得这个信息，但是Alice不知道Bob是否得到这个信息。将OT协议与门电路结合在一起可以得到加门和乘门的安全协同计算：

加门的安全协同计算步骤如下：

步骤 1：Alice 对她的输入比特信息 a，找 SA和 SB，使得SA⊕SB=a，将SB发送给Bob。Bob做同样的操作，对它的输入信息比特b，找tA和tB，使得TA⊕tB=b，将tA发送给 Alice；

步骤 2：Alice 计算 SA⊕TA=uA,Bob 计算 SB⊕tB=uB；

步骤 3：Alice 和 Bob 将第二步中计算出的结果发送给第三方。

输出：第三方计算出 a⊕b=uA⊕UB，也可以将结果告诉 Alice和Bob。

乘门的安全协同计算步骤如下：

步骤 1：Alice 对她的输入比特信息 a，找 SA和 SB，使得SA⊕SB=a，将SB发送给Bob。Bob 做同样的操作，对它的输入信息比特b，找tA和tB，使得tA⊕tB=b，将tA发送给Alice；

步骤2：Alice和Bob利用OT协议，Alice作为发送者拥有信息ρ0和ρ0⊕SA，Bob有一个选择SB，协议输入为Bob得到ρ0⊕SBtA；

步骤3：Alice和Bob利用OT协议，Alice作为发送者拥有信息ρ1和ρ1⊕SA，Bob有一个选择SB，协议输入为Bob得到ρ1⊕SBtA；

步骤 4：Alice计算 UA=SAtA⊕ρ0⊕ρ1，Bob 计算 UB=SBtB⊕SBtA⊕ρ0⊕ρ1，将UA和UB发送给第三方。

输出：第三方计算出ab=UA⊕UB，也可以将结果告诉Alice和Bob。

非门同样可以进行安全协同计算，但由于非门从输出可以看出输入的特点，没有办法保护原始信息的隐私，而且非门通常在门电路中使用很少，对于隐私保护没有明显的影响。

2 可保护隐私的网上信息比对

对于网上信息比对而言，有三种情形可以利用上面的方法解决隐私保护：

第一种是两个信息只需比对前面一位或者少数几个位置比特值的大小，利用百万富翁协议就行了，比如比对五个比特位的大小只需将前面的百万富翁协议中计算10个数字改为计算32个数字，然后执行协议就够了。

第二种是两个信息需要知道是否完全一致，比如Alice有个信息m1，Bob有个信息m2，双方想知道对方的信息是否和自己一致，可以利用Hash函数的单向性进行设计。

设Alice有公开的公钥加密函数Ea(x)和对应的私钥解密函数Da(x)，Bob有公开的公钥加密函数Eb(x)和对应的私钥解密函数Db(x)，双方通过公开渠道协商了Hash函数H(x)。Alice有信息m1，Bob有信息m2，协议如下：

1.Alice计算Eb(H(m1))；

2.Alice将k1发送给Bob；

3. Bob计算D(k1)与自己的H(m2)比较，将相等或者不相等的结论发送给Alice。

协议完成之后，如果m1与m2相等则协议完成了它的任务；如果 m1与m2不相等，由于Hash的单向性，对方也无法知道自己的信息，从而在完成比较的同时没有泄露更多的信息。

第三种双方知道信息想知道是否只是相差很少几个比特，可以利用门电路的安全协同计算进行比较。如果Alice拥有信息m1，Bob拥有信息 m2，Alice和 Bob利用门电路的安全协同计算H(m1-m2)的值。双方将只有几个比特位为非0的Hash值列表后和H(m1-m2)的值进行比较，就可以知道双方信息是否相差几个比特甚至是那几个比特，但是如果H(m1-m2)的值不在预先计算的表中，双方也无法知道对方的信息，从而保护了信息的隐私。

3 结束语

由于安全协同计算的特点，协议执行后可以很好的保护信息比对参与方的隐私，随着社会的发展，信息比对的形式和要求越来越新，比如信息比对中需要知道两个信息相似程度时的隐私保护、网上信息比对对参与方的主动参与程度等等都是未来值得进一步研究的方向。

[1]W.Diffle and M.Hellman.New Directions in Cryptograghy[J],.IEEE Trans Inform Theory，1976.

[2]Yao A C,Protocols for Secure Computations[C],In Proceedings of 23th Annual IEEE Symposium on Foundations of Computer Science，1982.

[3]M.O.Radin.How to Exchange Secrets by Oblivious Transfer[R].Tech Memo TR-81Aiken Computation Laboratory，