基于后缀树的基因数据可搜索加密方法

doi:10.12068/j.issn.1005-3026.2019.04.002

东北大学学报:自然科学版 ›› 2019, Vol. 40 ›› Issue (4): 461-466.DOI: 10.12068/j.issn.1005-3026.2019.04.002

基于后缀树的基因数据可搜索加密方法

秦诗悦¹，周福才²，柳璐²

(1. 东北大学计算机科学与工程学院，辽宁沈阳110169; 2. 东北大学软件学院，辽宁沈阳110169)

收稿日期:2018-02-28 修回日期:2018-02-28 出版日期:2019-04-15 发布日期:2019-04-26
通讯作者: 秦诗悦
作者简介:秦诗悦(1994-)，女，辽宁沈阳人，东北大学博士研究生；周福才(1964-)，男，吉林长春人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(61772127，61872069)；中央高校基本科研业务费专项资金资助项目(N151704002).

Searchable Encryption Scheme of Genomic Data Based on Suffix Tree

QIN Shi-yue¹， ZHOU Fu-cai²， LIU Lu²

1. School of Computer Science & Engineering， Northeastern University， Shenyang 110169， China; 2. School of Software， Northeastern University， Shenyang 110169， China.

Received:2018-02-28 Revised:2018-02-28 Online:2019-04-15 Published:2019-04-26
Contact: ZHOU Fu-cai
About author:-
Supported by:
-

摘要/Abstract

摘要： 为保障用户免遭侵犯隐私的风险，提出了一种特别支持基因数据的可搜索加密方法.针对目前密文搜索方案大多数仅支持通过关键字进行搜索，而无法用于不含关键字的基因数据的问题，利用后缀树和伪随机函数等密码学原语构建安全索引，实现对密文基因数据的任意子字符串搜索.安全性证明该方法满足动态自适应安全，利用理论分析和真实数据对效率进行测评.该方法可以对基因数据进行高效安全的任意子字符串搜索，保护数据完整性和隐私性，在个性化医疗大众化的环境下具备广阔的应用前景.

关键词: 基因数据, 后缀树, 可搜索加密, 子字符串搜索, 现代医疗

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

中图分类号:

TP309

秦诗悦，周福才，柳璐. 基于后缀树的基因数据可搜索加密方法[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 Natural Science, 2019, 40(4): 461-466.

参考文献

[1]Erlich Y，Narayanan A.Routes for breaching and protecting genetic privacy［J］.Nature Reviews Genetics，2014，15(6):409-421.
[2]Cao N，Wang C，Li M，et al.Privacy-preserving multi-keyword ranked search over encrypted cloud data［C］//IEEEConference on Computer Communications.Piscataway:IEEE，2011:829-837.
[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.
[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.
[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.
[8]Simmons S，Berger B.Realizing privacy preserving genome-wide association studies［J］.Bioinformatics，2016，32(9):1293-1300.
[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.
[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.
[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.
[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/.(上接第460页)
[2]Govindana K，Fattahib M，Keyvanshokooh E.Supply chain network design under uncertainty:a comprehensive review and future research directions［J］.European Journal of Operational Research，2017，263(1):108-141.
[3]Li T，Ma J H.Complexity analysis of the dual-channel supply chain model with delay decision［J］.Nonlinear Dynamics，2014，78(4):2617-2626.
[4]Sivadasan S，Eftathiou J，Calinescu A，et al.Advances on measuring the operational complexity of supplier-customer systems［J］.European Journal of Operational Research，2006，171:208-226.
[5]邱菀华.管理决策与应用熵学［M］.北京:机械工业出版社，2002.(Qiu Wan-hua.The decision-making of management and the application of entropy［M］.Beijing:China Machine Press，2002.)
[6]邱若臻，苑红涛，冯俏.有限需求信息下基于最大熵原理的风险厌恶库存模型［J］.东北大学学报(自然科学版)，2016，37(10):1512-1516.(Qiu Ruo-zhen，Yuan Hong-tao，Feng Qiao.Risk aversion inventory model based on maximum entropy approach under limited demand information ［J］.Journal of Northeastern University(Natural Science)，2016， 37(10):1512-1516.)
[7]Perea-López E，Grossmann I E，Ydstie B E，et al.Dynamic modeling and decentralized control of supply chains［J］.Industrial Engineering Chemistry Research，2001，40(15):3369-3383.
[8]Raj T S，Lakshminarayanan S.Entropy-based optimization of decentralized supply-chain networks［J］.Industrial Engineering Chemistry Research，2010，49(7):3250-3261.
[9]李国家，汪定伟.供应链中控制多级存储的射频辨识Push/Pull混合策略设计与仿真［J］.控制理论与应用，2014，31(10):1302-1309.(Li Guo-jia，Wang Ding-wei.Design and simulation of radio frequency identification-enabled hybrid Push/Pull strategy for multi-echelon inventory of supply chain ［J］.Control Theory & Applications，2014，31(10):1302-1309.)
[10]Fu D F，Ionescu C M， Aghezzaf E H，et al.Decentralized and centralized model predictive control to reduce the Bullwhip effect in supply chain management［J］.Computers & Industrial Engineering，2014，73:21-31.
[11]Xu H，Rong G，Feng Y P，et al.Control variance amplification in linear time invariant decentralized supply chains:a minimum variance control perspective［J］.Industrial Engineering Chemistry Research，2010，49(18):8644-8656.
[12]Jung J Y，Blaua G，Pekny J F，et al.A simulation based optimization approach to supply chain management under demand uncertainty［J］.Computers and Chemical Engineering，2004，28(10):2087-2106.
[13]Mele F D，Guillén G，Espua A，et al.A simulation-based optimization framework for parameter optimization of supply-chain networks［J］.Industrial Engineering Chemistry Research，2006，45:3133-3148.

基于后缀树的基因数据可搜索加密方法

Searchable Encryption Scheme of Genomic Data Based on Suffix Tree

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	葛悦，李宇溪，周福才，张鑫月. 具有前向安全特性的密态图像搜索方案[J]. 东北大学学报（自然科学版）, 2021, 42(8): 1079-1085.
[2]	厉鹏，周福才，张帅. 基于BSSEVD的可搜索加密方案原型系统设计与实现[J]. 东北大学学报:自然科学版, 2020, 41(9): 1244-1250.
[3]	贾强，张帅，周福才. 一种面向密文大型数据集的可搜索加密方案[J]. 东北大学学报:自然科学版, 2019, 40(7): 913-919.
[4]	周福才，张宗烨，王恺璇，李宇溪. 基于Paillier和PSI的多关键字可搜索加密方案[J]. 东北大学学报:自然科学版, 2019, 40(3): 321-326.
[5]	韩东红;王国仁;乔百友. XML路径表达式中公共子查询的优化技术[J]. 东北大学学报(自然科学版), 2005, 26(6): 535-537.
[6]	乔百友;葛健;王国仁;韩东红. 并行后缀树的构造及查询算法[J]. 东北大学学报(自然科学版), 2004, 25(3): 231-234.