隱私保護DNA序列漢明距離計算問題

馬敏耀 徐藝 劉卓

摘 要：DNA序列承載著人體重要的生物學信息，如何在保護隱私的情況下正確地對不同的DNA序列進行比對，成為亟待研究的科學問題。漢明距離在一定程度上刻畫了兩個DNA序列的相似程度，在保護隱私的情況下，研究DNA序列的漢明距離計算問題。首先定義了DNA序列的0-1編碼規則，該規則將長度為n的DNA序列編碼成長度為4n的0-1串，證明了兩個DNA序列的漢明距離等于它們的0-1編碼串的漢明距離的一半。以此結論為基礎，以GM（Goldwasser-Micali）加密算法為主要密碼學工具，構造了計算DNA序列漢明距離的一個安全兩方計算協議。在半誠實攻擊者模型下，證明了協議的正確性，給出了基于模擬器的安全性證明，并對協議的效率進行了分析。

關鍵詞：漢明距離;DNA序列;隱私保護;安全多方計算;同態加密

中圖分類號：TP309

文獻標志碼：A

Privacy preserving Hamming distance computing problem of DNA sequences

MA Minyao1，2*， XU Yi1，2， LIU Zhuo1，2

1.School of Mathematics and Big Data， Guizhou Education University， Guiyang Guizhou 550018， China;

2.Key Laboratory of Cyberspace Security， Guizhou Education University， Guiyang Guizhou 550018， China

Abstract：

DNA sequences carry important biological information of human bodies， how to compare multiple DNA sequences correctly with privacy preserving is an important problem. To a certain extent， Hamming distance characterizes the similarity between two DNA sequences. Therefore， the privacy preserving Hamming distance computing problem of DNA sequences was researched. First of all， the “0-1 Coding” of the DNA sequence was defined， which codes the DNA sequence with length n to a 0-1 string with length 4n， proving that the Hamming distance of two DNA sequences is a half of the Hamming distance of their “0-1 Coding” strings. Then， with the help of this conclusion， with the Goldwasser-Micali （GM） encryption algorithm taken as main encryption tool， a secure two-party computation protocol for computing the Hamming distance of two DNA sequences was proposed. It was shown that the protocol is both secure and correct under semi-honest attacker model. The proof of security based on a simulator was given. After then， the efficiency of the protocol was analyzed.

Key words：

Hamming distance; DNA sequence; privacy preserving; secure multi-party computation; homomorphic encryption

0 引言

安全多方計算研究如何使互不信任的多個參與方在不借助任何第三方的情況下實現保護隱私的協同計算。安全多方計算技術常用來解決各種隱私保護科學計算問題。只含兩個參與方的安全多方計算稱為安全兩方計算，即參與方A1和A2分別擁有自己的秘密輸入x1和x2，在不借助任何第三方的情況下聯合計算某個二元函數（y1， y2）=f （x1， x2），協議結束后，參與方Ai得到本方的正確輸出yi（正確性）且任何一方的輸入都未泄露給其他人（安全性）。1982年，姚期智在文獻[1]中Yao等[1]最先提出安全多方計算的思想。隨后，文獻[2-4]研究安全多方計算的可行性問題，即具體安全模型下安全多方計算協議的存在性問題，以及構造能夠計算任意可計算函數的通用安全多方計算協議。由于通用協議的執行效率相對較低，因此大量的文獻研究具體安全多方計算問題的解決方案，例如：百萬富翁問題等多方數據比較問題[5]、隱私保護線性代數計算問題[6]、安全多方集合計算問題[7-12]、安全多方量子計算問題[5， 7] 、隱私保護機器學習[13]等。

本文將研究隱私保護DNA序列漢明距離計算問題。醫學上常常需要對多個DNA序列進行比對，以判斷不同DNA樣本的某些生物特征的相似度，其中DNA序列是由A（腺嘌呤）、C（胞嘧啶）、G（鳥嘌呤）和T（胸腺嘧啶）按某種順序排列而成的有限長度字符串。在傳統的DNA序列比對過程中，幾乎不考慮DNA序列的隱私性。然而，DNA序列承載著重要的生物學信息，屬于個人的隱私。因此，如何在保護隱私的情況下正確地對多個DNA序列進行比對，是一個亟待研究的課題。

漢明距離在一定程度上刻畫了兩個DNA序列的相似程度，是DNA序列相似度比較中的一個重要指標，其中漢明距離是兩個等長的字符串中位置相同但字符不同的位置個數。本文在保護隱私的情況下，研究兩個等長的DNA序列的漢明距離計算問題：即兩個參與方A和B，分別擁有長度相同的DNA序列X和Y，如何在保證自己的序列信息未被泄露的情況下，正確地計算出X和Y的漢明距離。

文獻[12]研究隱私交集基數問題，即如何在隱私保護的情況下，計算雙方集合交集的基數（即所含元素的個數）。該文指出“字符串的漢明距離問題可以轉換為隱私交集基數問題”，因此計算DNA序列漢明距離問題可以轉化為計算交集基數問題。然而該文提出的思路尚存在以下問題：第一，該文在計算隱私交集基數問題時，將問題轉化為計算兩個0-1串中數值同時為“1”的位置個數，在執行協議的過程中，泄露了其中一方的0-1串中“1”的個數，沒有很好地保護隱私;第二，為了能夠用該文協議來解決漢明距離計算問題，還需要對協議作進一步擴展，使其能夠計算兩個0-1串中數值同時為“0”的位置個數;第三，為了能夠用隱私交集基數協議來解決DNA序列漢明距離問題，還需要將DNA序列漢明距離問題轉化為隱私交集基數問題的嚴格推導和證明。

因此，若基于文獻[12]的協議來解決隱私保護DNA序列漢明距離問題，還存在問題轉化、協議擴展、隱私保護加強、效率優化等諸多問題。鑒于此，本文在解決DNA序列漢明距離問題時，既未采取文獻[12]提出的思路，也未借助隱私交集基數協議為設計模塊。主要思路如下：首先將DNA序列漢明距離問題轉化為0-1串的漢明距離問題，然后通過直接求解0-1串的漢明距離問題來求解DNA漢明距離問題。

論文的主要工作如下：

1）定義了DNA序列的0-1編碼規則，該規則將長為n的DNA序列編碼成長為4n的0-1串，證明了兩個DNA序列的漢明距離等于它們的0-1編碼串的漢明距離的一半。

2）以Goldwasser-Micali（GM）加密系統[14]為主要密碼學工具，在半誠實攻擊者模型[15]下，構造了計算DNA序列漢明距離的一個隱私保護計算協議。進一步證明了協議的正確性，并給出了基于模擬器的安全性證明，且對協議的效率進行了分析和說明。其中，GM加密系統的安全性基于二次剩余問題的難解性，加密過程按逐比特加密的方式進行（即明文空間是{0， 1}），該系統具有異或同態性，即“密文的乘積等于異或值的密文”。

1 知識準備

1.1 基本概念

同一字符集C上長度相同的兩個序列X和Y的漢明距離，定義為二者位置相同但字符不同的位置個數，記為HMD（X，Y）。特別，若X和Y是0-1序列，則HMD（X，Y）等于0-1序列X⊕Y中所含“1”的個數。

用字母A、C、G和T分別代表組成DNA的4種核苷酸腺嘌呤、胞嘧啶、鳥嘌呤和胸腺嘧啶，即DNA序列的字符集為{A，C，G，T}。用{A，C，G，T}*表示由字符A，C，G，T組合而成的、長度有限的字符串全體所構成的集合，則任意一個DNA序列X都滿足X∈{A，C，G，T}*。

隱私保護DNA序列漢明距離計算問題：用戶A和B分別擁有長度相同的DNA序列X和Y，在保護輸入隱私的情況下，A輸出漢明距離HMD（X，Y），B沒有輸出。求解DNA序列隱私保護漢明距離計算問題的安全兩方計算協議，稱為隱私保護DNA序列漢明距離計算協議。

1.2 GM加密系統[14]

對整數N>1，定義Z*N={a∈ZN：gcd（a，N）=1}。a∈Z*N叫作模N的二次剩余，如果存在x∈ZN，使得x2≡a mod N;否則a叫作模N的二次非剩余。判斷a是否是模N的二次剩余的問題稱為模N的二次剩余問題。

對素數p和任意x∈Z*p，x模p的勒讓德符號定義為：

xp=1，? x是模p的二次剩余

-1，x是模p的二次非剩余

設合數N的素因子（可重復）分解為N=p1p2…pk，則：

xN=xp1xp2…xpk

稱為x模N的雅可比符號，xpi是x模pi的勒讓德符號。

GM加密系統的密鑰生成算法、加密算法、解密算法描述如下：

1）密鑰生成算法。用戶隨機地生成兩個大素數p和q，計算N=pq，選取模N的一個二次非剩余δ∈Z*N滿足雅可比符號δN=1。公鑰是pk=（δ，N），私鑰是sk=（p，q）。

2）加密算法。明文空間是{0，1}。對明文x∈{0，1}，選取秘密隨機數r∈Z*N，計算密文Epk（x）=r2δx mod N。

3）解密算法。對密文c（c∈Z*N），如下計算明文：

Dsk（c）=0， 若c是模N的二次剩余

1，其他

GM加密系統基于模N的二次剩余問題的難解性。對攻擊者而言，未知大整數N的因數分解，模N的二次剩余問題是困難的;對私鑰擁有者而言，知道N的因數分解，模N的二次剩余問題是容易的。該密碼系統具有如下特性：

1）概率加密性。每次加密都有隨機數r參與計算密文;

2）異或同態性。Epk（x1）和Epk（x2）分別是x1和x2的密文，則（Epk（x1）·Epk（x2）） mod N是x1⊕x2的密文，即（Epk（x1）·Epk（x2）） mod N=Epk（x1⊕x2）。

1.3 半誠實攻擊模型下的隱私函數計算[15]

記f：{0，1}*×{0，1}*→{0，1}*×{0，1}*是一個二元概率多項式時間函數，其中f（X，Y）=（f1（X，X）， f2（X，X））。Π是計算f的一個雙方協議。參與方P1和P2分別以X和Y為輸入執行協議后，P1的view記為viewΠ1（X，Y）=（X，r1，m11，m12，…，m1t），P2的view記為viewΠ2（X，Y）=（Y，r2，m21，m22，…，m2k），其中，ri表示第i方的內部擲硬幣的輸出，mij表示第i方收到的第j條信息。第i方的output輸出記為outputΠi（X，Y）。

定義1 對函數f=（f1， f2），稱Π在半誠實攻擊模型下隱私計算f，如果存在概率多項式時間算法S1和S2，滿足：

{S1（X， f1（X，Y））， f2（X，Y）}≡c{viewΠ1（X，Y），outputΠ2（X，Y）}

和

{f1（X，Y），S2（Y， f2（X，Y））}≡c{outputΠ1（X，Y），viewΠ2（X，Y）}

其中≡c表示隨機變量簇的計算不可區分。

2 DNA序列的0-1編碼

定義2 長度為n的DNA序列的全域向量定義為長度為4n的如下向量：

V（n）DNA=（（A，1），（C，1），（G，1），（T，1），（A，2），（C，2），（G，2），（T，2），…，（A，n），（C，n），（G，n），（T，n））

定義3 設X=a1a2…an∈{A，C，G，T}*是長度為n的任意DNA序列，將各字符連同其位置標識視為一個整體，得到如下長度為n的序列X*：

X*=（（a1，1），（a2，2），…，（an，n））

DNA序列X的0-1編碼定義為如下長度為4n序列：

SX=（s1，s2，…，s4n）∈{0，1}4n

其中si=1當且僅當全域向量V（n）DNA中的第i （1≤i≤4n）個元素出現在序列X*中，即：

si=1 （A，i/4」+1）∈X*， i≡1 mod 4

（C，i/4」+1）∈X*，i≡2 mod 4

（G，i/4」+1）∈X*，i≡3 mod 4

（T，i/4」）∈X（*），i≡0 mod 4

其中：x∈X*表示x出現在序列X*中;a」表示a取整。

由定義可見，X*中的每個元素，決定了SX中的連續4個比特，并且在這4個連續比特中，有且僅有一個比特是“1”。

例如，長度為5的DNA序列的全域向量為：

V（n）DNA=（（A，1），（C，1），（G，1），（T，1），（A，2），（C，2），（G，2），（T，2），（A，3），（C，3），（G，3），（T，3），（A，4），（C，4），（G，4），（T，4），（A，5），（C，5），（G，5），（T，5））

對DNA序列X=CGAGT， X*={（C，1），（G，2），（A，3），（G，4），（T，5）}， 則X的0-1編碼為：

SX=（0，1，0，0對應（C，1），0，0，1，0對應（G，2），1，0，0，0對應（A，3），0，0，1，0對應（G，4），0，0，0，1對應（T，5））∈

{0，1}20

定理1 設X=a1a2…an和X=b1b2…bn是兩個長度為n的DNA序列，SX和SY的分別是X和Y的0-1編碼，則漢明距離HMD（X，Y）=HMD（SX，SY）/2，即HMD（X，Y）等于SX⊕SY中所含“1”的個數的一半。

證明 對DNA序列X=a1a2…an和X=b1b2…bn，有X*=（（a1，1），（a2，2），…，（an，n））和 Y*=（（b1，1），（b2，2），…，（bn，n）），則HMD（X，Y）=HMD（X*，Y*），即X*和Y*中位置相同但元素不同的位置個數。

記X和Y的0-1編碼分別為SX=（α1，α2，…，α4n）和SY=（β1，β2，…，β4n）。根據DNA序列的0-1編碼規則，X*中的每個元素決定了0-1編碼SX=（α1，α2，…，α4n）中的4個相鄰比特，且含1個“1”和3個“0”;同樣，Y*中的每個元素也決定了0-1編碼SY=（β1，β2，…，β4n）中的4個相鄰比特，且同樣含1個“1”和3個“0”。

對X*和Y*中的第k個位置上的元素（ak，k）和（bk，k）：

1）若（ak，k）=（bk，k），則它們在0-1編碼中決定的4個相鄰比特（β4k-3， β4k-2， β4k-1， β4k）和（β4k-3， β4k-2， β4k-1， β4k）對應相同（因為“1”所在的位置相同），因此對應比特異或（α4k-3，α4k-2，α4k-1，α4k）⊕（β4k-3，β4k-2，β4k-1，β4k）中，所含“1”的個數為0;

2）若（ak，k）≠（bk，k），則它們在0-1編碼中決定的4個相鄰比特（α4k-3，α4k-2，α4k-1，α4k）和（β4k-3， β4k-2， β4k-1， β4k）中，有2個對應比特不同（因為“1”所在的位置不同），因此（α4k-3，α4k-2，α4k-1，α4k）⊕（β4k-3， β4k-2， β4k-1， β4k）中所含“1”的個數為2。

因此，設X*和Y*中位置相同但元素不同的位置個數為h，即HMD（X*，Y*）=h，則在SX⊕SY的結果中，所含“1”的個數為2h，即HMD（SX，SY）=2h。

綜上HMD（X，Y）=HMD（X*，Y*）=h=HMD（SX，SY）/2。

3 隱私保護DNA序列漢明距離計算協議

3.1 協議描述

協議開始之前，參與方A生成自己的GM加密算法的公私鑰對（pk，sk），將公鑰pk=（δ，N）發送給B，保密私鑰sk=（p，q）。

協議1 隱私保護DNA序列漢明距離計算協議。

輸入：A和B分別擁有長度相同的DNA序列：

X=a1a2…an∈{A，C，G，T}*和Y=b1b2…bn∈{A，C，G，T}*;

輸出：A輸出漢明距離HMD（X，Y），B沒有輸出。

協議步驟：

1）A計算DNA序列X的0-1編碼SX=（α1，α2，…，α4n），調用GM加密算法，用自己的公鑰pk加密SX的每一個元素，得到加密向量：

Epk（SX）=（Epk（α1），Epk（α2），…，Epk（α4n））

然后將Epk（SX）發送給B。

2）B收到Epk（SX）后，執行以下步驟：

①計算DNA序列Y的0-1編碼SY=（β1， β2，…， β4n），調用GM加密算法，用A的公鑰pk加密SY的每一個元素，得到加密向量：

Epk（SY）=（Epk（β1），Epk（β2），…，Epk（β4n））

②根據GM加密算法的異或同態性，將Epk（SX）與Epk（SY）的對應元素在模N下相乘，得到：

Epk（SX⊕SY）=（Epk（α1⊕β1），Epk（α2⊕β2），…，Epk（α4n⊕β4n））

③隨機選取集合{1，2，…，4n}上的一個秘密置換T，對Epk（SX⊕SY）進行置換，得到：

T（Epk （SXSY））= （Epk（αT（1） βT（1） ），Epk（αT（2） ?βT（2） ），…，Epk（αT（4n ） βT（4n ） ））

將T（Epk（SX⊕SY））發送給A。

3）A收到T（Epk（SX⊕SY））后，用自己的私鑰sk解密其中的每一個元素，得到：

T（SX⊕SY）=（αT（1）⊕βT（1），αT（2）⊕βT（2），…，αT（4n）⊕βΤ（4n））

計算T（SX⊕SY）中所含“1”的個數，記為Sum，則輸出HMD（X，Y）=Sum/2。

3.2 正確性分析

定理2 在半誠實攻擊者模型下，協議1執行結束后將輸出正確的結果。

證明 在半誠實模型下，A和B都嚴格遵循協議步驟。

根據GM加密算法的同態性，第2）中的②步是正確的。由于對向量的加解密是對每個分量進行加解密，因此“加解密”和“置換”的順序可以交換。從而在第3）步中，A用自己的私鑰sk解密T（Epk（SX⊕SY））后得到的即為T（SX⊕SY）。

由于Τ（SX⊕SY）中含“1”的個數為Sum，而Τ是集合{1，2，…，4n}上的置換，故SX⊕SY中也含Sum 個“1”。根據定理1 ，漢明距離HMD（X，Y）=HMD（SX，SY）/2，即等于SX⊕SY中“1”的個數的一半，因此HMD（X，Y）=Sum/2。

3.3 安全性分析

定理3 在半誠實攻擊者模型下，協議1是安全的。

證明 在半誠實模型下，A和B都嚴格遵循協議步驟。他們可能記錄自己在執行協議過程中的中間信息，嘗試去推測對方的秘密輸入。下面將證明協議1滿足定義3的條件。

根據協議描述，A的輸出f1（X，Y）=HMD（X，Y）=Sum/2，B的輸出f2（X，Y）=⊥（空字符）。下面分兩個步驟進行證明。

步驟1 構造模擬器S1，使得下式成立：

{S1（X， f1（X，Y））， f2（X，Y）}≡c

{viewΠ1（X，Y），outputΠ2（X，Y）}

由協議描述可知，執行完協議后，A的view為：

viewΠ1（X，Y）=（X，r1，（Epk（αΤ（1）⊕βΤ（1）），Epk（αΤ（2）⊕βΤ（2）），…，Epk（αΤ（4n）⊕βΤ（4n））））

其中X是A的隱私輸入，r1是A的內部隨機帶的輸出，

（Epk（αΤ（1）⊕βΤ（1）），Epk（αΤ（2）⊕βΤ（2）），…，

Epk（αΤ（4n）⊕βΤ（4n）））=Τ（Epk（S（4n）1⊕S（4n）2））

是A從B處收到的信息。

如下構造模擬器S1：以（X， f1（X，Y））=（X，HMD（X，Y））為輸入，執行如下步驟：

1）計算DNA序列X的0-1編碼SX=（α1，α2，…，α4n）。

2）生成長度與X相同的DNA序列Y*，滿足

HMD（X，Y*）=HMD（X，Y）。

3）計算Y*的0-1編碼SY*=（β*1，β*2，…，β*4n），計算：

SX⊕SY*=（α1⊕β*1，α2⊕β*2，…，α4n⊕β*4n）

用A的公鑰pk加密SX⊕SY*的每個分量，得：

Epk（SX⊕SY*）=（Epk（α1⊕β*1），Epk（α2⊕β*2），…，Epk（α4n⊕β*4n））

4）隨機選取集合{1，2，…，4n}上的一個置換T*，對Epk（SX⊕SY*）進行置換，得到：

T*（Epk（SX⊕SY*））=（Epk（αT*（1）⊕β*T*（1）），Epk（αT*（2）⊕β*T*（2）），…，Epk（αT*（4n）⊕β*T*（4n）））

5）S1輸出：

S1（X， f1（X，Y））=（X，R1，（Epk（αT*（1）⊕β*T*（1）），Epk（αT*（2）⊕β*T*（2）），…，Epk（αT*（4n）⊕β*T*（4n））））

其中R1是S1的內部隨機帶的輸出。

下面證明：

{S1（X， f1（X，Y））， f2（X，Y）}≡c{viewΠ1（X，Y），outputΠ2（X，Y）}

由于f2（X，Y）=outputΠ2（X，Y）=⊥，故只需證明：

{S1（X， f1（X，Y））}≡c{viewΠ1（X，Y）}

即

（X，R1，（Epk（αT*（1）⊕β*T*（1）），Epk（αT*（2）⊕β*T*（2）），…，Epk（αT*（4n）⊕β*T*（4n））））≡c（X，r1，（Epk（αΤ（1）⊕βΤ（1）），Epk（αΤ（2）⊕βΤ（2）），…，Epk（αΤ（4n）⊕βΤ（4n））））

為此，分兩步完成：

1）由于r1和R1分別是S1和A的內部隨機帶的輸出，因此{r1}≡c{R1}。

2）下面只需要證明對任意1≤i≤4n，均滿足：

{Epk（αT*（i）⊕β*T*（i））}≡c{Epk（αΤ（i）⊕βΤ（i））}

根據GM加密算法，有：

Epk（αT*（i）⊕β*T*（i））=r2T*（i）·σαT*（i）⊕β*T*（i） mod n

又根據GM算法同態性，有：

Epk（αΤ（i）⊕βΤ（i））=Epk（αΤ（i））·Epk（βΤ（i））mod n=

（r2A-T（i）·σαΤ（i））（r2B-T（i）·σβΤ（i））mod n=（rA-T（i）rB-T（i））2·σαΤ（i）⊕βΤ（i） mod n

上述rT*（i），rA-T（i）和rB-T（i）分別是模擬器S1、參與方A和參與方B調用GM加密算法時選取的隨機數，故Epk（αT*（i）⊕β*T*（i））和Epk（αΤ（i）⊕βΤ（i））是隨機的，因此有：

{Epk（αT*（i）⊕β*T*（i））}≡c{Epk（αΤ（i）⊕βΤ（i））}

綜上可得：

{S1（X， f1（X，Y））， f2（X，Y）}≡c{viewΠ1（X，Y），outputΠ2（X，Y）}

步驟1證明完成。

步驟2 構造模擬器S2，使得下式成立：

{f1（X，Y），S2（Y， f2（X，Y））}≡c{outputΠ1（X，Y），viewΠ2（X，Y）}

由協議描述可知，執行完協議后，B的view為：

viewΠ2（X，Y）=（Y，r2，（Epk（α1），Epk（α2），…，Epk（α4n）））

其中Y是B的隱私輸入，r2是B的內部隨機帶的輸出，（Epk（α1），Epk（α2），…，Epk（α4n））是B從A處收到的信息。

如下構造模擬器S2：以（Y， f2（X，Y））=（Y，⊥）為輸入，執行如下步驟。

1）隨機生成長度與X相同的DNA序列X*。

2）計算X*的0-1編碼SX*=（α*1，α*2，…，α*4n），用A的公鑰pk加密SX*的每個分量，得

Epk（SX*）=（Epk（α*1），Epk（α*2），…，Epk（α*4n））

3）S2輸出：

S2（Y， f2（X，Y））=（Y，R2，（Epk（α*1），Epk（α*2），…，Epk（α*4n）））

其中R2是S2的內部隨機帶的輸出。

下面證明：

{f1（X，Y），S2（Y， f2（X，Y））}≡c{outputΠ1（X，Y），viewΠ2（X，Y）}

由于f1（X，Y）=outputΠ1（X，Y）=HMD（X，Y），故只需證明：

{S2（Y， f2（X，Y））}≡c{viewΠ2（X，Y）}

即

{（Y，R2，（Epk（α*1），Epk（α*2），…，Epk（α*4n）））}≡c

{（Y，r2，（Epk（α1），Epk（α2），…，Epk（α4n）））}

由于R2和r2分別是S2和B的內部隨機帶的輸出，因此{R2}≡c{r2}。對任意1≤i≤4n，注意到α*i來自于隨機生成的DNA序列X*，類似步驟1的證明過程，根據GM算法加密數據的隨機性，可證{Epk（α*i）}≡c{Epk（αi）}成立。因此可得：

{f1（X，Y），S2（Y， f2（X，Y））}≡c

{outputΠ1（X，Y），viewΠ2（X，Y）}

步驟2證明完成。

綜合步驟1和2，定理3證明完成。

3.4 性能分析

記n為DNA序列長度，N為GM加密算法的模數，在一次執行過程中，協議1的計算復雜度為：參與方A需要執行4n次加密運算和4n次解密運算，B需要執行4n次加密運算和4n次模N乘法;通信復雜度為：發送2條信息共8n log N比特;輪復雜度為1。

文獻[12]指出其提出的隱私集合交集基數協議能夠用來解決隱私保護DNA序列漢明距離問題，但實際上還存在問題轉化、協議擴展、隱私保護加強、效率優化等方面的工作。協議1采取了不同的解決思路來解決隱私保護DNA序列漢明距離問題。下面將對協議1與“以文獻[12]的思路為基礎的協議”（簡記為[12]-HM）進行性能比較。

協議1與[12]-HM都以GM加密算法為密碼學工具，充分利用該算法的異或同態性進行協議設計。兩種思路都涉及到計算0-1串漢明距離問題，但解決0-1串漢明距離問題的處理方法有著明顯差異。兩種方法分別記為[12]-HM0-1和協議1-HM0-1，二者的通信復雜度都為2n log N，輪復雜度都為1，A方的計算復雜度都為n次加密和n次解密，其他比較情況如表1所示，其中n是雙方的0-1串長度，N是GM加密算法的模數。

文獻[12]-HM和協議1的通信復雜度都為8n log N，輪復雜度都為1，A方的計算復雜度都為4n次加密和4n次解密，其他比較情況如表2所示，其中n是雙方的DNA序列長度，N是GM加密算法的模數。

4 結語

隱私保護科學計算是當前學界研究的熱點問題，隱私保護的DNA序列比較有利于更好地保護個人的生物特征隱私。漢明距離作為度量DNA序列相似程度的指標之一，因此需要研究在保護隱私的情況下如何計算兩個DNA序列的漢明距離。本文主要基于GM加密算法的異或同態特性，在半誠實攻擊者模型下，構造了計算DNA序列漢明距離的一個隱私保護計算協議，并證明了協議的正確性和安全性。在性能上，是否存在執行效率更高的解決方案是下一步研究的問題。此外，對隱私保護的DNA序列比較的其他問題，也有待進一步研究。

參考文獻

[1]YAO A C. Protocols for secure computations [C]// SFCS ‘82： Proceedings of 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—a completeness theorem for protocols with honest majority [C]// STOC ‘87： Proceedings of the 19th Annual ACM Symposium on Theory of Computing. New York： ACM， 1987： 218-229.

[3]BEN-OR M， GOLDWASSER S， WIGDERSON A. Completeness theorems for non-cryptographic fault-tolerant distributed computation [C]// STOC ‘88： Proceedings of the 29th Annual ACM Symposium on Theory of Computing. New York： ACM， 1988： 1-10.

[4]YAO A C. How to generate and exchange secrets [C]// SFCS ‘86： Proceedings of the 27th Annual Symposium on Foundations of Computer Science. Washington， DC： IEEE Computer Society， 1986： 162-167.

[5]ZHOU Y H， SHI W M， YANG Y G. A quantum protocol for millionaire problem with continuous variables [J]. Communications in Theoretical Physics， 2014， 61（4）： 452-456.

[6]MOHASSEL P， WEINREB E. Efficient secure linear algebra in the presence of covert or computationally unbounded adversaries [C]// Proceedings of the Annual International Cryptology Conference， LNCS 5157. Berlin： Springer， 2008： 481-496.

[7]SHI R， MU Y， ZHONG H， et al. An efficient quantum scheme for private set intersection [J]. Quantum Information Processing， 2016， 15（1）： 363-371.

[8]CHUN J Y， HONG D， JEONG I R， et al. Privacy-preserving disjunctive normal form operations on distributed sets [J]. Information Sciences， 2013， 231： 113-122.

[9]RINDAL P， ROSULEK M. Improved private set intersection against malicious adversaries [C]// Proceedings of the 2017 Annual International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 10210. Berlin： Springer， 2017： 235-259.

[10]羅小雙，楊曉元，王緒安.一類可抵抗惡意攻擊的隱私集合交集協議[J].計算機應用，2017，37（6）：1593-1598.（LUO X S， YANG X Y， WANG X A. A private set intersection protocol against malicious attack [J]. Journal of Computer Applications， 2017， 37（6）： 1593-1598.）

[11]張恩，金剛剛.基于同態加密和Bloom過濾器的云外包多方隱私集合比較協議[J].計算機應用，2018，38（8）：2256-2260.（ZHANG E， JIN G G. Cloud outsourcing multiparty private set intersection protocol based on homomorphic encryption and Bloom filter [J]. Journal of Computer Applications， 2018， 38（8）： 2256-2260.）

[12]馬敏耀，陳松良，左羽.基于Goldwasser-Micali加密系統的隱私交集基數協議研究[J].計算機應用研究，2018，35（9）：2748-2751.（MA M Y， CHEN S L， ZUO Y. Research on private set intersection cardinality protocol based on Goldwasser-Micali encryption system [J]. Application Research of Computers， 2018， 35（9）： 2748-2751.）