馬敏耀 徐藝 劉卓

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

關(guān)鍵詞：漢明距離;DNA序列;隱私保護(hù);安全多方計(jì)算;同態(tài)加密

中圖分類號：TP309

文獻(xiàn)標(biāo)志碼：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 引言

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

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

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

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

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

論文的主要工作如下：

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

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

1 知識準(zhǔn)備

1.1 基本概念

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

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

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

1.2 GM加密系統(tǒng)[14]

對整數(shù)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的二次剩余問題。

對素?cái)?shù)p和任意x∈Z*p，x模p的勒讓德符號定義為：

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

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

設(shè)合數(shù)N的素因子（可重復(fù)）分解為N=p1p2…pk，則：

xN=xp1xp2…xpk

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

GM加密系統(tǒng)的密鑰生成算法、加密算法、解密算法描述如下：

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

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

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

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

1，其他

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

1）概率加密性。每次加密都有隨機(jī)數(shù)r參與計(jì)算密文;

2）異或同態(tài)性。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 半誠實(shí)攻擊模型下的隱私函數(shù)計(jì)算[15]

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

定義1 對函數(shù)f=（f1， f2），稱Π在半誠實(shí)攻擊模型下隱私計(jì)算f，如果存在概率多項(xiàng)式時間算法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表示隨機(jī)變量簇的計(jì)算不可區(qū)分。

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 設(shè)X=a1a2…an∈{A，C，G，T}*是長度為n的任意DNA序列，將各字符連同其位置標(biāo)識視為一個整體，得到如下長度為n的序列X*：

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

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

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

其中si=1當(dāng)且僅當(dāng)全域向量V（n）DNA中的第i （1≤i≤4n）個元素出現(xiàn)在序列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出現(xiàn)在序列X*中;a」表示a取整。

由定義可見，X*中的每個元素，決定了SX中的連續(xù)4個比特，并且在這4個連續(xù)比特中，有且僅有一個比特是“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對應(yīng)（C，1），0，0，1，0對應(yīng)（G，2），1，0，0，0對應(yīng)（A，3），0，0，1，0對應(yīng)（G，4），0，0，0，1對應(yīng)（T，5））∈

{0，1}20

定理1 設(shè)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”的個數(shù)的一半。

證明 對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*中位置相同但元素不同的位置個數(shù)。

記X和Y的0-1編碼分別為SX=（α1，α2，…，α4n）和SY=（β1，β2，…，β4n）。根據(jù)DNA序列的0-1編碼規(guī)則，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）對應(yīng)相同（因?yàn)椤?”所在的位置相同），因此對應(yīng)比特異或（α4k-3，α4k-2，α4k-1，α4k）⊕（β4k-3，β4k-2，β4k-1，β4k）中，所含“1”的個數(shù)為0;

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

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

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

3 隱私保護(hù)DNA序列漢明距離計(jì)算協(xié)議

3.1 協(xié)議描述

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

協(xié)議1 隱私保護(hù)DNA序列漢明距離計(jì)算協(xié)議。

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

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

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

協(xié)議步驟：

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

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

然后將Epk（SX）發(fā)送給B。

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

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

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

②根據(jù)GM加密算法的異或同態(tài)性，將Epk（SX）與Epk（SY）的對應(yīng)元素在模N下相乘，得到：

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

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

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

將T（Epk（SX⊕SY））發(fā)送給A。

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

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

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

3.2 正確性分析

定理2 在半誠實(shí)攻擊者模型下，協(xié)議1執(zhí)行結(jié)束后將輸出正確的結(jié)果。

證明 在半誠實(shí)模型下，A和B都嚴(yán)格遵循協(xié)議步驟。

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

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

3.3 安全性分析

定理3 在半誠實(shí)攻擊者模型下，協(xié)議1是安全的。

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

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

步驟1 構(gòu)造模擬器S1，使得下式成立：

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

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

由協(xié)議描述可知，執(zhí)行完協(xié)議后，A的view為：

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

其中X是A的隱私輸入，r1是A的內(nèi)部隨機(jī)帶的輸出，

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

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

是A從B處收到的信息。

如下構(gòu)造模擬器S1：以（X， f1（X，Y））=（X，HMD（X，Y））為輸入，執(zhí)行如下步驟：

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

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

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

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

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）隨機(jī)選取集合{1，2，…，4n}上的一個置換T*，對Epk（SX⊕SY*）進(jìn)行置換，得到：

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的內(nèi)部隨機(jī)帶的輸出。

下面證明：

{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的內(nèi)部隨機(jī)帶的輸出，因此{(lán)r1}≡c{R1}。

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

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

根據(jù)GM加密算法，有：

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

又根據(jù)GM算法同態(tài)性，有：

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調(diào)用GM加密算法時選取的隨機(jī)數(shù)，故Epk（αT*（i）⊕β*T*（i））和Epk（αΤ（i）⊕βΤ（i））是隨機(jī)的，因此有：

{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 構(gòu)造模擬器S2，使得下式成立：

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

由協(xié)議描述可知，執(zhí)行完協(xié)議后，B的view為：

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

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

如下構(gòu)造模擬器S2：以（Y， f2（X，Y））=（Y，⊥）為輸入，執(zhí)行如下步驟。

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

2）計(jì)算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的內(nèi)部隨機(jī)帶的輸出。

下面證明：

{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的內(nèi)部隨機(jī)帶的輸出，因此{(lán)R2}≡c{r2}。對任意1≤i≤4n，注意到α*i來自于隨機(jī)生成的DNA序列X*，類似步驟1的證明過程，根據(jù)GM算法加密數(shù)據(jù)的隨機(jī)性，可證{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加密算法的模數(shù)，在一次執(zhí)行過程中，協(xié)議1的計(jì)算復(fù)雜度為：參與方A需要執(zhí)行4n次加密運(yùn)算和4n次解密運(yùn)算，B需要執(zhí)行4n次加密運(yùn)算和4n次模N乘法;通信復(fù)雜度為：發(fā)送2條信息共8n log N比特;輪復(fù)雜度為1。

文獻(xiàn)[12]指出其提出的隱私集合交集基數(shù)協(xié)議能夠用來解決隱私保護(hù)DNA序列漢明距離問題，但實(shí)際上還存在問題轉(zhuǎn)化、協(xié)議擴(kuò)展、隱私保護(hù)加強(qiáng)、效率優(yōu)化等方面的工作。協(xié)議1采取了不同的解決思路來解決隱私保護(hù)DNA序列漢明距離問題。下面將對協(xié)議1與“以文獻(xiàn)[12]的思路為基礎(chǔ)的協(xié)議”（簡記為[12]-HM）進(jìn)行性能比較。

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

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

4 結(jié)語

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

參考文獻(xiàn)

[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]羅小雙，楊曉元，王緒安.一類可抵抗惡意攻擊的隱私集合交集協(xié)議[J].計(jì)算機(jī)應(yīng)用，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]張恩，金剛剛.基于同態(tài)加密和Bloom過濾器的云外包多方隱私集合比較協(xié)議[J].計(jì)算機(jī)應(yīng)用，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加密系統(tǒng)的隱私交集基數(shù)協(xié)議研究[J].計(jì)算機(jī)應(yīng)用研究，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.）