本发明公开了一种传染病患者密切接触者的隐私保护追溯系统及方法，系统包括：可信中心(TA)、服务器(CS)、用户(USER)；假设所述系统内有n位用户USERi。TA分配和计算系统参数：用户的身份标识ID、用户匹配密钥、服务器密钥、通讯密钥、Hash函数，USERi将个人敏感的实时位置活动轨迹通过用户匹配密钥和通讯密钥加密生成报告上传到CS，CS由通讯密钥进行身份验证，进而匹配并整合构建出一张由密文报告组成的社会活动网络图G；最后通过加密上传患者活动轨迹，CS定位患者顶点后根据图G搜索出当前所有的患者密切接触者以便后续进行检查和诊断。本发明能够保证在接触者追溯时用户隐私不被泄露，同时支持动态更新和多次追溯，速度快、处理准确高效。
1.一种传染病患者密切接触者的隐私保护追溯方法，其特征在于，包括以下步骤：步骤1：系统参数生成；
步骤1.1：可信中心TA选择参数m，用于保证活动区域和时间能被完整地映射，生成用户m×m匹配密钥(N1,N2,N3,N4)和服务器密钥M，其中N1,N2,N3,N4,M∈R 且都为可逆矩阵，即m行m列的矩阵且矩阵元素均为随机数；
步骤1.2：可信中心TA选择n对可逆矩阵(Ui,Vi)作为通讯密钥，其中Ui,Vi∈R ；
步骤1.3：可信中心TA选择安全加密hash函数 用于对活动区域中的所有重要活动地点进行映射，从而数值化成二元序列；可信中心TA选择安全加密hash函数 用于对当前时间进行映射；可信中心TA选择安全加密hash函数m
H：{0，1}*→{0，1}，用于对用户进行验证，其中2m1+2m2＝m；公布(H1,H2,H)；
步骤2：实体注册，包括用户USER注册和服务器CS注册；
步骤2中所述用户USER注册，具体包括以下子步骤：步骤2.1.1：用户USERi发送注册请求；
步骤2.1.2：可信中心TA从整数序列{1,2,…,n}中随机地选择一个数作为此用户的身份标识IDi，每次选择不重叠，即唯一标识；
步骤2.1.4：可信中心TA向用户USERi返回 并不再保存这些密钥；
步骤2中所述服务器CS注册，具体包括以下子步骤：步骤2.2.1：服务器CS发送注册请求；
步骤2.2.2：可信中心TA向服务器CS返回 并不再保存这些密钥；
步骤3.1：用户USERi周期性地收集自己的位置信息Dj和当前时戳Tj；计算：H1(Dj)，补码H2(Tj)，补码 用户USERi将得到活动信息从而由m比特组成一个m阶的向量Xj，每个比特为向量的每个元素；
步骤3.2：用户USERi生成个人活动轨迹报告，并将个人活动轨迹报告发送给服务器CS；
步骤3.2.1：对于Xj中每一个元素 用户USERi选择两对随机数(p′j,k,p″j,k)和(q′j,k,q″j,k)，其中 使得Xj能够被拆分为一对列向量(p′j,p″j)和一对行向量(q′j,q″j)；
步骤3.2.2：用户USERi通过密钥 生成密文个人活动轨迹报告步骤3.2.3：用户USERi在个人活动轨迹报告后添加附加信息；
步骤3.2.3.1：用户USERi计算签名信息 其中Tj是时间戳；
步骤3.2.3.2：选择m对随机数(w′j,k,w″j,k)，使得 能够被拆分为一对列向量(w′j,w″j)；
步骤3.2.3.3：用户USERi通过密钥 生成个人活动轨迹报告签名σj；
步骤3.2.4：用户USERi将个人活动轨迹报告(IDi,Yj,σj)发送给服务器CS；
步骤4.1：服务器CS收到个人活动轨迹报告之后，首先需要对报告进行身份验证，确保收到的报告是来自合法用户且该用户的轨迹信息未被篡改或伪造；
步骤4.1中，服务器CS收到活动轨迹报告(IDi,Yj,σj)之后，对报告进行身份验证，是通过密钥 验证下面等式是否成立；
若等式成立，则可确保收到的报告是来自合法用户且该用户的轨迹信息未被篡改或伪造；否则服务器丢弃该活动轨迹报告；
步骤4.2.1：每条通过身份验证的个人活动轨迹报告视为一个顶点(IDi,Yj)添加到图G中，每个用户IDi的一系列活动按照提交先后进行连接视为单向边添加到图G中；其中，每个用户USERi的每条个人活动轨迹报告记为Yj；
步骤4.2.2：对于每个用户USERi的每条个人活动轨迹报告Yj，计算此报告与其他所有用户USERi′的活动报告Yj′的相似性 其中i′≠i；如果 则将顶点(IDi,Yj)和(IDi′,Yj′)进行双向连接，将此双向边添加到图G中；
步骤4.2.3：遍历每个顶点，重复进行活动报告相似性判断，其中遍历过程跳过已经被双向连接的顶点；根据所有的顶点和边可以构造社会活动图G；
步骤5.1：生成已经被确诊感染的用户的患者活动轨迹报告；
步骤5.3：服务器CS将感染者的活动轨迹添加到图G中；
步骤5.4.1：对于感染者每个活动地点，服务器CS在图G中找到所有存在双向连接的邻居顶点，被视为密切接触者；
步骤5.4.2：服务器CS对接触者集合中的ID进行去重操作；
步骤5.4.3：服务器CS对所有密切接触者发送提醒以便后续进行检查和诊断。
2.一种传染病患者密切接触者的隐私保护追溯系统，用于实现权利要求1所述的传染病患者密切接触者的隐私保护追溯方法；其特征在于：包括可信中心TA、服务器CS、用户USER；
若所述系统内有n位用户USERi，i＝1,2,…,n；可信中心TA分配和计算系统参数，包括用户的身份标识ID、用户匹配密钥、服务器密钥、通讯密钥、Hash函数；USERi将个人敏感的实时位置活动轨迹通过用户匹配密钥和通讯密钥加密生成轨迹报告上传到服务器CS；服务器CS由通讯密钥进行身份验证，进而匹配并整合构建出一张由密文报告组成的社会活动网络图G；最后通过加密上传患者活动轨迹，服务器CS定位患者顶点后根据图G搜索出当前所有的患者密切接触者以便后续进行检查和诊断。
一种传染病患者密切接触者的隐私保护追溯系统及方法
技术领域
[0001] 本发明属于社会网络技术领域和用户敏感数据隐私保护技术领域，涉及一种社会网络中保护用户活动隐私的接触者追溯系统及方法，尤其涉及一种外包环境下用户敏感数据隐私需要的传染病接触者追溯系统及方法。
背景技术
[0002] 在现有的接触者跟踪方案中，公民隐私大都不是设计目标，通常使用用户生成的位置历史记录来计算接触者的追踪信息。但攻击者可以监听共享的实时位置信息，分析这些数据并用于非法操作。因此，如何保护社会活动中用户的敏感位置信息隐私是一个重要课题。
[0003] 在接触者跟踪中，所有用户上传自己的实时位置信息。用户提供当前时间和当前位置。通过时间和位置的唯一匹配可以确定用户是否是患者的密切接触者。
[0004] 目前也出现了一些解决上述问题的方法，例如基于多方安全计算来测量接触者与患者之间欧几里得距离的方法；同态性质使得对加密后得到的密文实施某种操作等同于对被加密的明文实施另一种操作得到的密文。但是已有的追溯方案首先每次搜索需要重新匹配计算不能形成一张有效的社会活动图，其次多轮通讯具有较高的时间开销，无法保证大型社会网络搜索的实用性。
[0005] 为了保护位置隐私和节省开销，用户活动信息通常被加密后再上传，在外包环境下进行匹配。进而整个过程应当保证服务器无法得知用户的敏感位置信息，系统用户除了知道自身是否为密切接触者得不到其他任何有效信息。
发明内容
[0006] 为了解决上述隐私保护问题，本发明提供了一种传染病患者密切接触者的隐私保护追溯系统及方法。
[0007] 本发明的系统所采用的技术方案是：一种传染病患者密切接触者的隐私保护追溯系统，包括可信中心TA、服务器CS、用户USER；
[0008] 若所述系统内有n位用户USERi，i＝1,2,…,n；可信中心TA分配和计算系统参数，包括用户的身份标识ID、用户匹配密钥、服务器密钥、通讯密钥、Hash 函数；USERi将个人敏感的实时位置活动轨迹通过用户匹配密钥和通讯密钥加密生成轨迹报告上传到服务器CS；服务器CS由通讯密钥进行身份验证，进而匹配并整合构建出一张由密文报告组成的社会活动网络图G；最后通过加密上传患者活动轨迹，服务器CS定位患者顶点后根据图G搜索出当前所有的患者密切接触者以便后续进行检查和诊断。
[0009] 本发明的方法所采用的技术方案是：一种传染病患者密切接触者的隐私保护追溯方法，包括以下步骤：
[0010] 步骤1：系统参数生成；
[0011] 步骤1.1：可信中心TA选择安全参数m(保证活动区域和时间能被完整地映射，可设m×m置为100)，生成用户匹配密钥(N1,N2,N3,N4)和服务器密钥M，其中N1,N2,N3,N4,M∈R 且都为可逆矩阵，即m行m列的矩阵且矩阵元素均为随机数；
[0012] 步骤1.2：可信中心TA选择n对可逆矩阵(Ui,Vi)作为通讯密钥，其中 Ui,Vi∈Rm×m；
[0013] 步骤1.3：可信中心TA选择安全加密hash函数 用于对活动区域中的所有重要活动地点进行映射，从而数值化成二元序列；可信中心 TA选择安全加密hash函数 用于对当前时间进行映射；可信中心TA选择安全加密hash
* m
函数H：{0，1}→{0，1}，用于对用户进行验证，其中2m1+2m2＝m；公布(H1,H2,H)；
[0014] 步骤2：实体注册，包括用户USER注册和服务器CS注册；
[0015] 步骤3：个人活动轨迹加密及报告生成；
[0016] 步骤3.1：用户USERi将利用智能设备周期性地(如每到一个新的活动地点) 收集自己的位置信息Dj和当前时戳Tj；计算：H1(Dj)，补码 H2(Tj)，补码 用户USERi将得到活动信息 从而由m比特组成一个m阶的向量Xj，每个比特为向量的每个元素；
[0017] 步骤3.2：用户USERi生成个人活动轨迹报告，并将个人活动轨迹报告发送给服务器CS；
[0018] 步骤4：社会活动网络图构造；
[0019] 步骤4.1：服务器CS收到个人活动轨迹报告之后，首先需要对报告进行身份验证，确保收到的报告是来自合法用户且该用户的轨迹信息未被篡改或伪造；
[0020] 步骤4.2：服务器CS构造社会活动图；
[0021] 步骤4.2.1：每条通过身份验证的个人活动轨迹报告视为一个顶点(IDi,Yj)添加到图G中，每个用户IDi的一系列活动按照提交先后进行连接视为单向边添加到图G中；其中，每个用户USERi的每条个人活动轨迹报告记为Yj；
[0022] 步骤4.2.2：对于每个用户USERi的每条个人活动轨迹报告Yj，计算此报告与其他所有用户USERi′的活动报告Yj′的相似性 其中i′≠i；如果 则将顶点(IDi,Yj)和(IDi′,Yj′)进行双向连接，将此双向边添加到图G中；
[0023] 步骤4.2.3：遍历每个顶点，重复进行活动报告相似性判断，其中遍历过程跳过已经被双向连接的顶点；根据所有的顶点和边可以构造社会活动图G；
[0024] 步骤5：被感染者密切接触者追溯。
[0025] 本发明方法与现有技术相比有如下的优点和有益效果：
[0026] (1)本发明具有很高的安全性，所有轨迹报告中活动信息都通过一次一密形式的随机数而分割，因此每份报告都是随机的不可回溯的。同时每个用户单独的通讯密钥保证只有服务器才能进行有效利用报告，同时合谋攻击也无法得到更多的有效信息；而报告附加的签名信息使得服务器能够验证用户身份以防恶意攻击方进行大量伪造，时间戳也能防止重放攻击。而用户匹配密钥保证了活动报告的正确匹配同时防止服务器分析出用户活动信息，服务器只有出于匹配的目的才能有效利用报告。因此，本发明具有很高的隐私保护安全性。
[0027] (2)利用Hash函数将活动信息数值化并排列为向量，同时K近邻方案的匹配方法能够计算出向量的内积从而确定出密切接触者，通过补码的形式即使知道内积数值m也无法反推确切的向量组合。
[0028] (3)本发明提出了一种传染病患者密切接触者的隐私保护搜索方法，在保证安全性的前提下，服务器生成双向的社会活动图，只需要搜索患者的邻居顶点，速度快，处理高效，并且满足动态更新和多次搜索，同时过程中的参数都可以预生成从而降低实际运行时间。
附图说明
[0029] 图1：本发明实施例的系统构架图；
[0030] 图2：本发明实施例的方法流程图；
[0031] 图3：本发明实施例的方法中实体注册的流程图；
具体实施方式
[0032] 为了便于本领域普通技术人员理解和实施本发明，下面结合附图及实施例对本发明作进一步的详细描述，应当理解，此处所描述的实施示例仅用于说明解释本发明，并不用于限定本发明。
[0033] 如图1所示，本发明提供了一种传染病患者密切接触者的隐私保护追溯系统。该系统包括：可信中心(TA)、服务器(CS)、用户(USER)；
[0034] 假设系统内有n位用户USERi(i＝1,2,…,n)。TA分配和计算系统参数：用户的身份标识ID、用户匹配密钥、服务器密钥、通讯密钥、Hash函数，USERi将个人敏感的实时位置活动轨迹通过用户匹配密钥和通讯密钥加密生成报告上传到CS，CS由通讯密钥进行身份验证，进而匹配并整合构建出一张由密文报告组成的社会活动网络图G；最后通过加密上传患者活动轨迹，CS定位患者顶点后根据图G搜索出当前所有的患者密切接触者以便后续进行检查和诊断。
[0035] 请见图2，本发明提供一种传染病患者密切接触者的隐私保护追溯方法，包括以下步骤：
[0036] 步骤1：系统参数生成；
[0037] 步骤1.1：可信中心(TA)选择安全参数m(保证活动区域和时间能被完整地映射，可m×m设置为100)，生成用户匹配密钥(N1,N2,N3,N4)和服务器密钥M，其中N1,N2,N3,N4,M∈R 且都为可逆矩阵，即m行m列的矩阵且矩阵元素均为随机数；
[0038] 步骤1.2：TA选择n对可逆矩阵Ui,Vi(i＝1,2,…,n)作为通讯密钥，其中 Ui,Vi∈Rm×m；
[0039] 步骤1.3：TA选择安全加密hash函数 用于对活动区域中的所有重要活动地点进行映射，从而数值化成二元序列；选择安全加密hash 函数*
用于对当前时间进行映射；选择安全加密hash函数 H：{0，1}→{0，
m
1}，用于对用户进行验证，其中2m1+2m2＝m；公布 (H1,H2,H)；
[0040] 实体注册过程涉及图3；
[0041] 步骤2：实体注册；
[0042] 步骤2.1：用户USERi(i＝1,2,…,n)注册；
[0043] 步骤2.1.1：用户USERi(i＝1,2,…,n)发送注册请求；
[0044] 步骤2.1.2：TA从整数序列{1,2,…,n}中随机地选择一个数作为此用户的身份标识IDi，每次选择不重叠，即唯一标识；
[0045] 步骤2.1.3：TA计算密钥集合
[0046]
[0047]
[0048]
[0049] 其中·表示矩阵乘积；
[0050] 步骤2.1.4：TA向用户USERi返回 并不再保存这些密钥；
[0051] 步骤2.2：服务器CS注册；
[0052] 步骤2.2.1：服务器CS发送注册请求；
[0053] 步骤2.2.2：TA向服务器CS返回 并不再保存这些密钥；
[0054] 步骤3：个人活动轨迹加密及报告生成；
[0055] 步骤3.1：用户USERi将利用智能设备周期性地(如每到一个新的活动地点) 收集自己的位置信息Dj和当前时戳Tj；其中位置信息由等长的两部分组成：前半部分是当前活动地点的映射H1(Dj)，后半部分是前半部分的补码表示 即0变为1或者1变为0；时间信息同样分为等长的两部分：前半部分为时间的映射H2(Tj)，后半部分是前半部分的补码表示 用户USERi将得到活动信息 从而由m比特组成一个m阶的向量Xj，每个比特为向量的每个元素；
[0056] 步骤3.2：用户USERi生成活动报告；
[0057] 步骤3.2.1：对于Xj中每一个元素 用户USERi选择两对随机数 (p′j,k,p″j,k)和(q′j,k,q″j,k)，其中 使得Xj能够被拆分为一对列向量(p′j,p″j)和一对行向量(q′j,q″j)；
[0058] 步骤3.2 .2：用户USERi通过密钥 生成密文活动报告
[0059]
[0060]
[0061] 步骤3.3：用户USERi在报告后添加附加信息；
[0062] 步骤3.3.1：用户USERi计算签名信息 其中Tj是时间戳；
[0063] 步骤3.3.2：选择m对随机数(w′j,k,w″j,k)，使得 能够被拆分为一对列向量(w′j,w″j)；
[0064] 步骤3.3.3：用户USERi通过密钥 生成报告签名σj；
[0065]
[0066] 步骤3.4：用户USERi将个人活动轨迹报告(IDi,Yj,σj)发送给服务器CS。
[0067] 步骤4：社会活动网络图构造；
[0068] 步骤4.1：服务器CS收到活动轨迹报告(IDi,Yj,σj)之后，首先需要对报告进行身份验证，确保收到的报告是来自合法用户且该用户的轨迹信息未被篡改或伪造。通过密钥验证下面等式是否成立：
[0069]
[0070] 步骤4.2：服务器CS构造社会活动图；
[0071] 步骤4.2.1：每条通过身份验证的活动报告视为一个顶点(IDi,Yj)添加到图G 中，每个用户IDi的一系列活动按照提交先后进行连接视为单向边添加到图G中；
[0072] 步骤4.2.2：对于每个用户USERi的每条活动报告Yj，计算此报告与其他所有用户USERi′(i′≠i)的活动报告Yj′的相似性 即判断是否在同一时间里与其在同一地点相处(如同车次的同一节车厢)；
[0073]
[0074] 如果 则将顶点(IDi,Yj)和(IDi′,Yj′)进行双向连接，将此双向边添加到图G中；
[0075] 步骤4.2.3：遍历每个顶点，重复进行活动报告相似性判断，其中遍历过程跳过已经被双向连接的顶点；根据所有的顶点和边可以构造社会活动图G；
[0076] 步骤5：被感染者密切接触者追溯；
[0077] 步骤5.1：根据步骤3，对于已经被确诊感染的用户的每个活动地点生成活动报告并附带签名，最后形成患者活动轨迹报告；
[0078] 步骤5.2：将患者轨迹报告发送给服务器CS；
[0079] 步骤5.3：服务器CS将感染者的活动轨迹添加到图G中；
[0080] 步骤5.3.1：同步骤4.1，服务器CS对报告进行身份验证后将此活动报告添加到图G中；
[0081] 步骤5.3.2：对于图G中的每个顶点，服务器CS计算其与 的相似度，并将其中相似度结果为m的顶点与 进行双向连接；
[0082] 步骤5.4：服务器CS搜索所有密切接触者；
[0083] 步骤5.4.1：对于感染者活动轨迹对应的每个顶点vs，CS在图G中找到vs的所有存在双向连接的邻居顶点，并将这些顶点对应的ID添加到接触者集合中；
[0084] 步骤5.4.2：CS对集合中的元素进行去重操作，剩余的所有ID为密切接触者的标识；
[0085] 步骤5.4.3：CS对所有密切接触者发送提醒以便后续进行检查和诊断。
[0086] 本发明基于KNN加密搜索方案实现了一种传染病患者密切接触者的隐私保护搜索方案，该方案实现了抗外部攻击和内部攻击。
[0087] 应当理解的是，上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。
