东北大学学报:自然科学版  2019, Vol. 40 Issue (4): 461-466  
0

引用本文 [复制中英文]

秦诗悦, 周福才, 柳璐. 基于后缀树的基因数据可搜索加密方法[J]. 东北大学学报:自然科学版, 2019, 40(4): 461-466.
[复制中文]
QIN Shi-yue, ZHOU Fu-cai, LIU Lu. Searchable Encryption Scheme of Genomic Data Based on Suffix Tree[J]. Journal of Northeastern University Nature Science, 2019, 40(4): 461-466. DOI: 10.12068/j.issn.1005-3026.2019.04.002.
[复制英文]

基金项目

国家自然科学基金资助项目(61772127, 61872069);中央高校基本科研业务费专项资金资助项目(N151704002)

作者简介

秦诗悦(1994-)，女，辽宁沈阳人，东北大学博士研究生;
周福才(1964-)，男，吉林长春人，东北大学教授，博士生导师。

文章历史

收稿日期：2018-02-28
Contents              Abstract              Full text              Figures/Tables              PDF
基于后缀树的基因数据可搜索加密方法
秦诗悦 1, 周福才 2, 柳璐 2     
1. 东北大学 计算机科学与工程学院, 辽宁 沈阳 110169;
 2. 东北大学 软件学院, 辽宁 沈阳 110169
收稿日期：2018-02-28
基金项目：国家自然科学基金资助项目(61772127, 61872069);中央高校基本科研业务费专项资金资助项目(N151704002)。
作者简介：秦诗悦(1994-)，女，辽宁沈阳人，东北大学博士研究生;
周福才(1964-)，男，吉林长春人，东北大学教授，博士生导师。
摘要：为保障用户免遭侵犯隐私的风险, 提出了一种特别支持基因数据的可搜索加密方法.针对目前密文搜索方案大多数仅支持通过关键字进行搜索, 而无法用于不含关键字的基因数据的问题, 利用后缀树和伪随机函数等密码学原语构建安全索引, 实现对密文基因数据的任意子字符串搜索.安全性证明该方法满足动态自适应安全, 利用理论分析和真实数据对效率进行测评.该方法可以对基因数据进行高效安全的任意子字符串搜索, 保护数据完整性和隐私性, 在个性化医疗大众化的环境下具备广阔的应用前景.
关键词：基因数据    后缀树    可搜索加密    子字符串搜索    现代医疗    
Searchable Encryption Scheme of Genomic Data Based on Suffix Tree
QIN Shi-yue 1, ZHOU Fu-cai 2, LIU Lu 2     
1. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China;
 2. School of Software, Northeastern University, Shenyang 110169, China
Corresponding author: ZHOU Fu-cai, E-mail: fczhou@mail.neu.edu.cn
Abstract: A searchable encryption scheme that specifically supports genetic data was proposed to protect users from privacy risks. The existing searchable encryption schemes only support keywords search, they cannot be applied to genetic data without keywords. So, a security index using cryptographic primitives such as suffix trees and pseudo-random functions was constructed to implement arbitrary substring searches for ciphertext genomic data. The safety proof indicated that the method satisfies the dynamic adaptive security, and the efficiency is evaluated by both theoretical analysis and real data. This scheme can perform efficient and safe arbitrary substring search on genomic data, protect data integrity and privacy and has broad application prospects in the environment of personalized medical popularization.
Key words: genomic data    suffix tree    searchable encryption    substring search    modern medicine    

随着人类基因组测序成本的下降, 个性化医疗将逐渐成为患者的首选.通过对患者进行基因测试获得患者的基因数据, 选择更具针对性的治疗方案.通过搜索患者的基因序列中是否存在突变基因, 计算基于基因数据的子字符串匹配问题, 决定是否需要采取早期干预措施来预防遗传疾病发生.基因数据的特性之一是其序列长度十分庞大.为了对这样的海量数据进行存储和计算, 许多基因医疗机构选择外包给云服务器或者第三方代理服务器.然而, 基因数据作为个人可标识信息, 患者将其提供给不可信第三方就可能会把自己置身于隐私侵犯和数据泄露的危险之中[1].

为了保证基因数据的隐私性, 以及防止数据泄露带来的隐私威胁问题, 在数据外包之前进行加密是有效技术手段.同时要求一个不可信实体(利用不可信服务器)能够完成对密文基因数据的子字符串搜索工作.传统的可搜索加密[2-3]通过预设关键字构造索引实现密文搜索, 但在基因数据中无法给出明确的关键字, 同时待搜索目标基因数据可能重复性较高, 因此无法直接应用.

Lu等[4]提出一个全基因组关联研究的安全外包方案, 该方案根据已知的基因突变和疾病间关联计算加密的统计数值作健康风险评估.Chase等[5]提出的方案会泄露搜索模式, 仅实现部分隐私保护.Ayday等[6]通过保序加密构建保护隐私的DNA检索方案.混淆电路[7]和差分隐私技术[8-9]同样可以用来保护基因数据, 但是噪音问题会干扰临床医生给出正确治疗方案, 同时影响方案效率.Wang等[10]利用属性加密解决序列匹配问题, 但无法获得具体目标基因位置信息.

本文针对组成元素简单、重复部分多且数据量大的基因数据, 提出一个基于后缀树的基因数据可搜索加密方法.通过构建具有后缀树结构的、支持子字符串搜索的安全索引, 利用伪随机函数等保证数据机密性与隐私性, 实现一个能在任何基因序列中搜索任意基因片段, 并返回其所有位置信息的可搜索加密方案.

1 预备知识 1.1 后缀树

后缀树(suffix tree)是一种可快速实现多种重要字符串操作的数据结构[11].一个长度为n的字符串s=s1s2…sn的后缀树是一棵包含根节点的树, 由节点和边组成.具备以下属性:

1) 每条边代表一个非空的s子字符串.

2) 若非叶子节点只有1个孩子节点, 去掉此孩子节点进行压缩.后缀树最多为2n个节点.

3) 从根到叶子节点i的路径与s从i位置开始的后缀对应, 即每条路径唯一代表s的一个后缀.

4) 同一节点下每条边以不同的字符开头[12].

后缀树的子字符串搜索速度较快, 对于长度为n字符串, 最多花费O(n)时间进行匹配.

1.2 伪随机函数

对长字符串计算伪随机函数, 需要先对长字符串做Hash处理, 使之变成定长字符, 然后对此Hash值计算伪随机函数.如果Hash具有通用抗碰撞性, 则该伪随机函数的伪随机性就依然成立.

设有限域集D, R, U, B, 其中D, U是定义域, R, B是结果集.λ, μ为密钥长度, 存在伪随机函数F: {0, 1}λ×D→R和通用抗碰撞Hash函数H: {0, 1}μ×U→B, 输入长字符串x, 则函数F(H(x)): {0, 1}λ+μ×U→R是一个合法伪随机函数.

2 模型与定义

本文考虑用户User与不可信服务器Ser进行交互, 对密文基因数据进行子字符串搜索, 确定某段特定标记序列是否出现及出现的位置.给定基因数据字符串s和一个待搜索字符串p, 找出p作为s子字符串出现的所有情况.

2.1 形式化定义

基于后缀树的基因数据可搜索加密方法主要由5个多项式时间算法/协议组成, 形式化定义为

SDNAsearch=(GenKey, STree, EncInd, GenTok, Search).

各算法具体描述如下:

1) K←GenKey(1λ):密钥生成算法, 输入安全参数λ, 输出所需密钥组K.

2) T←STree(s):后缀树构建算法, 输入明文字符串s, 输出s的后缀树结构T.

3) SI←EncInd(K, T, s, ε):安全索引构建算法, 输入密钥K、明文字符串s、其后缀树结构T及加密方案ε；输出安全索引SI=(D, C, L).其中, D为加密字典结构, C为加密文件信息, L为加密数组信息, SI上传至服务器保存.

4) Tok←GenTok(K, p, ε):令牌生成算法, 输入待搜索子字符串p, 令牌所需密钥K, 构建安全索引所用加密方案ε, 输出为令牌Tok.

5) User:Rst←Search(User:Tok; Ser:SI):交互搜索协议，用户向服务器发送令牌Tok, 服务器根据SI进行搜索, 交互结束用户输出结果Rst.

2.2 安全性定义

假设服务器Ser为一个半诚信多项式时间敌手A, 具有自适应性, 即A可以任意选择信息加密并执行搜索协议进行质询, 并可以根据已得质询结果发起新质询.定义多项式时间模拟器S生成随机字符串.定义2个泄漏函数L1, L2:L1(SI)为加密过程的泄露函数, 是安全索引SI的泄漏信息; L2(SI, p1, …, pj)为搜索过程中的泄露函数, 是前j次搜索的泄漏信息, pi为第i次搜索.

构建现实实验RealA, U(λ):敌手A和用户U利用真实加密方法进行交互.对A选择的字符串s, U生成安全索引SI并发送给A.A根据SI进行多次自适应质询, 即待搜索字符串p1, …, pt(t为多项式级).每次质询pi后, U利用Tok算法计算令牌Toki并返回给A.

构建理想实验IdealA, S(λ):敌手A和有状态的模拟器S进行理想交互.对于A选择的字符串s, S以泄露函数L1, L2作为输入生成随机结构SI′发送给A, A根据SI′自适应进行多次质询p1, …, pt(t为多项式级).每次质询pi后, S利用生成随机字符串vi, 返回给A.

若在多项式时间内, 敌手A以可忽略的概率区分实验输出结果, 则称本文构建的方法在泄露函数L1, L2下是满足动态自适应安全的.

3 详细描述 3.1 符号说明

选择安全参数λ, 满足密钥不可区分性及IND-CPA安全的对称加密算法ε=(Gen, Enc, Dec), 伪随机函数F:{0, 1}λ×{0, 1}*→{0, 1}λ, 伪随机置换P:{0, 1}λ×[n]→[n], P′:{0, 1}λ×[d]→[d], π:{0, 1}λ×[m]→[m]和π′:{0, 1}λ×[num]→[num].定义基因数据字符集Σ(例如:{A, T, G, C}), 集合所含字符个数|Σ|=d, 各符号定义如表 1所示.

表 1 符号说明 Table 1 Symbols description
3.2 算法描述

基于后缀树的基因数据可搜索加密方法的详细算法及协议描述如下.

1) K←GenKey(1λ):密钥生成算法由User执行.随机生成{0, 1}λ7个不同比特串组成密钥组K.KD, KC, KL分别是字典结构D、密文数组C及叶子数组L的密钥；K1, K2用于处理字典内数据以及令牌Tok；K3, K4用于伪随机置换.输出用户密钥K.

2) T←STree(s):后缀树构建算法由User执行.首先, 在字符串s=s1…sn∈Σn末尾添加特殊字符′＄′, 避免后缀隐藏问题.构建一棵空树, 每插入一个字符si, 利用后缀指针SuffixLink进行树结构变换, 生成后缀树T.

算法伪代码如下:

表

3) SI←EncInd(K, T, s, ε):安全索引构建算法由User执行.根据s=s1…sn∈Σn的后缀树T构建安全索引SI=(D, C, L), 其中D是字典, C是密文数组, L是叶子数组.将安全索引SI上传至Ser.

① 字典D:以字符串s=″agaggtc″为例构建初始字典D如表 2所示.然而, 其存在中断搜索的错误情况.因此, 利用=p(par(u))‖ω代替p(u)构建字典D, ω是par(u)与u连接边上的第一个字符.改进字典D如表 3所示.

表 2 初始字典示例 Table 2 Example of initial dictionary
表 3 改进字典示例 Table 3 Example of improved dictionary

在字典D=(key, value)中, key存储后缀树T的每个节点入口, 即f1(u)=F(K1, ).value值由搜索结构和密文结构组成.对每个节点u的每个孩子节点child(u, i)计算f2, i(u)=F(K2, (child(u, i))).若de(u) < d, 添加随机项{0, 1}λ进行补充, 并利用伪随机置换P′进行顺序随机化，得到搜索结构f2, P′(1)(u), …, f2, P′(d)(u).利用KD加密得到密文结构, Xu=ε.Enc(KD, (indu, leftleafu, numu, lenu, f1(u), f2, P′(1)(u), …, f2, P′(d)(u))), 则value=(f2, P′(1)(u), …, f2, P′(d)(u), Xu).同时为保障字典D的安全性, 除了T现存的N个节点入口, 另外构建2n-N个虚拟入口, 每个虚拟入口利用随机项f1, f2, 1, …, 填充, 即:key=f1, value=(f2, 1, …, f2, d, ε.Enc(KD, 0)).

② 密文数组C:利用密钥KC和伪随机置换PK3:[n]→[n]对字符串s进行确定性加密.保证密文唯一, 生成C[PK3(i)]=ε.Enc(KC, si‖i).

③ 叶子数组L:为返回p在s中的全部位置指针, 构建叶子数组L.利用密钥KL和伪随机置换PK4:[n]→[n], 生成L[PK4(i)]=ε.Enc(KL, indleafi‖i).

4) Tok←GenTok(K, p, ε):令牌生成算法由User执行.由p=p1，…，pm计算Tok=T1, …, Tm, f0(∈), f0(∈)是后缀树根节点的密文, 即字典D入口, Ti=ε.EncF(K1, p[1…i])(F(K2, p[1… i])).

5) User:Rst←Search(User:Tok; Ser:SI):交互搜索协议由User和Ser进行.User发送Tok给Ser.Ser根据f1(∈)找到字典D中相等的入口key值, 并利用对应value值中的搜索结构对Ti(i=1, …, m)进行解析, 即计算Y=ε.Dec(f2, j, Ti)(j=1, …, d).若Y有效且能与字典D的某个key值匹配, 则记录其对应value值的密文结构X, 并利用该value值中的搜索结构解析下一个令牌Ti+1；若Y无效或者没有key值与有效Y相等, 则继续利用同一个搜索结构解析Ti+1.在所有令牌解析完成后，对字典的搜索结束.Ser发送最终记录的密文结构X至User.

如果User解密W=ε.Dec(KD, X)得到有效明文, 首先检验f1=F(K1, p[1…i])是否成立, 并判断在a=i+1, …, m且b=1, …, d时, ε.Dec(f2, b, Ta)=⊥是否成立.若皆成立, 则p[1…i]是最长匹配前缀, 计算xπ(i)=P(K3, ind+i-1)并发送给Ser, 否则, 搜索失败.Ser根据(x1, …, xm)搜索C, 返回(C1, …, Cm).如果User解密Y=ε.Dec(KC, Cπ1(i))得到有效值Y =(p′i‖j), 判断j=ind+i-1且p′1…p′m=p是否成立；若成立, 计算yπ′(i)=PK4(leftleaf+i-1)发送给Ser, 否则, 搜索失败.Ser根据(y1, …, ynum)搜索L, 返回L[y1], …, L[ynum].User若解密Rst=ε.Dec(KL, L[yi])得到⊥, 或者Rst=(ai, j)中存在j≠leftleaf+i-1, 则代表搜索失败；否则, 结果Rst={a1, …，anum}.

4 安全性证明与效率分析 4.1 安全性证明

构建理想实验具体过程如下:

根据安全性定义, 预证本方法在泄露函数L1, L2下满足动态自适应安全, 应对任意多项式敌手A, 存在一个多项式模拟器S, 满足

|Pr[RealA, U(1λ)=1]-Pr[IdealA, S(1λ)=1]|≤λ.

其中, λ为可忽略函数.称基于后缀树的基因数据可搜索加密方法在泄露函数L1, L2下是满足动态自适应安全的.

证明:

1) 在加密过程中, S可以根据L1构建模拟结构D′，生成2n条定长随机数据模拟D.对任意多项式时间敌手A满足

|Pr[1←A(D, n)]-Pr[1←A(D′, n)]|≤λ.

假设λ不可忽略, 则敌手A可以区分D和D′, 即能以不可忽略概率区分随机数和伪随机函数, 违背伪随机函数的伪随机性.因此, 概率λ可忽略.

2) 在加密过程中, 满足IND-CPA安全的真实加密方法ε生成密文数组C[i]=ε.Enc(KC, si‖i).S构建游戏H0, …, Hn:若i′>i, Ci′=ε.Enc(KC, (σ, 0))(σ是随机数), 否则Ci′=ε.Enc(KC, (si′, i′)).要求敌手A区分Ci是由(σ, 0)还是(si′, i′)计算得到, 则对于所有多项式时间敌手A, 存在不等式:

假设λ不可忽略, 表示敌手A可以以不可忽略概率区分ε.Enc(KC, (σ, 0))和ε.Enc(KC, si‖i), 则打破IND-CPA安全, 产生悖论.因此, 概率λ可忽略.

3) 在搜索过程中, 假设两次查询pj, pj′和令牌Ti, j, Ti, j′, 存在相同不匹配前缀pj[1…i]=pj′[1…i].S构建状态表Ψ1模拟字典D.Ψ1=(i, j, k)代表字典D的入口k是第i次搜索访问第j个节点.定义pmax×(smax+1)个游戏Hi, j, 其中pmax为最大查询次数, smax为最长待搜索字符串长度, i∈{1, …, smax}且j∈{1, …, pmax}.当Hi, j满足pj[1…i]≠pj′[1…i], 随机选择r, 令Tj′, i←ε.Enc(r, Ψ1(pj′[1…i])).若pj为匹配前缀, 则重选r′替换Tj′, i为Tj, i；否则, 根据L2返回Tj′, i=QP(s, p1, …pj)[j′], 如果D(Ψ1(pj[1…i]))成立, 令Tj′, i=Tj, i.如果真实ε具有密钥不可区分性, 则对任意多项式时间敌手A满足不等式:

假设λ是不可忽略的, 敌手A能够以不可忽略概率区分Ti, j, Ti, j′是由匹配前缀还是由不匹配前缀产生的, 即敌手A可以打破密钥不可区分性, 产生悖论.因此概率λ是可忽略的.

综合实验所述, 可得|Pr[RealA, U}(λ)=1]-Pr[IdealA, S(λ)=1]|≤λ, 即真实实验RealA, U(λ)与理想实验IdealA, S(λ)的输出是不可区分的.因此, 如果ε是满足密钥不可区分性以及IND-CPA安全的对称加密算法, F和P分别是伪随机函数和伪随机置换, 则本文方法在泄漏函数L1, L2下是满足动态自适应安全的.

4.2 效率分析

本方法使用UKK算法进行后缀树快速构建, 时间复杂度O(n).调用Openssl库中的随机数生成算法构建密钥组K, 时间复杂度O(1).利用AES_CBC加密算法以及SHA-128伪随机函数构建安全索引.实验数据集来源为NCBI数据库[13].

1) 加密阶段:安全索引构建耗时如图 1所示, 构建安全索引的耗时会随着基因长度d增加而增加.在d较大时, 其安全索引构建所需要添加的虚拟孩子节点和虚拟字典条目也会增多, 总共需要O(d2)次伪随机函数计算、伪随机序列计算和加密计算.由于基因数据存在稳定性, 因此, 对其进行一次索引构建即可支持后续的多次搜索, 所以本次测试结果可以考虑应用于实际.

图 1 基因数据长度对安全索引构建耗时的影响 Fig.1 Effect of genomic data length on secure index constructing time

2) 搜索阶段:待搜索字符串长度对搜索时间的影响如图 2所示.待搜索字符串长度m影响构建搜索令牌数量, 而令牌数量决定搜索字典时执行解密的次数, 搜索D和C的复杂度分别为O(md)和O(m)个解密操作, L的搜索次数保持为O(1).执行一次搜索需要用户和服务器之间进行3次交互.

图 2 子字符串长度对搜索耗时的影响 Fig.2 Effect of substring length on searching time

综上, 根据基因数据的“一次构建, 多次搜索”的特殊需求, 本文提出的基于后缀树的基因数据可搜索加密方法适合现代医疗场景.

5 结论

1) 针对多数密文搜索方案仅支持关键字搜索的问题, 本文提出一种基于后缀树的基因数据可搜索加密方法.在不可信环境下, 对不具有关键字信息且重复性较大的基因数据的可搜索加密, 实现基于密文的子字符串搜索并返回其具体位置信息.

2) 利用后缀树的结构特点, 结合伪随机函数、哈希函数等密码学原语进行高效安全的方案构建, 并给出相关形式化描述和安全性定义.

3) 安全性实验和性能实验结果表明，本文提出的基于后缀树的基因数据可搜索加密方法在个性化医疗逐渐大众化的环境下具备广阔的应用前景.

参考文献
[1]
Erlich Y, Narayanan A. Routes for breaching and protecting genetic privacy[J]. Nature Reviews Genetics, 2014, 15(6): 409–421. DOI:10.1038/nrg3723
[2]
Cao N, Wang C, Li M, et al.Privacy-preserving multi-keyword ranked search over encrypted cloud data[C]//IEEE Conference on Computer Communications.Piscataway: IEEE, 2011: 829-837. https://www.researchgate.net/publication/221241718_Privacy-Preserving_Multi-Keyword_Ranked_Search_over_Encrypted_Cloud_Data?_sg=DlWAb25SLM_Tezx3ygb2vls2QxH0HH4dXu75iDPzaOxXAWdgJks6NZ1tAhT5oS88wv3Vi6SgH8VsO6I0Y_NpGw
[3]
Wang B, Yu S, Lou W, et al.Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud[C]//IEEE Conference on Computer Communications.Piscataway: IEEE, 2014: 2112-2120.
[4]
Lu W, Yamada Y, Sakuma J.Efficient secure outsourcing of genome-wide association studies[C]//2015 IEEE Security and Privacy Workshops.Los Alamitos: IEEE, 2015: 3-6. https://www.researchgate.net/publication/308604836_Efficient_Secure_Outsourcing_of_Genome-Wide_Association_Studies?ev=auth_pub
[5]
Chase M, Shen E. Substring searchable symmetric encryption[J]. Proceedings on Privacy Enhancing Technologies, 2015, 2015(2): 263–281.
[6]
Ayday E, Raisaro J L, Hengartner U, et al.Privacy preserving processing of raw genomic data[C]//International Workshop on Data Privacy Management and Autonomous Spontaneous Security.New York : Springer-Verlag, 2013: 133-147. https://link.springer.com/chapter/10.1007%2F978-3-642-54568-9_9
[7]
Riazi M S, Dantu N K R, Gattu L N V, et al.GenMatch: secure DNA compatibility testing[C]//IEEE International Symposium on Hardware-Oriented Security and Trust(HOST).Piscataway: IEEE, 2016: 248-253. https://www.researchgate.net/publication/304457080_GenMatch_Secure_DNA_compatibility_testing?ev=auth_pub
[8]
Simmons S, Berger B. Realizing privacy preserving genome-wide association studies[J]. Bioinformatics, 2016, 32(9): 1293–1300. DOI:10.1093/bioinformatics/btw009
[9]
Wang M, Ji Z, Wang S, et al. Mechanisms to protect the privacy of families when using the transmission disequilibrium test in genome-wide association studies[J]. Bioinformatics, 2017, 33(23): 3716–3725. DOI:10.1093/bioinformatics/btx470
[10]
Wang B, Song W, Lou W, et al.Privacy-preserving pattern matching over encrypted genetic data in cloud computing[C]//IEEE Conference on Computer Communications.Piscataway : IEEE, 2017: 1-9. https://www.researchgate.net/publication/320252686_Privacy-preserving_pattern_matching_over_encrypted_genetic_data_in_cloud_computing
[11]
Weiner P.Linear pattern matching algorithms[C]//14th Annual Symposium on Switching Automata Theory.New York : IEEE, 1973: 1-11.
[12]
McCreight E M. A space-economical suffix tree construction algorithm[J]. Journal of the ACM, 1976, 23(2): 262–272. DOI:10.1145/321941.321946
[13]
U.S.National Library of Medicine.National center for biotechnology information(NCBI): GenBank flat file release 229.0[DB/OL].[2018-11-15].https://www.ncbi.nlm.nih.gov/genbank/.