基于同态加密的生物数据版本管理

杨明朗　满毅　刘宁宁　张奕欣　邢潇

摘   要：随着生物技术的发展和研究的深入，生物数据也逐步完备。对于同一物种的基因组测序，也在原始版本的基础上不断完善。当前主流的存储方式为将多个测序版本完整保存，由于生物数据本身体积较大，对相似的大数据存储大量重复部分是不划算的。同时，由于这些数据经常涉及到较高的隐私性，在公开情景执行修改和分析时，需要有一定的手段对其进行保护。文章设计了数据的差异文件版本管理方案，并结合同态加密技术，实现基因组数据的轻便存储和安全修改，并通过对短 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.