隐私保护的传染病密切接触者身份追踪系统

陈梁景，王志伟,2,3

(1.南京邮电大学 计算机学院，江苏 南京 210003;2.江苏省大数据安全与智能处理重点实验室，江苏 南京 210023;3.江苏省计算机网络技术重点实验室，江苏 南京 210096)

0 引 言

近年来，传染性疾病比如肺炎的大规模爆发给人们敲响警钟。关于传染病患者以及其密切接触者的发现以及隔离对于控制疫情异常重要[1]。政府官员和业界人士所采取的一种通用方法是(全部或部分)实现人工追踪联系人的广泛任务的自动化。该文主要研究关于隐私保护的传染病密切接触者身份追踪系统。主要思路是：(1)密切接触者相互接触时取得彼此的公钥进行交互认证，认证成功交换彼此的身份密文信息；(2)患者被确诊后，通过执行带地域的群签名加入病人群，管理者为权威医疗机构。将患者保存的密切接触者的加密信息打包公布，并附上群签名；(3)用户读取公布的加密信息，若群签名验证成功且解密密文成功，则上报相关机构去隔离点隔离，从而达到追踪密切接触者身份的目的。必要的情况下，群管理者可以打开签名追踪到确认患者的人员信息。

1 相关工作

在隐私保护方面,Zhang等人[2]提出了一种基于邻近性的移动社交网络的隐私保护配置文件匹配算法。该算法使用户能够匹配他们的个人资料，而不透露他们的个人资料的任何信息。另一个相关研究方向是移动社交网络中保护隐私的位置共享[3-5]。然而，该领域的大多数解决方案都假设社交网络平台知道每个用户的位置，并提供基于位置的隐私保护搜索功能。澳大利亚与以色列推出了新型冠状病毒安全应用[6]以及一款HaMagen[7]的联系人追踪应用，然而用户需要对权威机构有高度的信任。另一个研究方向，Naren N[8]和Alansari S A等人[9]使用区块链来帮助推进隐私保护相关的接触追踪应用程序。Jan Camenisch[10]提出了一个紧凑群签名。允许授权机构向用户发出带有属性的成员资格凭证。该文将区域属性加入到群签名当中，区域记为相遇的区域编号。如果需要，权威医疗机构可以恢复患者的身份。

该文贡献列举如下：(1)提出了一个隐私保护的传染病密切接触者身份追踪系统方案；(2)方案第一部分提出了一个身份认证协议实现接触者双方的相遇认证，利用零知识验证公钥的正确性；(3)方案提出了一个基于Jan Camenisch等人群签名方案的带地域属性的群签名方案，实现了匿名确诊的匿名性、安全性、可追溯性。

2 预备知识

2.1 配 对

给定中性元1G的群G，G*为G{1G}。一个非对称配对组(p,G1,G2,GT,e)，p是一个质数,G1,G2,GT是p阶的群,以及e:G1×G2→GT是一个有效的可计算的非退化的双线性映射。类型3配对群是指已知G2到G1没有有效可计算同态的配对群。

2.2 Elgamal公钥加密体制

Elgamal加密算法[11]分为密钥生成算法、加密算法、解密算法，如下：

2.3 q-MSDH-1假设

Pointcheval和Sanders引入了Modified q-Strong Diffie-Hellman假设,并证明它拥有一般双线性群模型[12]。暗示了SDL假设。

定义1(q-MSDH-1假设[12])：设G为3型配对群发生器。对G的q-MSDH-1假设,对所有λ∈,Γ=(p,G1,G2,GT,e)←G(1λ)，给定和两个元组和

2.4 Pointcheval-Sanders签名方案

Pointcheval和Sanders证明了[13]，该签名方案在q-MDSH-1假设下存在不可伪造(见2.3节定义1)。

2.5 零知识证明

零知识证明是一种两方协议，允许一方说服另一方某件事是真的，而不透露其他任何东西。Yuen等人[14]提出了一个未知阶数群上离散对数(DL)关系的紧凑零知识证明，该文首先考虑一个群元素g,w∈G在未知阶群G中的简单DL关系R的ZK证明：R={x∈:w=gx}。证明者P和验证者V之间的零知识证明由以下三部分组成。

(1)验证者发送一个随机λ位素数l。

(2)证明者发现q'∈以及r∈[0,l-1]，有x=q'l+r。证明者发送Q=gq'和r给验证者。

(3)验证者验证，如果r∈[0,l-1]且Qlgr=w，则接受。

3 系统模型和安全模型

3.1 系统模型

系统如图1所示，包含三个主体，权威医疗机构、用户和公告板。角色定义如下：

图1 系统模型

-公告板：用于发布公共信息。它可以通过使用web或者区块链系统来实例化。

-用户(User)：它可以被称为正常使用手机的人群。在其余部分，使用Alice和Bob来表示两个用户为密切接触者。

-权威医疗机构(D)：只有医生才能将患者确诊，并颁发给患者确诊凭证患者，而医生也隶属于某家医院。

必须做出以下合理假设：

(1)用户不会公开他们的社交活动(例如在微博上发布与某人的合照)。

(2)系统和智能手机都连接到了互联网上。

(3)智能手机可以通过蓝牙连接。

(4)用户不会与他人共享私钥。

(5)医生或医疗机构是完全可信的。

3.2 威胁模型

在实际应用中，一个安全的隐私保护身份追踪系统应满足以下属性：

(1)正确性：用户相遇，彼此可以正确地进行相遇认证，并正确地将对方的身份信息用对方的公钥加密后，保存在自己手机上。若某用户被确诊后，可以正确入群，并取得医生颁发的确诊凭证。此外，若有需要，医生可以正确地恢复出患者的身份信息。

(2)匿名性：除医生外，任何人都不应知道确诊病人的身份详情。对手包括该患者的所有密切接触者(该密切接触者是确诊前的)和公众。任何人，都不应了解确诊患者密切接触者的身份信息，包括接触者的位置。这里的密码敌手试图找出确诊患者密切接触者的所有细节。

(3)可追溯性：当需要时，权威医疗机构可打开病人群签名，可追溯性对于任何有效的令牌，只要发行者是诚实的，它就保证了开放既不能失败，也不能暴露一个不正确的诚实身份。

4 关于隐私保护的密切接触者追踪协议

4.1 概 述

本协议有四个阶段。在注册阶段，用户选择自己的私公钥。医生将获得医院颁发的用户密钥，该密钥用于代表医院生成群签名。在相遇认证阶段，密切接触者之间相互接触取得彼此的公钥，进行公钥零知识证明。认证完毕后，交换彼此的身份信息密文。在匿名确诊阶段，用户确诊后，通过执行带区域属性的群签名加入病人群，管理者为权威医疗机构。在公示解密阶段，将该患者手机中传染周期内的密接者加密信息以及群签名张贴到公告牌上。若群签名验证成功且解密密文成功，则表示该密文信息指向他们自己。必要的情况下，群管理者(医生)可以打开签名追踪到确认患者的身份信息。

4.2 详细描述

4.2.1 注册阶段

(1)用户注册：

Step2：用户Alice选择一个私钥skA，私钥为一个随机数a(1

Step3：Alice随机生成标识IDA∈p。

(2)医生注册：

G为3型配对组生成器，H为哈希函数，PS为改进Pointcheval-Sanders签名方案。用k来表示每个用户的属性个数，本方案仅仅采用一个区域属性，k取值为1。

Step1：Setup(1λ,k)→pp：生成Γ=(p,G1,G2,GT,e)←G(1λ)，返回 (Γ,k+1)。生成公共参数pp，用于生成发行者(一般情况下为权威医疗机构)密钥。

4.2.2 相遇认证阶段

(1)公钥零知识证明。

Alice和Bob相遇，Alice向Bob发送自己的公钥pkA。Alice要向Bob证明，Bob收到的pkA:A=gamodp是正确产生的，Bob已收到有效的Alice公钥，如下：

①验证者(Bob)发送一个随机λ位素数l给证明者(Alice)。

②证明者(Alice)的私钥skA为a∈以及r∈[0,l-1]，有a=ql+r，计算gq=Q。证明者(Alice)发送r给验证者(Bob)。

③验证者(Bob)验证，如果r∈[0,l-1]且Qlgr=A，则确认收到的pkA是正确的。

在另一方面，Bob也这样做，向Alice发送自己的公钥pkB，让Alice验证他收到的自己的公钥是否是正确产生的。

(2)相遇认证。

相遇认证阶段协议模型如图2所示。

图2 相遇认证协议模型

认证请求：将Key用Bob的公钥进行Elgamal加密CB=(Key)pkB，Key为一次性会话密钥，用于此会话中接触者双方之间的信息加密通信如下：

Step1：对消息Key随机选择整数r(1

Step2：计算c≡gr(modp)，c'≡yrKey(modp)；

Step3：生成密文CB=(c,c')。

将mA=(IDA,loc,T)用Key加密CKey=(IDA,loc,T)Key并将CKey和CB一起发送给Bob。

请求验证：Bob在接收到消息后，用自己的私钥skB解密获得对称密钥Key，如下：

Step1：Bob收到密文CB=(c,c')；

Step3：得到明文m=Key。

接触者Bob可以解密(mA)Key，从而获取Alice的相关信息(身份标识，相遇地点编号，时间戳)。用pkA对mA进行Elgamal加密。将加密完的信息登记在B的手机上。

请求响应：相对的，Bob也这样做，将mB用Key加密CKey=(mB)Key。Bob向Alice发送响应消息(mB)Key。其中mB为Bob的相关信息，而mB=(IDB,loc,T)，其中IDB为Bob的身份标识，loc为接触者双方相遇的地点，T为接触者双方相遇的时间。

响应确认：在接收到消息后，Alice使用对称密钥可以解密CKey，从而获取Bob的相关信息(身份标识，相遇地点编号，时间戳)。验证相遇地点编号以及时间戳，不同则验证失败。用pkB对mB进行Elgamal加密。将加密信息登记在Alice的手机上。

4.2.3 匿名确诊阶段

在本小节中，将介绍关于一个重要构建块，即带区域属性的动态群签名，基于动态群签名[15]改进而来。本阶段通过权威医疗机构和用户之间发行签名，来实现用户信息的隐私保护以及匿名。

(1)生成确诊凭证。

Issue：为了在用户u和权威医疗机构D之间发行签名，假设用户和发行者之间通信的信道是安全信道。如果一方中止协议，则返回⊥。进一步假设身份空间ID是Zp的多项式大小的子集。

Step1：Issue.D(sk,st,ID,regionid)。

-如果st中存在记录(ID,regionid，*)，则中止；

-σ=(a',σ1,σ2)←PS.Sign(sk,(ID,T))；

-将σ发送给u，并返回st'

←st∪(ID,regionid,a')，将状态更新为st'。

ID是患者用户的身份标识，regionid为患者用户所在区域的编号值。PS为改进的Pointcheval-Sanders签名方案。

Step2：Issue.U(ID,regionid,pk),一旦从D接收到σ：

-验证PS.Vf(GPK,(ID,regionid),σ)=1，如果不是则中止；

cred为病人加入病人群的入群凭证。确诊的病人加入病人群。

(2)匿名签名。

对确诊患者的密切接触者的加密信息，用带地域属性的群签名签名。表明该信息确实是来自确诊病人，且是该确诊病人的密切接触者相关信息。

Auth(GPK,cred,m)→tok：分析

m即为确诊病人最近传染周期内的密切接触者Bob的加密信息(mB)pkB。tok为确诊患者对其最近传染周期内的密切接触者(例如Bob)的加密信息的签名。

4.2.4 公示解密阶段

(1)签名公示。

Step2：将确诊患者最近传染周期内的密切接触者(例如Bob)的加密信息(mB)pkB和tok以及σ*公布在公告板上。公布信息时，按照患者所在区域划分进行公布。

(2)解密查询。

Step1：外界用户验证信息真实性以及是否被篡改。

①先验证该信息是否被权威医疗机构授权。验证PS.Vf(GPK,(m1,…,mn),σ*)=1，若不是，则该信息无效。

②验证公布在公告板上的tok带属性的群签名，若验证成功，则该信息确实是来自确诊患者。Vf(GPK,m,regionid,tok)→b：用π=(c,vID,va')，regionid=a1来分析tok=(σ1,σ2,π)。如果σ1≠1G且c=H0(u,regionid,m,σ1,σ2,GPK)，则返回1。这是因为

Step2：验证成功之后，用户读取加密信息。如果可以用自己的私钥解密某个加密信息，若能解密其中某个信息，则说明该用户就是确诊患者的密切接触者之一。

4.2.5 身份追踪

医疗机构可打开群签名，找到确诊患者的身份信息。Open(GSK,st,m,regionid,tok)→ID/⊥：为消息m属性regionid生成身份验证令牌tok=(σ1,σ2,π)的用户恢复身份ID。它首先验证tok对m和regionid是否有效。验证成功，遍历st中的元组(ID,regionid,a')，直到找到一个使得(a',σ1,σ2)在(ID,regionid)上是一个有效的PS签名，然后返回ID。如果没有找到这样的元组，则返回⊥。

5 方案的安全性及性能分析

5.1 安全性分析

本方案的安全性主要是基于带属性的动态群签名方案[10]以及ElGamal加密体制的安全性。

定理1：在随机oracle模型中，如果第一组DDH和SDL假设都对组生成器G有效，则带地域属性的动态群签名方案满足匿名性。

以及c←H0(u,regionid*,m*,σ1,σ2,GPK)。Δ设置π←(c,sID,sa')，以及返回(σ1,σ2,π)给Λ。

Δ对查询挑战的回答由于C计算的σ1和σ2的分布，在计算上与C0的回答没有区别，且Δ在G1中的DDH假设下是不可区分的。C0和Δ的不可区分性论证类似于Jan Camenisch等人方案[10]的证明。

还原(reduction)算法像挑战之前一样回答其他查询。因此，对Issue,Issue.D,Auth, Corrupt,Open查询和挑战的查询的联合分布的答案还原算法都相同地分布到C0或Δ，这取决于(g0,g1,g2,g3)是否为DDH元组。因此DDH假设下，C0和Δ在计算上不可区分(任何对手的明显优势最多是先验还原算法|ID|2倍DDH优势)。同样，Δ和C1在计算上无法区分。C0和C1在计算上不可区分，DGSR在DDH假设下满足匿名性。接着，列举一些典型的攻击进行分析：

5.1.1 敌手的窃听攻击

窃听是一种捕获未经授权的机密信息的攻击。加密提供了强大的防御窃听。在该框架中，所有通信都是加密的，以防止窃听。从理论上讲，如果攻击者无法获得密钥，他们就无法解密消息以获得消息内部的内容。

5.1.2 中间人攻击

中间人(man-in-middle，MITM)攻击是指攻击者在通信过程中伪装成正确的人，利用从一方接收到的信息欺骗另一方。受害者双方都觉得他们在直接交换信息。然而，本协议采用了零知识证明，能够验证彼此公钥是否是正确产生的，无法冒充其他人，并把自己的公钥顶替他人的公钥。不能将无效公钥引入认证。它保证了对MITM攻击的强大防御，因为MITM攻击者不可能在没有正确的私钥的情况下实现公钥的零知识证明。

5.1.3 重放攻击

在重放攻击中，攻击者获取两个受害者之间的信息并拦截该信息并欺骗性地重放它。这种攻击可以通过在相遇认证中使用一次性共享密钥来禁用。此外，这两个认证都使用时间戳和带随机数的ElGamal加密体制来防止应答攻击。如果攻击者想要实现他的目标，他必须猜测一次性共享密钥，但正如上面分析的，这几乎是不可能的。

5.2 性能分析

对协议进行性能评估，测试环境如下：处理器：Intel(R) Core(TM) i7-8550U CPU @ 1.80 GHz 2.00 GHz，RAM 16.00 GB。

语言：Java+JPBC库+Bouncycastle第三方库。

5.2.1 相遇身份认证性能分析

为方便后续的性能评估,定义以下符号：Th:运行1次Hash函数所需的时间(Th≈0.32 ms)；Ts:运行1次对称加密所需的时间(Ts≈0.8 ms)；Te:运行一次Elgamal加密或解密所需要的平均时间(Te≈2.6 ms)；Tzk:运行1次公钥零知识证明所需的时间(Tzk≈13 ms)。异或运算的计算量很小，忽略不计。上述这些操作运行所花费的时间为10次实验的平均值。

表1列出了文中相遇阶段身份认证协议与Zhao[17]身份认证协议计算开销的对比。且文中对相遇双方执行了高效的零知识证明[14]。无需第三方CA机构，仅通过双方进行彼此公钥的零知识证明，即可确认彼此公钥的正确性。Zhao[17]协议是非对称密钥双向认证协议，需要彼此注册身份，且登录和双向认证阶段的信息构造运算较为复杂。文中相遇阶段身份认证协议相比Zhao[17]的身份认证协议在保证安全性的同时也更加高效。且应用Yuen[14]的紧致零知识证明仅仅需要一次实现验证，十分高效。

表1 身份认证性能比较

5.2.2 匿名确诊阶段性能分析

病人身份验证令牌包含两个G1元素和三个p元素,共计232个字节。群签名知识证明中的哈希值实际上可以缩短，进一步将群签名缩短为216字节。在本方案中，由于令牌大小为216字节，基于配对的实例化足够紧凑，可以与本协议的病人确诊方案结合使用。

本次测试分别测试文中方案匿名确诊阶段群签名的令牌生成过程、签名过程所消耗的时间，同时在相同环境下与Jan Camenisch[10]方案进行了测量比较，结果如表2所示。

表2 匿名确诊性能比较 ms

如表2所示，文中方案在效率上略优于Jan Camenisch[10]方案。文中方案采用带地域属性的动态群签名方案，仅采用一个属性，相较于Jan Camenisch提出的多属性动态群签名方案更为简便，在性能上更加优秀。

5.2.3 公示解密阶段性能分析

图3表示在公示解密阶段，512 bit和1 024 bit密钥长度时，匹配解密一定数量的密文的性能情况。公布的密文越多，解密匹配的次数越多，运行时间也越多。密钥长度也会影响运行的时间。为了保证实验的随机性和真实性，分别随机选取50条，100条，150条，200条密文进行解密匹配，计算时间消耗。计算200次时，1 024 bit密钥长度的时间消耗都在1 000 ms以下，512 bit密钥长度的时间消耗仅有100 ms左右。

图3 解密匹配执行时间

考虑到实际的计算能力远远高于文中的实验条件，解密匹配的时间消耗会更短，因此文中协议具有较好的性能。且Elgamal虽然是公钥密码体制，但身份信息较短，约256比特，解密代价较小，能够为资源受限的用户设备所容忍。

6 结束语

用ElGamal加密体制以及Yuen的零知识证明方法，来验证相遇双方身份。采用对称加密实现加密传输彼此身份信息，用对方公钥将对方身份信息加密保存在自己手机上。在病人匿名确诊认证阶段，基于带属性的群签名，对患者确诊进行匿名认证。在必要情况下，可以通过打开群签名的方式来达到追踪患者身份的目的。该方案的隐私保护特性在于：(1)匿名性：患者身份不能泄露；(2)可追踪性：在公示阶段，用户可通过尝试解密公布的加密信息来验证自己是否为患者的密切接触者。