基于同態(tài)加密的生物數(shù)據(jù)版本管理

楊明朗　滿毅　劉寧寧　張奕欣　邢瀟

摘? ?要：隨著生物技術(shù)的發(fā)展和研究的深入，生物數(shù)據(jù)也逐步完備。對于同一物種的基因組測序，也在原始版本的基礎(chǔ)上不斷完善。當(dāng)前主流的存儲方式為將多個(gè)測序版本完整保存，由于生物數(shù)據(jù)本身體積較大，對相似的大數(shù)據(jù)存儲大量重復(fù)部分是不劃算的。同時(shí)，由于這些數(shù)據(jù)經(jīng)常涉及到較高的隱私性，在公開情景執(zhí)行修改和分析時(shí)，需要有一定的手段對其進(jìn)行保護(hù)。文章設(shè)計(jì)了數(shù)據(jù)的差異文件版本管理方案，并結(jié)合同態(tài)加密技術(shù)，實(shí)現(xiàn)基因組數(shù)據(jù)的輕便存儲和安全修改，并通過對短 DNA 序列的分析實(shí)現(xiàn)了驗(yàn)證。

關(guān)鍵詞：版本管理;同態(tài)加密;生物信息學(xué);數(shù)據(jù)隱私;同態(tài)連接

中圖分類號：TP393? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A

Design of biological data version management scheme based on homomorphic encryption

Yang Minglang1， Man Yi1， Liu Ningning2， Zhang Yixin3， Xing Xiao3

[1.Beijing Univeristy of Posts and Telecommunications， Beijing 100876;

2.Neusoft Corporation（Beijing） Co.，Ltd.， Beijing 100193;

3.National Computer Network Emergency Response Technical Team/Coordination Center of China， Beijing 100094]

Abstract： With the development of biotechnology and the deepening of research， biological data is gradually completed. Genome sequencing of the same species is also improving on the original basis. The current mainstream storage method is to save multiple sequencing versions completely. Due to the large volume of biological data itself， it is not cost-effective to store a large number of similar big data. At the same time， as these data often involve high privacy， certain means are needed to protect them when performing modification and analysis in public scenarios. In this paper， we proposed a version management scheme for differential files of data. And we combined homomorphic encryption technology to realize portable storage and secure modification of genomic data， which is verified by analyzing short DNA sequences.

Key words： version management; homomorphic encryption; bioinformatics; data privacy; homomorphic concat

1 引言

近年來，隨著生物科學(xué)技術(shù)的迅猛發(fā)展，生物數(shù)據(jù)資源急劇膨脹，大量多樣化的生物學(xué)數(shù)據(jù)資料產(chǎn)生，同時(shí)原有基因組數(shù)據(jù)的未測量部分也隨著研究深入和技術(shù)進(jìn)步逐步測出，已測量部分也存在一定修正，進(jìn)而不斷產(chǎn)生新的版本。同時(shí)，當(dāng)前國際主流的生物數(shù)據(jù)網(wǎng)站，已經(jīng)可以公開獲取人類基因組數(shù)據(jù)。當(dāng)前，基因組數(shù)據(jù)使用方式為完整存儲數(shù)據(jù)的多重版本，對隱私性強(qiáng)的數(shù)據(jù)采取去除部分信息的匿名化方式。

不同生物網(wǎng)站存儲的數(shù)據(jù)可以進(jìn)行版本對應(yīng)。以Ensembl基因組數(shù)據(jù)庫為例。該數(shù)據(jù)庫存儲的人類基因組數(shù)據(jù)，除當(dāng)前主流的版本 GRCh38外，網(wǎng)站也存儲了諸多歷史版本，如release-76到release-83對應(yīng) GRCh38，從release-55到release-75對應(yīng)GRCh37，以及更早期的一些版本。每一版本中也包含 patch 文件，記錄了一些小的修改。

另一方面，即使是匿名的基因組數(shù)據(jù)也會泄露參與者的重要信息，部分個(gè)人信息仍能從序列中被恢復(fù)出來。研究[1] [2] [3]等表明，基因中包含的可鑒別的個(gè)人信息不能被完全消除，攻擊者甚至能從很小的基因片段中提取出個(gè)人序列所特有的特征。研究[4]指出，個(gè)人基因組能夠恢復(fù)出所屬者的姓氏;研究[5]提出了一種REIDIT算法，可以將基因組數(shù)據(jù)與公開記錄中的指定個(gè)人聯(lián)系起來。因此，對于基因組數(shù)據(jù)的保護(hù)不是簡單匿名即可解決的。

為了解決隱私性這一問題，密碼學(xué)提供了一種加密解決方案——同態(tài)加密[6]。同態(tài)加密是一種對數(shù)據(jù)進(jìn)行加密的技術(shù)，其加密方式是任何人都可以對其進(jìn)行計(jì)算，而不需要訪問加密或解密密鑰，并且計(jì)算結(jié)果以加密的形式獲得。目前，已有利用同態(tài)加密分析基因組數(shù)據(jù)的相關(guān)研究，主要方向是進(jìn)行同態(tài)加密生物數(shù)據(jù)上的數(shù)據(jù)分析，如進(jìn)行數(shù)據(jù)挖掘、序列比對、計(jì)算編輯距離等。在[7]中，提出使用Paillier加密系統(tǒng)進(jìn)行實(shí)驗(yàn)分析，可以在不違反基因組序列隱私的情況下支持?jǐn)?shù)據(jù)挖掘。[8]在安全計(jì)算最小距離方面得到了進(jìn)展，包括漢明距離和歐氏距離。這些研究主要適用于具體的分析比對場景，并不適用于生物數(shù)據(jù)網(wǎng)站面對的場景。

基于以上討論，生物數(shù)據(jù)兼具著強(qiáng)隱私性和版本更新的兩種特征，現(xiàn)有的方法并不能很好地滿足數(shù)據(jù)更新和隱私保護(hù)的需求。需要有更強(qiáng)力、有效的方式對這些敏感數(shù)據(jù)進(jìn)行管理和保護(hù)。本文正是面向上述背景，提出了一種基于同態(tài)加密的基因數(shù)據(jù)多版本存儲控制解決方案。本文提出不再存儲不同版本的完整文件，而是存儲差異文件，并利用同態(tài)加密位加密同態(tài)的特性，在明文上進(jìn)行如增刪改的操作，在密文形式上等價(jià)實(shí)現(xiàn)。實(shí)現(xiàn)同態(tài)加密上差異文件與原始文件的合并操作。這樣，就減少了數(shù)據(jù)存儲量并增強(qiáng)了操作數(shù)據(jù)的安全性。

2 版本管理方案提出與分析

如圖1所示描述了方案的總體設(shè)計(jì)和執(zhí)行過程。

方案整體包括三個(gè)組成部分，主要為數(shù)據(jù)庫服務(wù)器、數(shù)據(jù)提供者和數(shù)據(jù)使用者。三者的主要職能和操作如下。

（1）數(shù)據(jù)庫服務(wù)器

存儲同態(tài)加密形式下的多個(gè)基因組數(shù)據(jù)文件及差異文件。

（2）數(shù)據(jù)提供者

當(dāng)產(chǎn)生新的測序文件，根據(jù)其版本類型進(jìn)行相應(yīng)操作，上傳至服務(wù)器。當(dāng)要提交的數(shù)據(jù)要作為標(biāo)準(zhǔn)文件時(shí)，將其完整加密并上傳。當(dāng)要提交新的差異文件時(shí)，需首先從服務(wù)器取得所屬的標(biāo)準(zhǔn)文件，將新測序版本與之比較得到差異文件，最后把差異文件進(jìn)行同態(tài)加密并上傳。

（3）數(shù)據(jù)使用者

需要使用某一版本文件時(shí)，同時(shí)下載對應(yīng)的標(biāo)準(zhǔn)版本文件和差異文件，通過解密即可得到。

2.1 版本管理設(shè)計(jì)

本文將詳細(xì)說明版本管理方案相關(guān)信息，如圖2所示。

以Ensembl基因組數(shù)據(jù)庫上的人類基因組數(shù)據(jù)（homo_sapiens）的組織形式為例，定義了三個(gè)文件：標(biāo)準(zhǔn)文件（Std）、差異文件（Diff）、測序文件（Seq）?；蚪M數(shù)據(jù)包含多個(gè)拼裝版本中的一個(gè)版本，如GRCh37、GRCh38等，它們又均包含多個(gè) release，目的之一正是簡化這些 release，標(biāo)準(zhǔn)文件（Std）代表了每個(gè)拼裝版本中的初始版本。將同版本中其他 release 與之比較，即得到差異文件（Diff），另外新的實(shí)驗(yàn)產(chǎn)生的數(shù)據(jù)，定義為測序文件（Seq）。

差異文件的目的主要在于體現(xiàn)當(dāng)前版本（Seq）與參考版本（Std）的不同，即由參考版本改變?yōu)楫?dāng)前版本需要進(jìn)行的操作。因此，涉及到的信息主要包括改變的位置（Pos）、偏移量（Offset）、操作類型（Type）、改變后的數(shù)據(jù)（Data）。進(jìn)一步地，操作類型包括修改（Change）、添加（Add）、刪除（Delete），數(shù)據(jù)部分在修改、插入情況下可能為一至多個(gè)堿基，在刪除情況下為空。

當(dāng)向服務(wù)器新增文件時(shí)，主要有兩項(xiàng)操作：

（1）新增標(biāo)準(zhǔn)文件

（2）新增差異文件

對新增的文件，若設(shè)定為新的標(biāo)準(zhǔn)文件，則在主線新增，若為普通的差異文件，則找到對應(yīng)的標(biāo)準(zhǔn)文件分支，進(jìn)行添加。添加的文件均為同態(tài)加密后的密文文件。

2.2 數(shù)據(jù)編碼

遺傳物質(zhì)——脫氧核糖核酸DNA主要包含四種核苷酸[9]：腺嘌呤A、胸腺嘧啶T、鳥嘌呤G、胞嘧啶C，它們按一定順序附著在堿基上構(gòu)成有向鏈，兩條互補(bǔ)的有向鏈結(jié)合形成的空間構(gòu)成就是DNA。故DNA的一級結(jié)構(gòu)是線性結(jié)構(gòu)，經(jīng)測序后可以看作是字母表{A，G，T，C}上的字符串，其長度是從幾萬字符到幾百萬字符甚至上億字符不等。DNA 序列包含四個(gè)堿基，需占據(jù)4個(gè)編碼位。同時(shí)基因數(shù)據(jù)存儲匯總使用N代表沒有測定的堿基，比如在測序過程中出現(xiàn)gap，那么這一段都用N來代替這些還沒有測序、尚不明確的堿基，如圖3所示。將NAGCT分別編碼為：1111，0001，0010，0100，1000，再用4位0值補(bǔ)足8比特。

一條操作信息由Pos、Offset、Type、Data 四項(xiàng)組成，并使用起始符、終止符將一條完整的操作封裝起來，對每一項(xiàng)均進(jìn)行同樣的編碼。

2.3 同態(tài)加密

在上一節(jié)中，已經(jīng)將數(shù)據(jù)進(jìn)行了編碼。這里將編碼后的數(shù)據(jù)進(jìn)行同態(tài)加密處理。如前所述，同態(tài)加密是一種對數(shù)據(jù)進(jìn)行加密的技術(shù)，任何人都可以在不掌握加密或解密密鑰的情況下對其進(jìn)行計(jì)算。[6]第一次提出了完全同態(tài)加密，是密碼學(xué)上的一項(xiàng)重要突破。很多相關(guān)工作進(jìn)一步完善了這一領(lǐng)域，如[10][11][12]。

使用到了位加密技術(shù)，該技術(shù)即為將需要加密的明文轉(zhuǎn)換為二進(jìn)制數(shù)據(jù)，再對得到的二進(jìn)制位進(jìn)行加密，得到密文。選用異或運(yùn)算符進(jìn)行加密、解密。在二進(jìn)制運(yùn)算中，如果將一個(gè)明文的二進(jìn)制位與密鑰進(jìn)行按位“異或”運(yùn)算，將得到密文;將此密文與密鑰再次進(jìn)行按位“異或”運(yùn)算，又可以得到明文。使用位加密作為同態(tài)加密的加密算法，則為一種對稱加密算法。

使用的同態(tài)加密方案主要由幾種算法組成：

（1）：生成8位二進(jìn)制密鑰，同時(shí)作為加密密鑰和解密密鑰;

（2）：給定公鑰，加密明文元素m∈R， 為待加密明文空間。加密使用異或操作，即;

（3） ：給定私鑰，密文，解密算法使用如下公式恢復(fù);

3 實(shí)驗(yàn)與分析

在實(shí)際版本檢測中，差異的密度比較低，因此選取一個(gè)長度為20基因序列片段為例，演示算法設(shè)計(jì)，如圖4和圖5所示。

作為標(biāo)準(zhǔn)文件的序列如圖4所示。

測序新得到的序列如圖5所示。

得到差異文件（Diff）如圖6所示。

依照編碼設(shè)計(jì)，對Std 文件和 Diff 文件進(jìn)行編碼，如圖7所示。

根據(jù)設(shè)計(jì)的方案，首先設(shè)定作為標(biāo)準(zhǔn)版本（）的基因組數(shù)據(jù)文件，并存儲其同態(tài)加密版本（），對于后續(xù)實(shí)驗(yàn)測得的版本（），將其與標(biāo)準(zhǔn)版本（）進(jìn)行比對，得到一個(gè)定義的差異文件（），這個(gè)差異文件記錄了由標(biāo)準(zhǔn)版本（）變化到當(dāng)前版本（）需要進(jìn)行的操作。將這一文件進(jìn)行同上的同態(tài)加密操作，并上傳到服務(wù)器進(jìn)行存儲。當(dāng)使用者需要某一版本的基因組數(shù)據(jù)時(shí)，即可下載同態(tài)加密后的標(biāo)準(zhǔn)版本文件（）與同態(tài)加密后的差異文件（），兩者經(jīng)過合并即為對應(yīng)版本的數(shù)據(jù)。經(jīng)過解密操作，即可得到所需的數(shù)據(jù)信息。

4 結(jié)束語

本文提出了一種基于差異版本的同態(tài)加密文件的連接技術(shù)。更準(zhǔn)確地說，我們對具有強(qiáng)隱私性的文件，提出了簡潔存儲和安全管理的技術(shù)。通過設(shè)定標(biāo)準(zhǔn)文件，定義當(dāng)前版本與標(biāo)準(zhǔn)版本的差異文件，在數(shù)據(jù)服務(wù)器端存儲標(biāo)準(zhǔn)文件和差異文件的同態(tài)加密結(jié)果。同時(shí)，利用同態(tài)加密的位同態(tài)性質(zhì)，實(shí)現(xiàn)密文文件的連接操作，進(jìn)而實(shí)現(xiàn)密文的增刪改操作。方案可以使當(dāng)前生物數(shù)據(jù)網(wǎng)站存儲更少量的數(shù)據(jù)，同時(shí)保障數(shù)據(jù)的隱私性。方案具有實(shí)現(xiàn)簡便、安全性強(qiáng)的特點(diǎn)。這一方案也可應(yīng)用于其他類似的數(shù)據(jù)場景中。

基金項(xiàng)目：

國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（項(xiàng)目編號：2017YFC1201204）。

參考文獻(xiàn)

[1] Humbert， M.， et al. Addressing the concerns of the lacks family：quantification of kin genomic privacy[C]. in Acm Sigsac Conference on Computer & Communications Security. 2013.

[2] Yaniv， E. and N. Arvind. Routes for breaching and protecting genetic privacy[J]. Nature Reviews Genetics， 2014，15（6）： 409-421.

[3] Naveed， M.， et al. Privacy in the Genomic Era[J]. Acm Computing Surveys， 2015，48（1）： 1-44.

[4] Melissa， G.， et al. Identifying personal genomes by surname inference[J]. Science， 2013，339（6117）： 321-324.

[5] Malin， B. and L. Sweeney. How （not） to protect genomic data privacy in a distributed network： using trail re-identification to evaluate and design anonymity protection systems[J]. Journal of Biomedical Informatics， 2004，37（3）： 179-192.

[6] Gentry， C. A fully homomorphic encryption scheme[M]. 2009.

[7] Murat， K.， et al. A cryptographic approach to securely share and query genomic sequences[J]. IEEE Transactions on Information Technology in Biomedicine， 2008，12（5）： 606-617.

[8] Kolesnikov， V.， A.R. Sadeghi， and T. Schneider. Improved Garbled Circuit Building Blocks and Applications to Auctions and Computing Minima[C]. in International Conference on Cryptology and Network Security. 2009.

[9] Wiki.DNA [EB/OL]. https：//en.wikipedia.org/wiki/DNA.

[10] Brakerski， Z. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP[C]. in Cryptology Conference on Advances in Cryptology-crypto. 2012.

[11] Bos， J.W.， et al. Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme[M]. 2013.

[12] Brakerski， Z.， C. Gentry， and V. Vaikuntanathan.（Leveled） Fully Homomorphic Encryption without Bootstrapping[J]. Acm Transactions on Computation Theory， 2014，6（3）： 1-36.