基于同態加密的生物數據版本管理

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

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

關鍵詞：版本管理;同態加密;生物信息學;數據隱私;同態連接

中圖分類號：TP393? ? ? ? ? 文獻標識碼：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 引言

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

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

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

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

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

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

如圖1所示描述了方案的總體設計和執行過程。

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

（1）數據庫服務器

存儲同態加密形式下的多個基因組數據文件及差異文件。

（2）數據提供者

當產生新的測序文件，根據其版本類型進行相應操作，上傳至服務器。當要提交的數據要作為標準文件時，將其完整加密并上傳。當要提交新的差異文件時，需首先從服務器取得所屬的標準文件，將新測序版本與之比較得到差異文件，最后把差異文件進行同態加密并上傳。

（3）數據使用者

需要使用某一版本文件時，同時下載對應的標準版本文件和差異文件，通過解密即可得到。

2.1 版本管理設計

本文將詳細說明版本管理方案相關信息，如圖2所示。

以Ensembl基因組數據庫上的人類基因組數據（homo_sapiens）的組織形式為例，定義了三個文件：標準文件（Std）、差異文件（Diff）、測序文件（Seq）。基因組數據包含多個拼裝版本中的一個版本，如GRCh37、GRCh38等，它們又均包含多個 release，目的之一正是簡化這些 release，標準文件（Std）代表了每個拼裝版本中的初始版本。將同版本中其他 release 與之比較，即得到差異文件（Diff），另外新的實驗產生的數據，定義為測序文件（Seq）。

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

當向服務器新增文件時，主要有兩項操作：

（1）新增標準文件

（2）新增差異文件

對新增的文件，若設定為新的標準文件，則在主線新增，若為普通的差異文件，則找到對應的標準文件分支，進行添加。添加的文件均為同態加密后的密文文件。

2.2 數據編碼

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

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

2.3 同態加密

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

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

使用的同態加密方案主要由幾種算法組成：

（1）：生成8位二進制密鑰，同時作為加密密鑰和解密密鑰;

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

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

3 實驗與分析

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

作為標準文件的序列如圖4所示。

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

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

依照編碼設計，對Std 文件和 Diff 文件進行編碼，如圖7所示。

根據設計的方案，首先設定作為標準版本（）的基因組數據文件，并存儲其同態加密版本（），對于后續實驗測得的版本（），將其與標準版本（）進行比對，得到一個定義的差異文件（），這個差異文件記錄了由標準版本（）變化到當前版本（）需要進行的操作。將這一文件進行同上的同態加密操作，并上傳到服務器進行存儲。當使用者需要某一版本的基因組數據時，即可下載同態加密后的標準版本文件（）與同態加密后的差異文件（），兩者經過合并即為對應版本的數據。經過解密操作，即可得到所需的數據信息。

4 結束語

本文提出了一種基于差異版本的同態加密文件的連接技術。更準確地說，我們對具有強隱私性的文件，提出了簡潔存儲和安全管理的技術。通過設定標準文件，定義當前版本與標準版本的差異文件，在數據服務器端存儲標準文件和差異文件的同態加密結果。同時，利用同態加密的位同態性質，實現密文文件的連接操作，進而實現密文的增刪改操作。方案可以使當前生物數據網站存儲更少量的數據，同時保障數據的隱私性。方案具有實現簡便、安全性強的特點。這一方案也可應用于其他類似的數據場景中。

基金項目：

國家重點研發計劃項目（項目編號：2017YFC1201204）。

參考文獻

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