隐私保护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.）