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

馬敏耀 徐藝 劉卓

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

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

中圖分類號：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 引言

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

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

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

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

因此，若基于文獻[12]的協(xié)議來解決隱私保護DNA序列漢明距離問題，還存在問題轉(zhuǎn)化、協(xié)議擴展、隱私保護加強、效率優(yōu)化等諸多問題。鑒于此，本文在解決DNA序列漢明距離問題時，既未采取文獻[12]提出的思路，也未借助隱私交集基數(shù)協(xié)議為設(shè)計模塊。主要思路如下：首先將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]為主要密碼學工具，在半誠實攻擊者模型[15]下，構(gòu)造了計算DNA序列漢明距離的一個隱私保護計算協(xié)議。進一步證明了協(xié)議的正確性，并給出了基于模擬器的安全性證明，且對協(xié)議的效率進行了分析和說明。其中，GM加密系統(tǒng)的安全性基于二次剩余問題的難解性，加密過程按逐比特加密的方式進行（即明文空間是{0， 1}），該系統(tǒng)具有異或同態(tài)性，即“密文的乘積等于異或值的密文”。

1 知識準備

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}*。

隱私保護DNA序列漢明距離計算問題：用戶A和B分別擁有長度相同的DNA序列X和Y，在保護輸入隱私的情況下，A輸出漢明距離HMD（X，Y），B沒有輸出。求解DNA序列隱私保護漢明距離計算問題的安全兩方計算協(xié)議，稱為隱私保護DNA序列漢明距離計算協(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的二次剩余問題。

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

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

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

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

xN=xp1xp2…xpk

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

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

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

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

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

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

1，其他

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

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

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ù)計算[15]

記f：{0，1}*×{0，1}*→{0，1}*×{0，1}*是一個二元概率多項式時間函數(shù)，其中f（X，Y）=（f1（X，X）， f2（X，X））。Π是計算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），稱Π在半誠實攻擊模型下隱私計算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表示隨機變量簇的計算不可區(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序列，將各字符連同其位置標識視為一個整體，得到如下長度為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）個元素出現(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)相同（因為“1”所在的位置相同），因此對應(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)比特不同（因為“1”所在的位置不同），因此（α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 隱私保護DNA序列漢明距離計算協(xié)議

3.1 協(xié)議描述

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

協(xié)議1 隱私保護DNA序列漢明距離計算協(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計算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í)行以下步驟：

①計算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））

③隨機選取集合{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））發(fā)送給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”的個數(shù)，記為Sum，則輸出HMD（X，Y）=Sum/2。

3.2 正確性分析

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

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

根據(jù)GM加密算法的同態(tài)性，第2）中的②步是正確的。由于對向量的加解密是對每個分量進行加解密，因此“加解密”和“置換”的順序可以交換。從而在第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 在半誠實攻擊者模型下，協(xié)議1是安全的。

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

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

步驟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)部隨機帶的輸出，

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

下面證明：

{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)部隨機帶的輸出，因此{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加密算法時選取的隨機數(shù)，故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 構(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)部隨機帶的輸出，（Epk（α1），Epk（α2），…，Epk（α4n））是B從A處收到的信息。

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

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

下面證明：

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

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

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

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

4 結(jié)語

隱私保護科學計算是當前學界研究的熱點問題，隱私保護的DNA序列比較有利于更好地保護個人的生物特征隱私。漢明距離作為度量DNA序列相似程度的指標之一，因此需要研究在保護隱私的情況下如何計算兩個DNA序列的漢明距離。本文主要基于GM加密算法的異或同態(tài)特性，在半誠實攻擊者模型下，構(gòu)造了計算DNA序列漢明距離的一個隱私保護計算協(xié)議，并證明了協(xié)議的正確性和安全性。在性能上，是否存在執(zhí)行效率更高的解決方案是下一步研究的問題。此外，對隱私保護的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]羅小雙，楊曉元，王緒安.一類可抵抗惡意攻擊的隱私集合交集協(xié)議[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].計算機應(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].計算機應(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.）