数据库加密的问题，近年来出现了一系列针对加密字符数据查询的技术

沙特国王大学学报一种设计索引以支持加密数据库Canh Ngoc Hoanga，Minh Hieu Nguyenb，Chang，Thuy Thu Thi Nguyena，Huy Quang VuaaThuongmai大学，Ho Tung Mau 79号。ST，Cau Giay，河内，越南b越南河内阮志成街105号密码科学与技术研究所阿提奇莱因福奥文章历史记录：2022年9月23日收到2023年1月9日修订2023年2月8日接受2023年2月15日在线提供保留字：布隆过滤器连接字符对字符位置可搜索索引子串搜索双指标A B S T R A C T近年来，对数据库中加密字符数据的查询技术引起了人们的兴趣，主要集中在关键字的检索上。本文提出了一种基于代理模型的双索引可查询对称加密方案（DIQ-SSE）。该模式允许有效地查询外包数据库上加密字符字段上的任何子串。该方案的思想是对Proxy安全区中的每一个明文A都采用传统的加密算法进行加密。在这段时间里，建立了两个特殊的索引集Index1和Index2，用于支持搜索。对应A的元组（密码、索引1和索引2）存储在外包数据库中。为了执行查询，使用了4个阶段。首先，对查询命令进行转换。其次，查询是在索引1上执行的。然后，继续在Index2上查询从阶段2获取的数据的任务。在最后一个阶段，数据被解密，并进行查询的明文。除了提出分四个阶段建立索引和查询的算法外，本文还对保护进行了分析和实验评估。版权所有2023作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY许可下的文章（http://creativecommons.org/licenses/by/4.0/）。1. 介绍工业革命4.0的到来要求许多组织将其数据迁移到云端进行存储和管理。然而，数据所有者可能会失去对数据的控制，并面临数据泄露问题。为了解决这些问题，组织然而，由于无法对加密数据执行查询，这给数据挖掘用户带来了障碍。为了解决这个问题，支持对加密数据（SE）的搜索的许多方案（Cash等人，2013; AES，2001;Boneh等人，2004; Boneh等人，2007; Chang和Mitzenmacher，2005; Chase和Kamara，2010; Curtmola等人，2006年;Goh，2003年;*通讯作者。电 子 邮 件 地 址 ： canhhn@tmu.edu.vn （ 中 国 ） NgocHoang ） ，hieuminhong@gmail. com （ M. Hieu Nguyen ） ， nguyenthithuthuy@tmu.edu.vn（T.Thu Thi Nguyen），huyvq@tmu.edu.vn（H. Quang Vu）。沙特国王大学负责同行审查Golle等人，2004; Hwang和Lee，2007; Lai等人，2013; Moataz和Shikfa，2013; Shi等人，2007; Song等人，2000）已经建立，其专注于用于加密模式的精确关键字搜索技术。加密模式可以是对称的或非对称的。然而，关键字搜索只是一种特殊的子字符串搜索;它不适用于云环境中最终用户的各种查询请求，例如搜索引擎数据搜索，电子邮件搜索或文本内容搜索。子字符串搜索包括几种常见格式，例如前缀和后缀搜索以及加密数据上不同长度的子字符串搜索。基于云的搜索问题尚未得到充分研究（Boldyreva和Chenette，2014; Cash等人，2014; Chase和Shen，2015; Faber等人，2015; Hahn等人，2018; Leontiadis和Li，2018; Li等人，2010; Strizhov和Ray，2015; Wang等人，2012;Yamamoto等人，2019年），因为托管成本以及搜索效率。研究贡献本文提出了双索引查询--https://doi.org/10.1016/j.jksuci.2023.02.0081319-1578/©2023作者。由Elsevier B.V.代表沙特国王大学出版。这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com●C. Ngoc Hoang，M.Hieu Nguyen，T.Thu Thi Nguyen等.沙特国王大学学报21ð●Þðð ÞðÞðSearchIndex.该模式应用于代理模型（图1），它允许在4个阶段（查询转换，索引1搜索，索引2搜索和解密数据重新查询）中搜索加密数据的子字符串。一对特殊的可搜索索引（索引1;索引 2）是基于新方法构建的在这对索引上的搜索算法也被设计成以提高查询时间、最小化错误记录、最小化数据传输和数据解密为目标第一个搜索算法应用于索引1。它使用关键字搜索方法，算法复杂度为O k，其中k是哈希函数的数量。第二搜索算法在执行第一算法时使用返回的结果集。它允许搜索基于索引2的子串，具有高精度和极低的误报率，以及具有O2m的算法复杂度，其中m为搜索子串的长度。索引数据用于提高攻击场景中的安全性理论和实验分析表明，索引1和索引 2能够抵抗统计攻击、已知明文攻击和查询模式攻击。在指标设计中使用了特殊的参数索引1;索引 2），提高了搜索算法的效率。它们还允许根据实际系统进行调整，以平衡安全性、性能和数据存储成本等因素本文的组织如下：下一节回顾了一些相关的工作。研究方法见第3节。第4节介绍了这些符号和标记。第5节提出了DIQ-SSE模式、代理模型和一种构建一对索引（索引1;索引 2）以支持搜索的方法。一种转换模式查询的设计与实现索引1;索引 2）上的子串搜索算法也在本节中给出。第六节从索引安全和模式查询两个方面讨论了模型的安全性第7介绍了该模型我们的结果也比较了其他出版物的结果。第8节进行讨论。最后，结论见第9节。2. 相关作品十多年来，加密数据一直被提及和研究。流行的SE方案可以容易地在关于可搜索对称加密（SSE）的许多出版物中找到（Cash等人，2013; Chang 和 Mitzenmacher ， 2005; Chase 和 Kamara ， 2010;Curtmola等人，2006; Goh，2003; Moataz和Shikfa，2013; Song等人，2000）以及可搜索非对称加密（PKSE）（Boneh等人，2004;Boneh等人，2007年）。一些方案基于利用数学中的性质，诸如同态或配对（Boneh等人，2007; Golle等人，2004; Hwang和Lee，2007; Lai等人，2013年; Shi等人， 2007）或者是加密数据上的模糊关键字搜索方案（Boldyreva和Chenette，2014; Li等人，2010; Wang等人，2012年）。由于子串搜索的设计复杂性、存储空间复杂性和搜索时间开销大，目前对子串搜索的研究还相当有限。多年来已经提出了一些用于搜索子串的SSE方案（Cash等人， 2014;Chase和Shen，2015; Faber等人，2015; Hahn等 人 ， 2018;Leontiadis 和 Li ，2018; Strizhov 和Ray ，2015; Yamamoto等人，2016; Yamamoto等人，2019年，可以分为两类。第一组（Chase和Shen，2015; Hahn等人，2018;Leontiadis和Li，2018; Yamamoto等人，2016）使用支持应用于密文的明文上的子串搜索的公共数据结构。 第二组（Boneh等人，二 ○ ○七年;Fig. 1. 代理模型允许查询加密的外包数据库。●C. Ngoc Hoang，M.Hieu Nguyen，T.Thu Thi Nguyen等.沙特国王大学学报22---吉吉SS不不不t ttHwang和Lee，2007）提出了新的设计和搜索思路的子串上的搜索。Chase和Shen（Chase and Shen，2015）展示了如何基于后缀树结构执行子串查询，存储成本为Ok：n，搜索复杂度为Ok：mk，其中k是安全参数，m是子串的长度，k是子串在长度为n的文本中的频率。数据通信的数量通信回合是三个，但实际上需要四个回合的通信，如文献中所示（Cash等人， 2014年）。Chase和Shen（Chase和Shen，2015）中的方法也具有在加密后泄漏与树的内部结构相关的信息的缺点;例如叶子的数量、子树的Leontiadis和Li（Leontiadis和Li，2018）通过实现一种称为FM索引的数据结构，提出了一种新的子串搜索SSE方案。它是BWT转换和后缀数组的组合，可以减少建议模式的索引大小Chase and Shen（Chase and Shen，2015）.存储成本变为O（k：n），其中k是一个非常小的隐藏常数。这个想法将文本分成kg，其中每k g（也称为作为桶）由符号表示，并且将伪组插入到原始文本中会引起噪声。这是为了隐藏数据的实际频率。在最坏的情况下，搜索成本与文本的长度On成线性关系。此外，该方案不支持查询长度小于k的子串。Strizhov和Ray（Strizhov and Ray，2015）提出了一种SSE方案，该方案支持基于给定明文数据的位置堆树因此，位置堆树的结构将包含有关明文数据的此外，该方案需要文本的逐字符组合来确定子串在文本中的位置因此，有必要为每个字符设计一个额外的索引来支持搜索过程。该索引显示字符的频率它增加了O m2D q的搜索成本，需要多达3轮的数据通信。Faber等人提出的另一种方案 （Faber等人， 2015）是支持共轭查询的可搜索对称加密方案（SSE）的扩展（Cash等人， 2014年）。它需要客户端中的指数成本增加来评估每个搜索查询的这种偏差。因此，它的主要障碍是在计算能力有限的客户端设备上实现模式。Hahn（Hahn等人，2018）提出使用称为频率隐藏保序加密（FHOPE）的特殊构造将子串搜索转换为有效的范围查询。然而，FHOPE索引的构造以及为确保性能和安全性而选择的k是一个需要在现有数据库中进行应用评估的问题。3. 方法通常，对加密数据执行查询的有效方法之一是使用可搜索索引。类似摘要针对加密字符数据的子串查询问题，提出了一种特殊的可搜索索引对，并对该索引对进行顺序查询的方法。除了参考如何建立索引和查询方法从许多以前的研究，我们还提出了建立索引，转换查询和查询的索引上的算法，并进行了单独的分析和证明，显示DIQ-SSE方案的效率。通过定量证明，从理论上证明了该研究提供了一种有效的加密字符数据子串查询解决方案，如下：- 第一个索引（Index1）是很容易建立在一个新的数据结构，能够保持更多的关键字和信息的明文。Index1支持快速确定从子字符串中提取的关键字集是否属于明文关键字集的能力。然而，索引1上的查询结果可以包括确定的假阳性记录率。- 第二个索引（Index2）是基于描述原始明文中每个字符位置的结构构建的。Index2的最大优点是它允许以非常高的准确率查询原始明文中的子串的存在。然而，存在比索引1上的算法更高的算法复杂度。- 对索引1和索引2进行了安全性分析，防止了统计攻击、已知明文攻击、查询模式攻击等攻击方法的明文信息泄露。- 查询过程完全在加密数据库中存储的索引上执行，查询顺序是在索引1上执行，然后在索引2上查询结果。- 用户和服务器之间的通信次数只有一圈。除了证明和分析新的数据结构和算法外，该研究还在TPC-H标准数据库（TPC，n.d.）上实验了所有提出的解决方案。）.我们使用DBGen工具为一个有100万条记录的LINEITEM表生成纯数据，为L_COMMENT字段构建索引1和索引2，并进行了一个三个子串长度为2的查询实验，索引1，索引2上的8，16个字符，用于验证每个阶段的过滤率，错误率和查询执行时间。对于每种类型的子串，我们随机抽取至少30个样本，并重复整个查询过程，以获得实验结果的平均值。实验结果的分析主要集中在阐明与查询性能相关的三个方面：第一，考虑索引1、索引2上查询后的过滤率和错误率，以加强对索引1、索引2上查询特性的理论证明。其次，满足查询的记录数量对过滤率和每个索引的错误率有影响。第三，从阶段的执行时间说明了使用两个索引而不是单个索引的原因。此外，它也证实了DIQ-SSE方案的优化，因为它只使用了一个sin-查询过程中的数据通信环路。超过一百万条记录的实验过程在两种环境中安装和测试：本地网络中的模拟和在云基础设施上运行，以便能够全面评估互联网传输的适用性和影响，以及DIQ-SSE方案的硬件基础设施。4. 准备工作和注释4.1. 符号关系R_ID;X_1;X_2;···;X_t;···;Xn_n与X_t是一个敏感的特征数据域。R将 被 重 构 为 关 系 RE ， 并 存 储 在 外 包 数 据 库REID;X1;X2;···;XE;···;Xn;SIX1;SIX2 中 ， 其 中 XE 是 Xt 的 加 密 字 段 ; 而XSIX1;SIX2是可搜索索引对应于Xt的对。给定As作为字符串，sKey作为私钥，则AE¼fEnc将As;sKey可以被看作是As的加密字符串，fEnc被称为加密功能类似地，f Dec被称为解密函数，并且A s^f Dec=A E; sKey=。C. Ngoc Hoang，M.Hieu Nguyen，T.Thu Thi Nguyen等.沙特国王大学学报23ðÞ.ΣS●ð Þ1/4 f···g给定As和A0s作为两个字符串，则AsjjA0s是两个给定字符串的连接。 如果X，Y的字符串存在，则A 0 s是A s的子串，其中eAs=XjjA0sjjY 。如果AT：是一个算法，那么一个←AT：可以被看作是以：作为输入参数执行算法AT给定符号jAsj作为字符串As中的字符数，如果我们有一组包含v个元素的AS。v/vV的绝对值指定为V-。假设A和B是两个集合，A[B]是A和B的并集。如果A是A的子集，则A≠B：给定Bi和Bj为具有相同大小的两个位串，两个位串的AND运算可被指派为Bi_Bj，且OR运算可被指派为Bi_Bj。右循环移位歌剧-比特串Bi的k比特的集合被分配为Bik。比特串Bi的k比特的左循环移位操作被分配为Bik。4.2. 伪随机函数定义1. 伪随机函数是一系列具有输入-输出特性的函数，事 实 上 ， 我 们 可 以 使 用 HMAC-SHA 128 和 HMAC-SHA 256（NIST，2002）等散列函数来模拟伪随机函数。4.3. 布隆过滤器布隆过滤器（Bloom filter，1970）是一个简单的结构，允许快速检查集合中一个元素的存在，误报的概率很小。布隆过滤器通过使用表示S = fs1; s2，..中的s的元素的数组m位来实现有效的存储成本。. sng.首先，数组中的位被分配为0，并且我们使用k个独立的随机散列函数h1，h2，.. . ;hka<$hiKeyi;sjs2S;i<$f1;：：;kg; 0≤a≤m-1以定义一组k个位置。然后，对于每个s2S，hi数组中的键i;s将被分配为1。要检查是否% s属于S，我们只需要检查数组中的所有位置hi Keyi;s，看看它们是否等于1。如果它们不是，则s不是S的某个成员;否则，s属于S，具有最佳的假阳性概率。定义2.具有不属于S但在位置hi=si中被值为1的比特满足的元素的假阳性概率在函数fFP中定义如下：fFP¼。1-1-1=mknk1-e-kn=mk在fFP的公式中，如果m很大，n很小，那么fFP的值就会很小。事实上，我们不能干涉n。因此，我们需要定义k个哈希函数的个数，使得fFP值尽可能小。fFP将是最小值，k<$ln 2 ωm=n。 在这种情况下，假阳性概率为fFP1= 2k1 = 0： 6185m=n。5. 建议计划5.1. 系统模型我们提出DIQ-SSE模式（GenSecretMetadata，BuildDoubleIndex，TranslateQuery和SearchIndex）如下：GenSecretMetadatak：生成安全数据MetaData（包括密钥、安全参数等）的算法它由数据所有者使用输入k执行。● BuildDoubleIndex：它包括BuildIndex1 IndexA s;MetaDataIndex和BuildIndex2 IndexA s两种算法;MetaDataIndex生成一对可搜索的索引，用于纯文本数据A s。● TranslateQuery ： 它 包 括 两 个 算 法 ： Tran1A0s;MetaData 和Tran2A0s;MetaData来转换子串查询A0s 分别为I1和I2的值，给出索引1和索引2的可搜索性。TranslateQuery● 序列号：它包括两算法ofSearchIndex1索引1;I 1索引和SearchIndex2索引2;I2索引，这允许定义A0s是否是A s的子串。在此步骤中，首先执行SearchIndex1，并返回结果集将在SearchIndex2中使用。考虑到DIQ-SSE的实用性，我们提出了一个代理模型，它由三部分组成：客户端、代理和DSP（也称为服务器端）。图1中的模型构造如下：客户端站点用于最终用户。它通过应用程序使用，以明文数据的形式输入查询数据来访问系统代理是用户和数据所有者的安全区，负责执行DIQ-SSE模型中的GenSecretMetadata和BuildDoubleIndex;TranslateQuery算法MetaData在Proxy中私下存储，如下所示：● 参数k;m;q：其中k是散列函数的数量{h1;h2;···;hkg. m是索引1的代表位串的长度。 Q是一个大素数。● Secret key密钥：用于加密和解密数据。它也是函数f Enc和f Dec中的一个参数（在此模型中，我们使用具有OFB模式的AES算法）。密钥集：它用于哈希函数（在这个模型中，我们使用SHA-256的哈希函数）：经由定义1中定义的伪随机函数生成KEY集合，其中k是秘密参数k。在算法BuildIndex1和Tran1中使用KEY集;Tran 2：● 秘密参数为u;u0和a：其中u和u0是用于创建一组距离连接字符对的参数，如5.2.1节所示。a是第5.2.2中表示的噪声参数。VA Va1;Va2;Vaz：是表示基于q的字符的秘密值的集合。参见第5.2.2。服务器站点（DSP）：存储加密数据库并执行DIQ-SSE模型中的SearchIndex1;SearchIndex 2算法5.2. 建立和存储数据索引目的是为关系R中的每个敏感明文字符串创建加密字符串和一对索引数据。 三元组AE;Index1;Index 2>存储在字段中，●C. Ngoc Hoang，M.Hieu Nguyen，T.Thu Thi Nguyen等.沙特国王大学学报241/4 f···gSð≤≤- -SSΣ ΣS联系我们SSu uuSSSS.ΣsiS一SSSSJDAu的 子集;8u0<$0 ≤u0≤. 0分。;u0≤u0。这是真实的情况下，一、s≤≤Þs¼1个;2;···;Ssi，其中AE←fEncA;sKey和As<$c 1c2···cv：敏感明文必须构建到索引1;t t ts sID：包含明文A的记录的标识;A←fDe c.AE;s Key;Index1←BuildInde x1：;Index2←BuildInde x2：。Sssm：索引1的代表位串的长度;k：哈希函数的个数;5.2.1. 构建索引1定义3. 给定A<$fa1;a2;···;azg是一组z字母表字符，As<$c1c2···cv是用KEY键1;键2;;键k：在k散列函数;u：连接字符对中字符之间的距离值;nMax：元素f的长度ElementMaxD;Az≥1;v≥1;8i1 ≤i≤v;c i2A。集合A u是一个基于A s 0 u v 2上距离u的连通字符对集合。 它的定义如下：输出.长度为m的位串BF;步长。AuAuFirstCharaterAuSingleCharaterAuPairCharaterAuLastCharater其中：(1) 建立一个集合DAu/fDW1;DW2;···;DWlg;秒/秒[秒[s]suuFirstCharaters¼ fc1jjωg(2) 对于每个关键字DW i2DAs ji2½1;l]：-一设置的值fp1;p2;·· ·;p kg是计算如下：fp1<$h1键1;DWi键;p2<$h2键2;DWi键;···;pk<$hk键k;DWi键g;AuSingleCharater fcigj1≤i≤vAuPairCharater^fcijjj-i-1jjcjgj1≤i;j≤v-1且0≤j-i-1≤u-一设置的值fq1;q2;···;q kg是计算如：fq1<$h1p1;ID;q2<$h2p2;ID;···;qk<$hkpk;IDg;- 设置BFqj 对于j2½1;k]，为1/4;(3) l是集合DAu中的项目数，t是随机数uLastCharater% s^^^在1/20范围内的数;nMax-1]：- 计算t0¼tmodm;- 计算BF BFt0;(4) 返回BF;例1. 假设给定字符串As<$$>aabcdadb}，因此，v<$48和基于As的距离u<$4 1的一组连接字符对如下给出：Au/faω;a;a;b;c;d;a;d;b;a0a;a1b;a0b;a1c;b0c;b1d;c0d;c1a;d0a;d1d;a0d;a1b;d0b;ωbg定义4. u是一组连接的字符对，5.2.2. 构建索引2定 义 5. 假 定 A<$fa1;a2;···;a zg 是 字 母 表 中 z 个 字 符 的 集 合 ， 则 As<$}c1c2·· ·cv}是基于字符的构建字符串 在 的 设置 的 一 ii≥1;v≥1;8i 1≤i≤v;ci2Ai，并且C¼ fa1;a2·· ·;a gg是一设置的杰出人物距离u在A s上。分配DA% s 作为一组有区别的连接基于As上的距离u的字符对。如果DAu只有As≤1≤g≤z;g≤v;jCjg。 分配P As¼。Pa1;Pa2;· · ·;Pag以a计表示字符位置的二进制数组的列表A的特殊项目。检察官≤。A. - 是的SSA如果：返回示例1，将DAu设置为Au表示为：Pa是一个数组，其中v位表示字符的位置DAufaω;a;b;c;d;a0a;a1b;a0b;a1c;b0c;b1d;c0d;c1a;d0a;d1d;a0d;d0b;ωbg定理1. 设DA u是一个基于距离u的可区分连通特征对集合，则所有u 0≤ u的集合DAu0都是DA u的子集。u0在字符串中记为j。As<$1≤j≤g<1、只有当？ajcv-i11≤i≤v实施例2. 构建一个二进制数组列表，该列表表示字符的字符串A saabcdadb}.然后，我们具有v/48;C/4fa;b;c;dg;g/4;16j64;a1/40a0;a2/40b0;a3/40c0;a4/40d0，PA s/4fPa;Pb; Pc; Pdg，Pa<$00100011;Pb< $10000100;Pc< $00001000;Pd< $01010000。定理2. 如果As是As的子串，则DAs永远是SS. 0分。 1（这意味着子串只有一个字符）。S定义6. 给定字符串A sc1c2···cv}，PA sPa1;Pa2;···;Pa g是表示位置的因此，我们可以使用DAu来有效地表示字符。A1gv的特征值和PAN nPaN PaN PaNo的特征值S. 集合fs1s2.. . ;SNG二进制数组的列表，表示作为噪声的位置，项目的明文和将被转化到一组u u uA s的特征。其中PN是随机位数组D^fDAs1;DAs2;···;DAsng. 在这种情况下，索引1的构建我啊啊对于Asi，将是对DAu1≤i≤n的指数 1的构建。我们可以最多有1位值使用布隆过滤器压缩DA使用si通过khash转换为m位的字符串（aisoptionalnoiseparterm0av. P N.Pai1我 g。si功能协调发展的m;k将被选择如下：(1) 将nElement定义为基于DAu的所有项的平均距离u的连接字符对的数量。(2) 根据下式选择一个整数m，其中k≥≤≤;。a.j;≤≤ Þ实施例3. 假设PAs是表示示例2中字符串As的字符位置的二进制数组列表，定义PAN如下：在第4.3中，作为k<$ln 2<$ω<$m=nElement<$。设fElementMaxD为返回最长元素的函数D组中的DA u。我们提出了一个构建索引1的算法，如下所示：输入.SPAN1/4nPaN;PbN;PcN;PdN0，具有1/42第200100011页。零件编号：00101000！产品编号<$00100011_00101000<$00101011一一明文AAS=，A一包含nGC. Ngoc Hoang，M.Hieu Nguyen，T.Thu Thi Nguyen等.沙特国王大学学报25BPb¼ 10000100;. 编号：01100000！Pb N<$10000100_01100000<$11100100C. Ngoc Hoang，M.Hieu Nguyen，T.Thu Thi Nguyen等.沙特国王大学学报26CDno1/4 f··· g我.Σ¼· ··noNNC¼fa;b;c;dg，PA¼Pa;Pb;Pc;Pd与Pa电话：+86-010 -8888888←ðÞ-不不12G不我我¼S12GS12GS1S122G12J不12zS12G¼12zG不1 2jt我我Pc<$00001000;. 编号：10000000！产品编号：<$00001000_10000000<$10001000Pd/01010000;. 编号：00000011！产品编号<$01010000_00000011<$01011011定理3. 给定字符串A0s<$}c01c02· ··c0t}和As<$}c1c2···cv}t≤vn，C<$fa1;a2···;agg是一组不同的A s和PA N¼中的字符Pa N;Pa N;···; Pa N是 一 列表 二元Asc1c2···cv}：需要构建的敏感明文索引2;q：大素数;VAVa1; Va2;;Va z ：一组秘密值，表示基于q的字母表中的z个字符;a：噪声参数;输出.表示作为As的字符的噪声的位置的数组。是位串的j位的右循环移位的结果PaN（1≤i≤g）。然后，为。1≤j≤t;c0A0s;c02C;Pc0N2PAN，weIP A组：A的索引2的代表;步骤。(1) 定义集合C¼。一个1;一个2· · ·;一个g，作为一组区分字符，i j j js0As的性质;1≤g≤v;可以得出一些关于As和As之间关系的结论：(2) BuildPAs Pa1;Pa2;;Pag;(3) 基于噪声参数a建立PA N ; Pa N ; ·· · ; Pa N。A0不是 A的子串，如果仅当(4) Build. IP As¼n.I a; IPa N;.I a; IPa N;··· ;.Iag;I aN oP c0N 1^P c0N2^ ···^P c0Nj^ ···^P c0N t1/40.● A0s是A s的子串假阳性率，如果P c0N 1^P c0N2^ ···^P c0Nj^ ···^P c0N t- 0.其中k是秘密参数;对于i¼1至g开始ki←PRFki;实施例4. 检查字符串A0s<$$>ab c}以确定它是否是A s <$} aabcdadb }的子字符串？根据示例3，我们有无无无无无无无SPbN¼11100100;PcN¼ 10001000和PdN¼01011011。基于定理3，我们计算PaN1;PbN2;PcN3;然后，我们将PaN1^PbN2^PcN3与0进行比较：Vai fvai;VA其中，fv是返回VA的集合中的Vai元素的函数;IaI 1/4 V aikiωq;IPaN¼PaNkAsVai;端PaN11/410010101;PbN2 公司简介N3¼01101011(5) 返回IPA;考虑示例4中给出的明文As}aabcdadb}，PaN¼00101011，PbN¼11100100，PcN¼10001000，PdN¼PaN1^PbN2^PcN30000001因此，我们可以得出结论，A0是A的子串。01011011. 选择质数q¼13，基数V<$20，ea<$3;eb<$1;ec<$5;ed<$4<$1 ≤e≤q= 2 Ω且k As 25%。设置基于定义7如下构建：定义7. A;a ;···;ag是 一 设置 的 z 字符 在VA14 f16; 14; 18; 17g.使用算法BuildIndex2为As构建索引2，结果可以alphabet表.给定的Q是一大Prime编号，设置Va1;Va2;···;Vazg称为表示基于q的集合A的字符的秘密值的集合，其中Vai表示ai，Vaj表示j8i;j≤i;j≤z，如果：Vai>q;Vaj>q;Vai和Vaj是整数1≤Vai-Vaj≤q=2见表1。5.3. 加密数据基于DIQ-SSE方案和图1中提出的代理查询模型，本文提出了一种新的代理查询模型. 1、查询过程中对子串A0s 在田野上在以下4个阶段执行：t t t阶段1-查询转换：转换纯文本查询数据（对字段Xt的查询）转换为对字段SIX1、SIX2的查询。这个阶段t t定义8. 给定字符字符串A s¼}c1c2···cv}和PA/4Pa N;Pa N;···;Pa N1 ≤g≤v是表示A s的字符的噪声的位置的二进制阵列的列表。给定一组一fa;a;···;a、Q是一大Prime号码，和是表示基于q的集合A的字符的秘密值的集合。字符串As的值Index2是一个集合可以在Proxy上使用。然后，将转换后的查询发送到DSP。阶段2-在索引1上搜索：在此阶段中，以高性能在字段SIX1上执行查询，该阶段在DSP上执行。阶段3-在索引2上搜索：此阶段在的IPAs¼n.我 a1; IPa N;.我a2; IPaN;···;.Iag; IPa Nowhere1≤i≤g;第二阶段返回的结果集中的第SIX2返回的并且每个项是元组Ia;IPaNa。每个元组的值都是我我将被定义为：我我表1描述索引2的结构。其中Vai2VA;ki是每个的显著随机整数。IaIIPaN¼PaNkAsVai 其中k A 是不同的随机整数明文字符索引2IaiIPaN伊伊斯全民IPaN我们提出了一个构建索引2的算法，如下所示：输入.As}aabcdadb}a00101010 01011001b00011011 1001100c01010011 00010001d10000110 01101101●C. Ngoc Hoang，M.Hieu Nguyen，T.Thu Thi Nguyen等.沙特国王大学学报27不.Σ我A AaA Aa1/4 f··· gSSu1/4 f···g.vv我. .u0我我我Ss left右下角南苏丹12不nIu0u0u0Þ.Σ结果将是一组假阳性率很小的记录此阶段在DSP执行，结果将发送到代理。阶段4其他DA0u0¼DA00;从第3阶段接收的XE列中的值，并再次重新中文（简体）南苏丹0u00在解密数据字段上。阶段4在代理中执行，返回的结果将传输到客户端站点。本文考虑子串中常见的查询条件在数据库s中搜索。假设A0 1/4abc，则三个popu-S(4) 对于每个字符串DW i2DAs：其中1≤i≤l，计算：DW transl<$fp1;p2;· ··;pk0g，其中p1<$h1Key01;DWi;p2<$4h2Key02;DWi;· · ·;pk0<$hk0Key0k0;DW i;TranTranTran最大搜索查询A0s 在具有关键字LIKE的字段Xt上包含：XtLIKE0ab cω0;XtLIKE0ωab c0;和XtLIKE0ωab cω0。5.3.1. 阶段1-查询翻译5.3.1.1. 查询转换以搜索索引1。 根据Def-在第三章中，我们称Au 和Au和Au为连通特征集，(5) 返回一组I1¼fDW 1;D W 2;· · ·;D Wl0g、注释：具有相同输入字符串A0s的Tran 1函数的输出在不同运行之间将不相同，因为u0;k0和集合KE Y0 发 生 了 变 化。5.3.1.2. 索引2上搜索的查询翻译。 根据Def-s left右下角南苏丹第8，敏感明文As的索引2被设置为IPA与基于As上从左、右和中间的距离u的其中它们被定义为：S元组Ia;IPa Na。由此，代理处的子字符串A将被转换为u uFirstCharateruSingleCharateruPairCharater¼[[一个与I ai具有相同形式的代表集 要查询在索引2上。变换算法Tran2n：n的思想可以是：s左s ss suuSingleCharateruPairCharateruLastCharaters右下角[s[sAu uSingleCharateruPairCharater被视为：算法：Tran2输入。A0s<$c01c02· · ·c0t：子串搜索;我的天啊[Asp：大素数;根据定义4，我们称DA为us left;DAu右下角 而U南苏丹VAVa1; Va2;;Va z ：设置的秘密表示z的基于q的字母表的字符;基于距离分别从左、右和中间的A上的u。输出.返回设置I2<$fIc0;Ic0;· · ·;Ic0g，其中t<$jA0sj;一个us left ;Au右下角 和u南苏丹是Au的子集，并且步骤：12TDAUs left ;DAu右下角 而U南苏丹 是DAu的子集。根据定理1(1) 集合t1/4。0分。;定理2，如果A0s是As的子串，8u00≤u0≤. 0分。;u0≤u0，则DA0;DA0和DA0是DA的子集。在此基础上，我们构建了算法Tran10：(2)转换字符串A0s一组单一的字符C1/2fc0;c0;· · ·;c0g;(3)集合I2c011/40 1≤i≤t，然后c0tc0i我二氧化 ;I如下所示算法：Tran1输入。A0s<$c01c02· ··c0t：子串搜索;类型：分类值为1或2或3;分别用于查询关键字LIKE为}A0sω}或}ωA0s}或}ωA0sω}的条件;k：哈希函数的个数;KEY键1;键2;;键k：一套钥匙;u：连接字符对中字符的距离值;输出.如下：对于i1至t开始其中k是秘密参数;Vc0i←fc0i;VA 其中f是返回VA集合中的Vaj元素的函数，其中aj^c0i1≤j≤z;我可以 ¼ V c0ik0iωq;TranTran传0返回集合I1¼fDW 1;D W 2;· ··;D Wl0g1≤i≤l，其中，每个DWtransl^fp1;p2;· ··;pk0g1≤j≤k0;1≤k0≤k;pj是整数;步(1)选取随机数u0;k0，其中0≤u0≤A0s;u0≤u;1≤k0≤k;(2) 从KEY集合中随机选择k0个密钥. 我们有一套KEY01;Key02;· · ·;Key0k0;按键0键Y;(3)检查类型的值建立DA0¼fD W 1;端(4) 返回I2;注释：Tran2函数的输出与输入字符串A相同 在不同的运行之间是不相同的，因为随机值k0i改变了。因为Vc0i>q（定义n7），那么，对于每个Ic0，将没有证据来确定Vc0i，即使攻击者知道Q。5.3.2. 阶段2 -在索引1u0DW 2;· · ·;DW0g，其中DA02fDA0u0;DA0中文（简体）u0;DA0u0g当最终用户使用ls：sleft右下角南苏丹LIKE子字符串A0<$c0c0· · ·c0的搜索条件，此命令如果类型为1，则DA0u0¼DA00;s1 2t将被移动到代理并使用算法Trans1执行，其中在查询中的条件改变为I1的集合。在DSP中，I1的集合被转换为比特串BF0，中文（简体）sleft可以在索引1中搜索将描述