Searchable Encryption Scheme of Genomic Data Based on Suffix Tree

doi:10.12068/j.issn.1005-3026.2019.04.002

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

CLC Number:

TP309

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.

References

[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.