基于广义SUFFIX树的基因组数据隐私保护字符串搜索

医学信息学解锁23（2021）100525基于广义SUFFIX树的基因组数据隐私保护字符串搜索Md Safiur Rahman Mahdia，Md Momin Al Aziz a，*，Noman Mohammeda，Xiaoqian Jiang ba加拿大马尼托巴大学计算机科学系b美国休斯敦得克萨斯大学健康科学中心生物医学信息学院A R T I C L EI N FO保留字：基因组数据的隐私子串搜索广义充分树安全子串搜索A B S T R A C T背景和目的：高效的测序技术产生了大量的基因组数据，并使其可供研究人员使用。为了计算大量的基因组数据集，通常需要将数据外包到云端。在外包之前，数据所有者会加密敏感数据，以确保数据的机密性。外包可以帮助数据所有者消除本地存储管理问题。由于基因组数据量很大，安全有效地执行研究人员方法：本文提出了一种在一个随机变量上安全地进行子串搜索和集合最大值搜索的方法使用广义充分树的SNP数据集。所提出的方法保证以下：（1）数据隐私，（2）查询隐私，和（3）输出隐私。它采用半诚实对手模型，通过加密和置乱电路保证数据的安全性。结果：我们的实验结果表明，我们提出的方法可以计算安全的子串和集最大搜索对单核苷酸多态性（SNPs）数据集的2184条记录（每条记录包含10000个SNPs），分别在2.3和2 s。此外，我们将我们的结果与现有的安全子串和集合最大搜索技术（Ishimaki等人，2016; Shimizu等人，2016年[1，2]， 400和2倍改善（表5）。1. 介绍由于当前测序技术的进步，基因组数据的量正在巨大地增长。如果我们能够确保数据的安全性和隐私性，将这些海量数据存储到云端可能是一个可行的解决方案。字符串搜索是一个众所周知且经常使用的问题，研究人员已经提出了几种算法。基因组数据的子串搜索和集合最大搜索是计算机科学中不可缺少的方法。子串搜索在现实生活中有很多应用，如祖先搜索[3]、相似患者查询、创建个性化医疗等。除了基因组数据，子串和集最大搜索也是必不可少的模式匹配和单词搜索。它们用于搜索文本消息、聊天记录或文档中的任何关键字。基因组数据比许多形式的数据更敏感，因为它们包含遗传信息。因此，我们必须保护上传到云中的基因组数据的安全性和隐私性。基因组数据泄露一个人的健康状况可能会揭示他们对特定疾病的易感性，这可能会影响他们是否有资格获得健康保险[4]。最近，人类基因组数据被用于法医学以识别金州杀手，像这样的例子显示了这些数据集的各种应用，并加剧了它们的隐私影响[5]。在本文中，我们的主要研究目标是外包基因组数据和计算子串和集合最大搜索外包数据的隐私保护的方式。在我们提出的模型中，我们利用云来存储数据，因为大量的基因组数据。我们提供外包云数据的数据隐私。因此，云无法从上传的数据中推断出任何信息。此外，研究人员以保留查询隐私和输出隐私的方式在云上执行查询。因此，任何对手或云本身都不会了解研究人员的查询，并且查询输出仅对研究人员可用。保护隐私的子串搜索和集极大搜索是一个基本问题，许多研究者提出了各种解决方案。根据搜索序列的数目、查询长度、起始位置、精确匹配和最大匹配，可以将EX匹配分为若干个子方法。我们比较了我们提出的方法与Ishimaki等人的子串搜索[1]其中，* 通讯作者。电子邮件地址：azizmma@cs.umanitoba.ca（M.M. Al Aziz）。https://doi.org/10.1016/j.imu.2021.100525接收日期：2020年10月2日;接收日期：2021年1月17日;接受日期：2021年2021年1月23日在线提供2352-9148/© 2021作者。出版社：Elsevier Ltd这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表医学信息学期刊主页：http://www.elsevier.com/locate/imuM.S. Rahman Mahdi等人医学信息学解锁23（2021）1005252M≈[]=[]=研究人员的查询序列长度小于数据集序列，并且研究人员对来自特定位置的精确匹配感兴趣。我们还将我们提出的集合最大搜索方法与Shimizu等人进行了比较。[2]，其中研究人员对查询序列和数据集序列之间从开始位置开始的最大匹配感兴趣。我们利用广义后缀树这种数据结构来存储一个序列的充分性.本文的新贡献总结如下：我们提出了一个隐私保护协议，以解决两个问题的基因组数据的基础上：子串搜索查询和集合最大匹配。我们利用广义充分树来创建基因组数据的索引。我们提出了不同的算法来执行安全子串搜索和安全集最大搜索加密树通过混淆电路[6]。我们提出的方法保护数据隐私，查询隐私和输出隐私。我们实现了我们提出的方法，并通过与Ishimaki等人[1]的比较来评估安全的实验结果表明，在2184条记录（每条记录包含10000个SNP）的数据集上，执行安全子串搜索需要大约2.3s，而Ishimaki等人[1]需要16min。Fig. 1. 提出了医院、认证机构、云服务器和研究人员的系统模型。表1样本单倍型SNP数据表示。#SNP1SNP 2SNP 3SNP 4SNP 5SNP 6• 此外，我们比较安全的集最大搜索与清水等人。[2] Sotiraki et al.[7]工作。实验结果表明，在2184条记录（每条记录包含10000个SNP）的数据集上，执行安全集最大值搜索需要大约2s，而Shimizu等人[2]需要3.97s。2. 预赛在本节中，我们将描述我们提出的系统模型、我们使用的数据类型、查询类型、加密方法和威胁模型。2.1. 系统模型我们提出的模型有四个实体：医院，认证机构（CI），云服务器（CS）和研究人员。医院实体负责拥有和管理SNP数据。虽然我们将实体命名为医院，但它可以是任何拥有或收集基因组数据的组织。我们的协议中的第二个实体是CI，他从医院收集数据并构建广义充分树。它还加密树，将加密的树发送到CS，并管理加密和解密所需的密钥。此外，CI将解密所需的密钥发送给研究人员。在这里，我们可以通过将CI的职责（构建和加密树）授予医院，将这两个实体（医院和CI）合并为一个实体（医院）CS存储加密的树，并在执行查询时与研究人员进行通信。图1总结了我们提出的系统模型。2.2. 数据表示人类基因组的差异只有0. 两个人之间的1%的位置。基因组中的这种位置差异被称为单核苷酸多态性（SNP）。在本文中，我们考虑了一个数据集的n个人类SNP序列与m个SNP。使用从2018年iDASH竞赛中收集的马尔可夫聚结模拟器模拟SNP数据[8]。这里，SNP是双等位基因表示的，0或1。最频繁的值被称为主要等位基因，而频率较低的值被称为次要等位基因。主要等位基因编码为0，而次要等位基因编码为1。值得注意的是，为了简单起见，我们只有二进制表示，因为我们提出的方法可以在任何具有固定字符集的数据集上工作。表1显示了数据集的一个示例。1 1 0 0 0 1 02 1 1 1 0 1 0⋮n0 1 0 1 0 12.3. 查询类型在这项研究中，我们提出了两个不同的字符串查询执行对 一 基因组 数据集。 让 D被 一 数据集 的 基因型（D ∈ {0，1} n），Dj = d1，d2，.，dm其中Dj表示一个特定的环，数据集中的cord（或序列）（1≤j≤n）。di表示SNP的载体的第i个基因组的基因型，其中SNP相对于它们在基因组上的位置进行排序。我们解决两个不同的字符串搜索问题，如下所述定义1. （子串搜索）：给定数据集D，查询序列q和搜索开始位置s，可能存在记录Dj（零个或更多个），使得：q=Dj[ds，ds+|Q|-1]，其中1≤j≤|D|（ 一）实施例3.3.1.考虑研究者提交的查询，q = 010，起始位置s = 4。如果我们对表1执行这个查询q，它应该输出第一个序列d1：100010和序列d2：111010，因为它们匹配来自位置4的查询子串010。子字符串搜索过程的详细信息在第3.3.1节中描述。定义2. （集合最大搜索）：如上所述，给定D，q和s，则D中存在j′（零或更多），使得：1. q[i1，imax]=Dj′[ds，ds+dmax-1]2. q[imax+1]=scinDj′[ds+dmaxx]3 .第三章。 1 ≤ j′ ≤ |D|实施例3.3.2.考虑研究者提交的查询，q = 00011，起始位置s = 2。如果我们在表1上执行这个查询q，研究人员将从序列d1中得到0001：100010，其中包含4火柴因此，q i11和q imax4。 集合最大搜索过程的细节在第3.3.2节中描述。···M.S. Rahman Mahdi等人医学信息学解锁23（2021）1005253（）下一页∑∑（）下一页∑∑∈∈（）下一页∈[||]联系我们||2.4. AES计数器模式加密（CTR）为了加密数据，我们使用高级加密标准（AES-CTR）加密的计数器模式（CTR）[9]。AES-CTR通过加密初始化向量（IV）和计数器的连续值来生成密钥流。计数器是在加密中从不重复的随机数。因此，由于唯一的计数器（填充IV和计数器值），AES-CTR每次为相同的纯文本生成不同的密码。这里，加密函数定义为：y i=E N Ck（IV|| C T Ri）x i，i≥ 1解密函数定义为：x i=E N Ck（IV|| C T Ri）C TR i，i≥ 1其中xi、yi、ENCk、CTR分别是i）明文（SNP序列）、ii）密文、iii）加密密钥和iv）计数器值。在我们提出的模型中，CI对数据进行加密以保护数据隐私，并管理加密和解密所需的密钥（加密，IV，CTR）。值得注意的是，AES-CTR被证明在选择明文攻击或IND-CPA安全下不可区分[10]。第3.2节描述了使用AES-CTR的详细信息。2.5. 威胁模型在本节中，我们将介绍我们提出的隐私模型、配置和安全目标。2.5.1. 隐私模型在本文中，我们定义了我们的三个隐私模型如下：数据隐私：存储在CS中的数据应受到保护。如果CS受到损害，攻击者不应该了解任何关于存储在云中的数据的信息。查询隐私：医院（提供数据的机构），CS或对手不应该了解研究人员执行的查询。输出隐私：查询结果不应透露给任何人，除了发起查询的研究人员。在形式上，医院将基因组数据外包给CS，并提供安全保障。所提出的方法需要确保参与者的隐私免受任何对数据的对抗性攻击研究人员并且CS旨在执行私有搜索操作f（q，D），其中双方都不知道彼此的输入。因此，q和D不会是分别向CS或研究人员透露。此外，f q，D应该只向研究人员发布，因为CS和医院应该不知道这些结果。2.5.2. 安保假设对于我们提出的系统，我们依赖于以下四个假设我们假设CS是一个半诚实的实体（也称为诚实但好奇）[11]，它遵循协议，但观察通信，并可能在执行研究人员然而，CS不会通过偏离计算协议而恶意地行动。我们认为CI是一个可信的实体，因为它负责创建足够的树，并与研究人员共享必要的密钥来解密加密的结果。我们认为医院、CI和CS都没有恶意行为以生成不正确的输出。此外，我们认为政务司司长并没有与研究人员勾结，和CI，研究人员不与CS勾结。2.5.3. 目标在所提出的方法中，我们有两个特定的目标来解决数据的隐私问题我们的第一个目标是确保基因组数据集D的机密性，以便CS不会了解任何关于外包数据的信息。其次，研究人员的查询需要对CS隐藏，因为它也可能是敏感的3. 方法在本节中，我们提出了我们提出的安全子串和集最大搜索方法。我们将所提出的方法分为三个子过程：1）广义充分树构建，2）树加密，以及3）加密树上的安全搜索：我们总结了表2中的符号，图2表示我们提出的解决方案的整体协议。3.1. 广义后缀树（GST）的建立设S是字母表0， 1上的序列，S是S的长度，Si，i1：S是S从位置i开始的充分条件。序列S的充分树T是一个根树，它的边用S的子串标记。节点v的路径标签是从根到v的所有边标签的添加。S的每个子串S′只包含T的一个子树T′。SuffiX树的每个节点要么是叶节点，要么有两个子节点，最多从0或1开始。边上的标签可以具有大于零的任何长度，并且从同一节点出去的任何两条边都不能以相同的字符开始。因此，给定的（startNode，suffiX String）对可以表示树中的唯一路径。suffi x树的另一个方面是后缀链接[12]，它在线性时间内构建suffi X树。 一条充分链路是从路径标签为αw的节点v到路径标签为w的节点v′的链路，其中α和w+。 每个内部顶点都有一个充分链接。此外，Ukkonen利用边缘标签压缩和跳过/计数加速，这在参考文献[13 ]第10段。实施例4.1.1. 图图3使用表1的序列1呈现充分树。如果我们遍历图3中的节点，我们得到0，10，010，0010，00010，100010，这实际上是序列100010的充分条件广义后缀树（GST）表示∈ { 0，1 }上的多重序列S1，为此，我们可以为S1建立一个充分树，然后通过合并序列S2， 朴素构造一个充分树的实现需要On2的时间复杂度，其中n是序列长度[13]。然而，Esko Ukkonen [12]使用suffiX link将其减少到On（线性）时间。Ukkonen算法[12]从第一个字符向前推进到最后一个字符，从最长到最短。然而，Ukkonen的SUFFI X树仅对单个序列进行操作。由于我们的数据集包含多个序列（表1），我们构建了以下所示的广义SuffiX树（GST）：实施例4.1.2. 图4呈现了使用表1的序列1和2的GST。它显示了SNP特征，以及表2符号。符号含义RGST的根节点q查询序列pos查询职位匹配序列encpos加密的足够X位置eqGC通过GC进行cNode子节点enclabel加密的标签序列|边缘标签长度|Length of edge label|Q|查询字符串长度·······M.S. Rahman Mahdi等人医学信息学解锁23（2021）1005254̃̃•̃[客户端]（||）≥̃̃图二. 我们提出的解决方案的总体协议。图三. 一个序列的SuffiX图四、具有足够位置的广义Suffi X树。每个顶点。图中的每个填充圆（顶点）。 4表示包括suffi X位置和包含suffi X（ex）的序列号的suffi x（es）。例如，如果我们遍历到节点5，我们得到suffiX 010和节点属性1; 4， 2; 4，它们表示从位置4开始具有suffiX 010的3.2. Tree加密CI利用AES-CTR[9]对GST中的内容进行加密，以确保数据隐私。GST加密的详细过程如下：密钥生成：CI生成密钥（E N Ck）、加密向量（IV）和计数器（CTR）以加密GST的每个边缘标签和节点属性（如果有的话）。• 加密：首先，CI通过 以下方式构建密钥流：E N CkIV C T Ri，其中i1。然后，它加密每个边缘标签和节点属性（SUFFIX位置）之间的边缘标签/suffix位置和密钥流执行异或操作。我们应用了两种不同的加密设置：一种只使用GST标签加密，另一种同时使用GST标签和足够的加密。位置加密。我们将加密的GST表示为G S T。分享：CI发送G S T并将所需的密钥发送到研究员3.3. 加密树上的安全搜索一旦研究人员发送了他们的查询，搜索过程就从存储在CS中的G S T开始。在我们提出的方法中，为了保持查询隐私，我们将研究人员我们描述安全子串和集合最大搜索的详细过程如下：算法1.GST上的安全子串搜索3.3.1. 安全子串搜索我们根据第2.3节中的示例描述安全子串搜索过程，其中研究人员将其查询序列010和位置4发送到CS。算法1描述了安全子串搜索过程。首先，我们声明一个名为matchedseq的空列表来存储匹配结果（第1行）。然后，算法2找到与查询序列匹配的特定节点，并且加密的查询序列被加密。G S T.具体地，在遍历G S T时，GC执行相等性测试（第8行），其中查询和加密的树标签之间的公共子序列比较它们的最小长度。下面的示例描述了详细的过程：实施例4.3.1. 研究人员将查询序列（q=010）和起始位置（pos=4）发送到GC。首先，我们找到一个匹配的节点，用算法2求出了G S T中的查询序列和充分序列。算法2从查找与查询的第一个字符和加密标签的第一个字符匹配的边开始（第2行）。这种相等性检查由GC执行。由于SNP数据是双等位基因（0或1），在最坏的情况下，需要两次GC相等检查来找到匹配边缘。此外，每个加密边可以具有不同长度的SNP。因此，算法2的第4-7行找到相等长度的查询序列和加密的边缘标签。GC对加密的边缘标签进行解密，并使用相应的查询序列执行相等性测试（第8行）。如果查询和树标签匹配，则算法继续到下一个节点(line号13）。因此，对于查询序列q=010，·M.S. Rahman Mahdi等人医学信息学解锁23（2021）1005255===[客户端]=̃̃=̃||=++=（||）的方式||2将匹配加密的边标签0、10和返回节点#5。为了更好地理解，我们通过将边缘标签和节点属性以明文形式呈现来演示示例。在匹配查询序列之后，我们需要检查查询的开始位置和匹配节点的足够位置。该相等性检查也经由安全协议GC（算法1，第5行）来执行。我们观察到匹配的节点#5包含与查询开始位置pos4匹配的属性1;4， 2;4。CS将加密后的匹配序列发送给研究者，研究者通过解密得到所需的结果。因此，它保留了输出隐私，因为只有CI和具有特定密钥的研究人员可以解密结果。算法1还检查匹配节点的每个子节点的足够位置，因为子节点也可以匹配查询序列和给定位置（getLeafInfo，第10-16行）。例如，在图4中，对于起始位置为1的查询序列q 10，算法2将返回节点#4。检查节点属性时#4（ 1; 5， 2; 5），算法1，第5行将不匹配查询开始位置pos=1。然而，节点#4具有子节点#10，其将suffiX位置1与查询开始位置pos=1匹配。3.3.2. 安全集极大搜索我们从第2.3节的例子中演示了安全集最大搜索过程，研究人员将他们的查询q 00011和pos 2发送到CS。同样，为了保护查询隐私，我们将返回者算法3描述了安全集-极大值搜索过程。安全子串搜索与集合最大搜索的区别在于，集合最大搜索中，GC检查的是查询序列与加密边标签之间的公共前缀个数，而不是相等性检验。下面的示例描述了详细的过程：算法2.GST上的匹配节点（子字符串搜索）实施例4.3.2. 研究人员发送查询q00011并开始po- 位置2到GC。与前面的示例类似，我们在查询序列和算法4的G S T。同样，算法4开始于找到与查询的第一个字符和GC加密标签的第一个字符匹配的边（第3行）。此外，算法4的第5-8行发现查询序列和加密的边缘标签的长度相等。GC对加密的边缘标签进行解密，并获得具有相应查询序列的公共前缀的数量（第9行）。如果查询和树标签匹配，则算法继续到下一个节点（第13行）。因此，对于查询序列q 00011，算法4将遍历节点：2、6、12和14。返回节点#12作为匹配节点，并返回4（ 1 1 2）作为匹配计数。为了更好地理解，我们通过将边标签和节点属性以明文形式呈现来演示示例。此外，我们需要检查GC查询的起始位置和匹配节点的足够位置（第5行）。我们观察到匹配的节点#12包含与查询开始位置pos=2匹配的属性[ 1; 2]。在遍历GSTT时，特定查询和加密树标签之间的多个公共前缀实际上确定它们之间的最大匹配（算法4的第9行：noOf-Match）。由于getLeafInfo的描述类似于算法1，所以我们不在算法3中描述它。此外，我们不需要在第10行执行GC相等测试如果在安全子串搜索和集合最大搜索中保持足够的位置不加密，则算法1和算法3都是53.3.2.1. 复杂性分析。算法2和算法4分别表示安全子串和集合最大搜索过程的搜索复杂度。对于这两种算法，仅搜索查询序列的最坏情况时间复杂度为O（|Q|），其中|Q|是查询长度 因为我们只是穿越|Q|字符使用GC在G S T，它应该导致最多q次搜索。这也在图5c的第4节中实验性地呈现（仅数据加密）。此外，如果我们加密树标签和每个节点的足够位置，则搜索查询序列的最坏情况时间复杂度取决于Oq t，其中q是查询序列的长度，t是包含匹配序列的数据集中的记录数。然而，由于GST的属性，查询开始位置不影响相同查询长度的搜索复杂度。算法3. GST上的安全集极大搜索M.S. Rahman Mahdi等人医学信息学解锁23（2021）1005256| |̃̃| |==-| |联系我们| | =--||=-| |={}={个||=-| |为||为图五. 树构建、加密和查询执行时间。算法4.GST上的匹配节点（集合最大搜索）4. 结果实现细节：安全子串和集合最大搜索的拟议方法在Java中实现，因为我们利用了2018年iDASH竞赛的合成数据集[8]。该数据集包含1000个个体的5000个SNP 我们在两台不同的机器上运行了CS和CI，机器上安装了英特尔酷睿i7（3. 41 GHz处理器）和16 GB内存。我们使 用 FlexSC[14] 库 实 现 了 自 定 义 GC 协 议 该 代 码 可 在https://github.com/Safiur-Mahdi/SecSS中找到。为了理解所提出的模型的可扩展性，我们用四个参数进行了实验：基因组序列上的SNP数量m、序列总数n、查询起始位置s和查询长度q。我们进一步分析了两种加密设置：1）GST标签加密，以及2）GST标签和充分位置加密，这对隐私和执行时间有直接影响。值得注意的是，执行时间和通信开销是10次随机试验的平均值。实验设置和细节：在下面的实验中，我们感兴趣的是分析GST生成和安全查询过程。休息时间。由于构建（和加密）G S T是一次性的预处理步骤，因此需要了解特定数据集n，m所需的时间。在处理查询时，查询长度q也是重要的，因为它保证了在整个查询过程中不同级别的搜索。G S T.图5a示出了具有加密的边缘标签和充分位置的GST构建和加密时间。我们注意到，数据预处理时间（树构建和加密）随着m的增加而线性增加，因为它增加了充分的总数。另一方面，图5b示出了不同数量的记录n200， 400，类似地，预处理时间随着n的增加而线性增加。有趣的是，与加密时间相比，树的构建时间要少得多。值得注意的是，这可以并行地完成，这可以加速 上预处理步骤。变量SNPm：表3表示查询执行时间和通信开销（固定n和变量m）。在这两个实验中-项（子串/集合最大搜索），我们考虑了五个不同的m=1000，2000，...，5000，q25，n1000.值得注意的是，与子串搜索相比，集合最大搜索的查询执行时间更快，通信开销更低，因为它需要执行的匹配更少。在子串搜索中，我们对精确匹配的结果感兴趣，而集合最大搜索要求查询和加密树标签之间的最大匹配。因此，查询和树标签之间的初始位置不匹配可能会导致更快的执行时间，从而导致与子串对应物相比更有效的集合最大搜索。我们还观察到，增加m既不影响执行时间，也不影响通信开销。然而，如果我们加密数据（树边缘标签）和足够的位置，查询执行时间和通信开销增加。序列n的变量数量：表4给出了记录n200、400、...、1000、q 25和m 3000的变量数量上的相同度量。我们观察到查询执行时间和通信开销都随着n的增加而线性增加，因为总匹配数随着n的增大而增加。值得注意的是，对于仅加密数据的两种搜索方法，时间和通信几乎相似，而对于加密的足够位置，时间和通信线性增加。这是因为增加n需要在GC上沿着加密的数字位置进行更多的相等性测试（算法1，3中的第5行）可变查询长度|Q|图5c示出了不同查询长度q50、100、.250的子串搜索查询执行时间，固定查询起始位置（s 1），n1000条记录，m3000个SNP。我们还根据两种不同的加密设置执行了这个实验：仅GST标签（数据）加密，以及数据和充分位置加密。虽然数据和足够的位置都是加密的，我们报告说，不同的查询长度与一个固定的查询开始位置影响查询执行时间。我们还分析了查询大小对执行时间的影响，因为它随着q的增加而减少，部分原因是总匹配计数减少。这是违反直觉的，因为它应该需要更少的时间来找到匹配， Q50而不是 Q150.然而，与q150相比，查询长度为50的匹配节点包含更多足够的位置来检查。另一方面，如果我们只使用加密数据执行相同的查询，则查询执行时间会随着增量|Q|. 但是，set-maximum搜索执行时间为M.S. Rahman Mahdi等人医学信息学解锁23（2021）1005257≈表3在m∈ [1000， 5000]的1000条记录上进行子串搜索和集合最大搜索的查询EX搜索时间（QET）和通信开销（CO）。查询类型子串搜索集极大搜索加密数据数据充足X位置&数据数据充足X位置&标准表4QET和CO用于子串搜索和集合最大值搜索3000个具有不同记录数的SNP，n∈ [ 200， 1000]。查询类型子串搜索集极大搜索加密数据数据充足X位置&数据数据充足X位置&标准独立于该查询长度并且取决于匹配的数量（表3和表4）。标杆我们通过与Ishimaki等人[1]（子串搜索）和Shimizu等人[2]（集合最大搜索）进行比较来评估我们提出的方法。对于子串搜索[1]，需要16分钟来处理由10个SNP组成的安全查询，而我们提出的方法只需要二、3秒Shimizu等人[2]需要大约4 s 以解决包含25个SNP的查询的安全集最大搜索。相比之下，我们提出的方法需要大约2秒的处理时间。值得注意的是，与Shimizu et al.[ 2 ]的工作相比，Ishimaki et al. [ 1 ]的实现不可用，因为我们无法在同一台机器上进行基准测试。然而，Ishimaki等人使用了一个比我们的更好的计算服务器来执行他们的实验。5. 讨论在本节中，我们将解释我们提出的模型的优点、缺点和未来的工作。5.1. 我们方法•广义后缀树在我们提出的方法中，CI从医院提交的累积数据中构建广义充分树。这是我们所提出的方法中的预处理步骤，其中我们将每个数据序列的所有suffiXes连同suffiX位置和序列号一起存储在GST中。建立商品及服务税的主要好处有两方面。该算法首先根据相似序列的充分位置对相似序列进行分类，表5比较2184条记录上的安全子串/集合最大搜索执行时间，每条记录包含10000个SNP [2]。Sotiraki等人[7]的工作被评估为|Q|，m= 300和n= 1000。序列号其次，增加数据集中SNP的数量不会影响查询执行时间。我们可以在表3中看到这一点。此外，我们只需要一次性的预处理来构建和加密GST。•安全集中模型我们利用集中式（外包）模型，其中医院通过可信实体CI将其数据集外包给CS。一旦外包，医院和CI之后可以保持离线。另一方面，在分布式（联合）模型中，医院/数据所有者不会将其数据集外包给云服务器。因此，分布式模型要求数据所有者在计算期间保持在线[15]。•隐私权保障数据隐私。 数据使用AES-CTR加密并存储在云服务器上。AES-CTR提供了一种语义安全的加密方案，即使数据从受损的云服务器泄露，也能确保数据的隐私。询问隐私。 由于查询是直接提交给GC的，因此只有研究人员知道，而系统中的任何其他参与实体都不知道。输出隐私。研究人员只有在解密结果后才知道结果，而云服务器只处理加密的副本。然而，我们并不阻止查询输出后的任何推理攻击，因为我们假设重新搜索者是诚实的。5.2. 限制•CS中搜索模式的泄漏在我们提出的方法中，在查询执行期间，CS学习问题比较EX EC时间树遍历模式，因为它依赖于研究人员的查询输入Ishimaki等.[1] 16 min我们的工作2. 3 sShimizu et al.[2] 3.97秒Sotiraki等人[7] 60年代我们的工作2s和GC输出。然而，CS将不会学习或推断任何敏感信息，因为SNP值的值是加密的，并且我们假设CS不与研究人员勾结。我们可以通过使用遗忘RAM来解决这种泄漏[16，17]，这将进一步积累计算复杂度。···n*m /评价QET（秒）文书主任（KB）QET（秒）文书主任（KB）QET（秒）文书主任（KB）QET（秒）文书主任（KB）1000*10002.26421.3681.4406.8841000*20002.36423.2771.7486.7841000*30002.46425.6821.6477.1871000*40002.26424.1781.5416.9871000*50002.16422.8771.8506.784n*m /评价QET（秒）文书主任（KB）QET（秒）文书主任（KB）QET（秒）文书主任（KB）QET（秒）文书主任（KB）200*30002.2867.4221.083.72.88400*30002.055.4611.7371.073.73.411600*30002.035.4616.1511.33.74.816800*30002.256.322.3711.144.015.7191000*30002.46.425.6821.64.77.123M.S. Rahman Mahdi等人医学信息学解锁23（2021）1005258[客户端]ו恶意研究者如第3.2节所述，研究人员从CI接收密钥（E N Ck，IV）以解密加密结果。因此，我们不认为本文中有任何不诚实的研究人员CI应该为每个研究人员创建和存储配置文件，并在向研究人员发送密钥之前进行身份验证。然后，由于研究者在查询CS时不是匿名的，CS监视研究者的动作以检测任何异常。如果CI发现任何不当行为，它可以阻止研究人员。5.3. 今后工作在本文中，我们的两个查询（安全子串搜索和安全集最大搜索）需要一个查询字符串的长度小于数据集序列的长度，和一个起始位置。在未来的工作中，我们打算扩展我们的工作以支持集合最大匹配[18]，其中查询长度将与数据序列长度相同，并且不给出起始位置。此外，我们可以在子串搜索查询中添加阈值，以便研究人员可以在查询序列和任何给定数据集之间实现一定数量的匹配结果。6. 安全分析所提出的框架的安全性依赖于两个原语：AES计数器模式（AES-CTR）和乱码电路。AES-CTR [9]的安全保证得到了很好的分析和理解，因为它在选择纯文本（IND-CPA）攻击下是不可识别的[10]。由于我们在AES-CTR的每次迭代中使用不同的随机IV，因此它将对相同输入基因组数据（或核苷酸值）的密文进行随机化。在我们的方法中，我们加密了不同节点上的核苷酸值和边缘值，这些值需要对CS隐藏。乱码电路支持对抗半诚实对手的安全两方计算[6]。在运行乱码电路后，双方都知道了函数的输出，但对彼此的输入一无所知CI加密树并将其发送到云服务器。云服务器将无法学习和解密树，因为它没有相应的密钥。研究人员直接将查询发送到GC，因此，云服务器将无法学习它。研究人员和云服务器使用乱码电路来执行查询，使得研究人员和云服务器将无法学习每个查询。别人6.1号提案所提出的隐私保护方法是安全的，对已知的密文攻击。证据如果可以证明云服务器或对手无法从加密的密文中获得任何有意义的信息，则任何加密方案都被认为是安全的，可以抵御已知的密文攻击。在我们提出的方法，所有基因组数据的核苷酸值都使用AES-128CTR密码系统加密。AES-CTR本质上将AES从块密码转换为流密码，因为输出密文是随机的，独立于明文。例如，核苷酸值（A，T，G，C）是重复的，并且它们需要在加密。由于云服务器将仅在外包的Suffix树上具有这些随机化的敏感加密值，因此将需要不切实际的计算时间量来破解密码系统。此外，根据NIST [19]，AES-CTR中使用的128位密钥将是安全的。7. 相关工作我们可以将现有的安全字符串搜索工作分为三类，如下所述：7.1. 没有查询起始位置的安全子串匹配是一种常见的方法，也是一个热门的研究领域。Katz等人[20]提出了一种使用乱码电路的安全精确DNA序列搜索[6]。Atallah等人。[21]利用动态编程来比较使用同态加密的两个序列。其他研究人员利用有限自动机与递归不经意传输（ROT）来解决DNA搜索问题[22，23]。Sudo等人。[24]提出了一种独特的算法，他们利用安全小波矩阵和加法同态加密在对数时间内进行搜索。7.2. 子串搜索虽然相关，但上述工作没有解决基于起始位置的安全精确子串搜索。在本文中，我们提出了一个安全的模型来找到一个字符串匹配的查询和数据集序列，其中查询提到的起始位置。此外，我们感兴趣的是找到精确的匹配计数，而不是最大的匹配。据我们所知，Ishimaki等人[1]仅解决了这个问题，因为他们从位置Burrows-Wheeler变换（PBWT）创建了一个查找表，并利用FHE进行自举优化。此外，为了减少不正确的解密（由于密文中的随机噪声），作者提出了两种解决方案：i）设置阈值噪声以确保正确解密，以及ii）通过利用自举方法重置噪声，这是非常昂贵的。7.3. 集极大搜索保护隐私的集最大搜索是另一种不可或缺的方法，有助于识别远亲。Shimizu等人[2]介绍了一种安全的可变长度的前缀/后缀匹配SNP序列或常规文本。对于预处理，作者使用Durbin等人提出的PBWT。[3]作为数据结构，而我们使用广义充分树来预处理数据。为了保证保密性，我们使用了乱码电路，而作者使用了加同态加密的ROT方法作为安全协议。在2019年的一个最近的解决方案中，Yamada [25]在字符串搜索框架中采用了完全和部分同态加密方案。然而，查询长度仅从5、 25中选择，最多需要80秒，这在现实生活中的基因组搜索操作中是不现实的。2019年，iDASH [8]组织了一场在两方环境中安全计算集合最大匹配的竞赛最准确的解决方案由MicrosftResearch[7]提出，并使用Goldreich-Micali-Wigderson（GMW）协议[26]。在这里，解决方案需要双方之间的XOR、AND和NOT运算的私有评估尽管如此，对于1000个数据库， 1000和查询大小300。不幸的是，iDASH 2020中提交的解决方案都没有成功用于10万个SNP。表6总结了现有的隐私保护字符串搜索方法。我们对以往的基于查询的方法进行了类型和查询起始位置的要求8. 结论本文提出了一种安全的基因组数据子串和集极大值搜索协议.我们提出了一种广义后缀树索引，并提出了由乱码电路保证的私有查询执行。与早期作品（Ishimaki等人[1]和Shimizu）的比较 等人[2]）证明了查询执行时间的显著改进。Sotiraki等人[7]的最新结果也因GST指数而较慢。在未来，我们打算扩展所提出的方法来执行子串和适当的字符串搜索的其他变体（即，没有预定义的查询位置）使用M.S. Rahman Mahdi等人医学信息学解锁23（2021）1005259表6以前的研究工作在基因组序列中的安全和隐私保护字符串搜索（HE =同态加密，ROT =递归不经意传输，GC =乱码电路，AHE =加性同态加密，FHE =全同态加密）。[2] 清水K，努伊达K，RüatschG. 高效的隐私保护字符串搜索及其在基因组学中的应用。生物信息学2016;32（11）：1652-61。[3] 德宾河使用位置Burrows-Wheeler变换（PBWT）进行高效的单倍型匹配和存储。 Bioinformatics 2014;30（9）：1266-72.[4] Naveed M，Ayday E，Clayton EW，FellayJ，Gunter CA，Hubau X J-P，Malin BA，Wang X. 基因组时代的隐私 ACM Comput Surv 2015;48（1）：6.Ex射线衍射技术年份查询类型查询起始位置主要方法[5] Guerrini CJ，Robinson JO，Petersen D，McGuire AL。警察应该访问遗传家谱数据库吗？利用一种有争