網上信息比對的隱私保護

◆游永興

（湖北警官學院 湖北 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，