一种基于前向和后向隐私的高效容错动态短语搜索方法

1.本发明属于信息安全技术及基于云的物联网
技术领域：
：，是一种基于前向和后向隐私的高效容错动态短语搜索方法，可用于在云的智能处理数据业务中。
背景技术：
：：2.近年来，云计算得到了极大的普及，因为它可以极大地降低存储成本，并且一些存储的数据由于包含敏感信息而需要适当的保护，如企业财务信息、企业税务信息、个人电子邮件、个人健康和医疗记录等。然而，数据所有者和云服务器并不总是在同一可信域，可能导致数据泄漏风险引用。由于用户无法对数据进行控制，可能会遭受来自云存储服务器供应商的内部攻击或来自黑客的外部攻击。近年来，许多公司都发生了严重的数据泄露事件。为了防止敏感数据在外包存储时泄漏，一个可能的解决方法是在外包之前加密数据。而这将与数据的可用性发生冲突，因为人们不能执行常见的操作,比如检索加密数据。3.为了安全地搜索加密数据，近年来已经开发了可搜索的加密技术。此外，当用户输入时，偶尔会出现轻微的拼写错误和格式不一致。然而，现有的可搜索加密方法大多只支持精确搜索，无法解决这种情况。解决这个问题的一种直接方法是使用拼写检查机制。但是，由于某些原因，这种方法并不适用。例如，它可能需要额外的交互，这会增加用户的计算成本。因此，为了满足这些需求，开发了模糊搜索，不仅提高了灵活性，而且还可以容忍较小的拼写和格式不一致。4.本技术提出了一种基于前向和后向隐私的高效容错动态短语搜索方法。采用混沌加密算法分段线性混沌映射和minhash函数对信息进行模糊处理，构造基于布隆过滤器索引，实现高效搜索和动态更新。基于形式化的安全证明表明，本技术具有较高的安全性和较优性能。5.本发明将布隆过滤器的变体、倒排索引和矩阵这三者相结合，设计了一种索引结构。还用轻量级加密算法对每个关键词在每个文档中的位置信息进行加密，使其实现短语搜索。安全性分析和性能分析表明本发明具有较为理想的性能。技术实现要素：6.本发明旨在解决以上现有技术的问题。提出了一种基于前向和后向隐私的高效容错动态短语搜索方法。本发明的技术方法如下：7.一种基于前向和后向隐私的高效容错动态短语搜索方法，其包括以下步骤：8.密钥生成阶段，生成密钥和公共参数；9.索引构建阶段，数据所有者使用分段线性混沌映、and-or结构级联的minhash函数、布隆过滤器、倒排索引和矩阵设计了一种索引结构；10.陷门生成阶段，用户利用短语生成陷门；11.短语搜索阶段，云服务器检查存储的加密索引，并返回中间加密结果；用户收到后，将其解密，并将获取的文件标识符返回给云服务器；云服务器返回响应的加密文件，用户解密文件；12.更新令牌生成阶段，用户生成令牌发送给云服务器；13.索引更新阶段，云服务器根据令牌更新索引和文档。14.进一步的，所述密钥生成阶段，生成密钥和公共参数，具体包括：15.(1)给定安全参数β，从同一个局部敏感哈希函数族里随机选取k×λ个minhash函数h1，选取密钥生成算法skgen()，选取两个单项散列函数h2和h3；16.(2)sk1←skgen(1β)，sk2←skgen(1β)，sk3←skgen(1β)，认证用户之后，通过安全信道将sk2分别传送给云服务器和用户，将sk1,sk3通过安全信道传送给用户；密钥为{sk1,sk2,sk3}，公共参数为{k,λ,h1,h2,h3}。17.进一步的，所述piecewiselinearchaoticmap具体包括：18.piecewiselinearchaoticmap(pwlcm)被描述为：[0019][0020]其中，xn∈(0,1),p∈(0,0.5)。xn为第n次得到的函数值，xn-1为第n-1次得到的函数值，f[xn-1]表示输入值为xn-1的函数值，p表示一个小数，f(1-xn-1)为输入值为1-xn-1的函数值。[0021]进一步的，所述and-or结构的minhash函数，具体包括：[0022]minhash是一种lsh函数族，它用于jaccard距离，minhash对集合中的每个元素使用随机hash函数，并选取所有hash值中的最小值；[0023]满足以下两个条件的hash函数称为(d1,d2,p1,p2)-sensitive:[0024](1)如果d(x,y)≤d1，则h(x)＝h(y)的概率至少为p1；[0025](2)如果d(x,y)≥d2，则h(x)＝h(y)的概率至多为p2；[0026]其中，d(x,y)表示x和y之间的距离度量；d1表示情况(1)的距离，d2表示情况(2)的距离，p1表示情况(1)下的概率，p2表示情况(2)下的概率。[0027]而and和or操作的级联可以生成更多的hashtable，使p1更接近于1，p2接近于0；[0028]使用k个随机函数实现and结构后，其结构表示为g＝(h1,h2,...,hk)；h1,h2,...,hk分别表示k个不同的哈希函数算出的哈希值。此时，若g(x)＝g(y)当且仅当g(x)、g(y)分别表示输入值分别为x、y时得到的k个哈希值。然后使用λ个不同的and结构实现or结构，其结构表示为f＝(g1∨g2∨...∨gλ)；此时，若f(x)＝f(y)当且仅当由此，可以将(d1,d2,p1,p2)-sensitive函数族变为(d1,d2,p1’,p2’)-sensitive函数族，其中p1’,p2’分别表示经过and和or操作的级联得到的不同的概率。[0029]进一步的，所述布隆过滤器由一个m位的二进制向量和许多随机映射函数组成，它主要用于查找一个元素是否存在于某个集合中，它是将元素用过随机映射函数映射到二进制向量中来操作的。[0030]进一步的，所述索引构建阶段具体包括：[0031]对每个wi∈wd,i∈[1,λ]，wd为关键词集合，λ为关键词集合中的关键词个数；(1)将wi的每个字母ψa的ascii码值使用单向hash函数映射成[0，1]内的小数，a∈[1,y]，y为wi的字母的个数，再将该值使用分段线性混沌映射算法映射到区间[0,s]的整数，s为minhash的秘密参数，得到的一组整数为关键词wi的编码，将该编码作为minhash的输入；[0032](2)使用and-or结构和从同一个局部敏感哈希函数族里随机选取k×λ个minhash函数，分别对wi进行运算，得到k×λ个值xi,j∈[1,m],i∈[1,λ],j∈[1,λ]，这k×λ个值形成k个hashtable，假设哈希不发生碰撞，将其中每个值xi,j映射到一个大小为m的数组γ，m＞|wd|×k×λ，m表示数组γ的大小，wd为关键词集合。[0033](3)将变为1，数组γ中和随机γ[xi,υ]对应的桶指向一个大小为|d|的数组f＝《f1,...,fi，...,f|d|》，i∈[1,λ],υ∈[1,k×λ]∧υ≠a×λ 1)，其中每个元素为一个链表，链表的第一个元素包含文档标识符id(dk)和指向下一个元素的指针，若标识符为id(dk)的文档包含关键词wi，则链表fi＝《id(dk),fk,1,...,fk,j,...,fk,t》,i∈[1,|d|],k∈[1,|d|],j∈[1,t]，其中t为关键词wi在标识符为id(dk)的文档中的位置个数，poskj表示关键词wi在标识符为id(dk)的文档中的第j次出现的位置，若标识符为id(dk)的文档不包含关键词wi，则在链表fi中填充v个随机无效字符，v∈[1,θ]；θ表示v的取值的最大数。[0034](4)使用sk1对文档集合d进行对称加密ζ←encdoc(sk1,d)；[0035](5)数据所有者将索引γ和加密文档集合ζ送给云服务器。[0036]进一步的，所述短语搜索阶段，具体包括：[0037](1)对于云服务器，收到用户发来的陷门t后，[0038]①生成一个列表ct，存储用户名和计数器值ctserver，设ctserver的初始值为0，每收到一次该用户的搜索查询，ctserver的值加1；[0039]②判断h2(ctserver,sk2)＝＝h2(ctuser,sk2)是否成立，若不成立，则返回用户“查询失败”，若成立，则对于索引中的每一个桶的位置loc计算loc表示索引中每一个桶的位置，表示使用loc得到的哈希值。[0040]③对于每个wi∈q，选取第一个hashtable中的λ个值，根据y与的值是否相等，将其映射到数组γ中的值，并判断是否成立；若不成立，依次判断k个hashtable，只要有一个hashtable能成立，则进行第④步；[0041]④若其中一个hashtable成立，则对于xi,a*λ 1表示第i个关键词使用了哈希函数得到的第a*λ 1个哈希值，即它就是数组γ中对应的桶的位置，a∈[0,k-1]，取出其所指向的数组f；[0042]⑤按照查询的顺序，将所有取出的数组发送给用户；[0043](2)用户收到云服务器发送的数组后，对于收到的每个数组的每个元素fkj：[0044]①使用式子(1)计算得出关键词wi在文档中的位置或者一个随机数，[0045][0046]得到加密之前的数组；[0047]②用户将得到的所有数组进行运算，判断在同一个文档中要查询的关键词的位置是否是相连的，计算得到文档标识符集r＝{id(di),i∈[1,n]}；用户将r发送给云服务器；[0048](3)云服务器收到回应后，将对应的文档的密文发送给用户；[0049](4)用户使用密钥sk1对收到的密文进行解密，得到要查询的文档明文。[0050]进一步的，所述更新令牌生成阶段，具体包括：[0051](1)添加文档：数据所有者对要添加的文档用第二步建立索引一样的方法生成一个子索引γ*，将γ*和加密文档ξ*作为更新令牌发送给云服务器；操作类型up＝“add”；[0052](2)删除文档：数据所有者对要删除的文档di,i∈[1,n]，将文档di的标识符id(di)作为更新令牌发送给云服务器。操作类型up＝“delete”；[0053](3)修改文档：操作类型up＝“modify”；[0054]①添加某个文档的关键词：数据所有者对要修改的文档di,i∈[1,n]，提取出di对应的一个|wd|×k维的行向量，将要添加的关键词对应的fi(i∈[1，n])中的随机数改为该关键词的位置，并用加密；另外，选取个包含随机数的对应链表，选择v(v∈[1,θ])个随机数，替换原链表元素，此时选取的v与原链表的个数可能不相同；将这个新生成的子索引γ*和加密文档ξ*作为更新令牌发送给云服务器；此操作一次可以添加同一个文档中的多个关键词；[0055]②删除某个文档的关键词：数据所有者对要修改的文档di,i∈[1,n]，提取出di对应的一个|wd|×k维的行向量，在要删除的关键词对应的fi(i∈[1，n])中将原关键词位置的加密数据用v(v∈[1,θ])个随机数替换；另外，选取个包含随机数的对应链表，选择v(v∈[1,θ])个随机数，替换原链表元素，此时选取的v与原链表的个数可能不相同；将这个新生成的子索引γ*和di的标识符id(di)作为更新令牌发送给云服务器；此操作一次可以删除同一个文档中的多个关键词。[0056]进一步的，所述索引更新阶段，具体包括：[0057](1)添加文档：云服务器收到后，分别将γ*和ξ*添加到γ和ξ中；[0058](2)删除文档：云服务器收到后，将γ中对应的链表删除，并根据id(di)将加密文档集合ζ中对应的文档di删除；[0059](3)修改文档：云服务器收到后，分别将γ*和ξ*替换γ和ξ中对应的位置。[0060]本发明的优点及有益效果如下：[0061]本发明提出一种基于前向和后向隐私的高效容错动态短语搜索方法。它具有前向隐私和后向隐私，并且支持模糊短语搜索和动态更新。具体来说，本文的创新点有：利用了混沌加密算法分段线性混沌映射和and结构和or结构级联的minhash函数来实现模糊搜索；还使用了布隆过滤器的变体和矩阵构建索引，实现了短语搜索和动态更新。本文的创新主要在于索引的构建、搜索阶段和动态更新阶段的实现。现有的方法中，使用混沌加密算法分段线性混沌映射来实现模糊搜索的方法是很少出现的。同时，在现有的短语搜索的方法中使用矩阵存储位置信息这一方法是不常见的。2-9的技术的巧妙之处在于将混沌加密算法分段线性混沌映射、and结构和or结构级联的minhash函数、布隆过滤器和矩阵的结合使用，实现了前向隐私、后向隐私、短语搜索和动态更新。在实现这些功能时，保证了本方法的效率也比一般的模糊搜索的方法高。[0062]本发明是基于前向和后向隐私的高效容错动态短语搜索方法，用轻量级加密算法对每个关键词在每个文档中的位置信息进行加密，使其实现短语搜索。并且在搜索时ftps能快速找到相应的位置，从而使搜索效率更加高效。同时实现了前向隐私和后向隐私，有较好的安全性。附图说明[0063]图1是本发明提供优选实施例的关键词编码；[0064]图2是本发明的索引结构图；[0065]图3是本发明的ct表；[0066]图4是基于前向和后向隐私的高效容错动态短语搜索方法示意图。具体实施方式[0067]下面将结合本发明实施例中的附图，对本发明实施例中的技术方法进行清楚、详细地描述。所描述的实施例仅仅是本发明的一部分实施例。[0068]本发明解决上述技术问题的技术方法是：[0069]下面结合附图1、2、3对本发明比特币交易模型做进一步的详细描述。具体的包括以下模块和步骤：[0070]1)分段线性混沌映射piecewiselinearchaoticmap：[0071]piecewiselinearchaoticmap(pwlcm)：混沌具有许多有趣的特性，例如良好的伪随机性和对其控制参数的敏感性，可以直接与密码术中混淆和扩散的属性相关联。并且这些系统是确定性的，也就是说，它们的未来行为不会有随机元素，完全由其参数确定。但是，由于混沌信号是伪随机的，未经授权的用户可能会将它认作噪声。[0072]混沌加密算法分利用了混沌的确定性、混合性、内随机性等特点,在保障安全性的前提下,实现简单、加密快速。[0073]pwlcm作为最简单的混沌加密算法之一，同样拥有这些特性。它可被描述为：[0074][0075]其中，xn∈(0,1),p∈(0,0.5)。xn为第n次得到的函数值，xn-1为第n-1次得到的函数值，f[xn-1]表示输入值为xn-1的函数值，p表示一个小数，f(1-xn-1)为输入值为1-xn-1的函数值。[0076]2)and-or结构的minhash函数：[0077]minhash是一种lsh函数族，它用于jaccard距离。minhash对集合中的每个元素使用随机hash函数，并选取所有hash值中的最小值。[0078]localitysensitivehashing(lsh)是一种用于解决在高维空间中查找相似节点问题的技术。如果直接在高维空间中进行线性查找，将面临维度灾难，并且效率十分低，而lsh的作用就是把原来高维空间上的点都映射到一个或多个hashtable的不同的位置上，这个位置术语上称作桶(buckets)。它在映射两个接近的高维空间的点时，有很大概率将这两个点映射到同一个桶中，也就是说，在同一个桶中的点在高维空间中很可能是接近的。由此可以根据这一特点进行查找，从而提高查找的效率。[0079]满足以下两个条件的hash函数称为(d1,d2,p1,p2)-sensitive:[0080](1)如果d(x,y)≤d1，则h(x)＝h(y)的概率至少为p1；[0081](2)如果d(x,y)≥d2，则h(x)＝h(y)的概率至多为p2。[0082]其中，d(x,y)表示x和y之间的距离度量。d1表示情况(1)的距离，d2表示情况(2)的距离，p1表示情况(1)下的概率，p2表示情况(2)下的概率。[0083]而and和or操作的级联可以生成更多的hashtable，使p1更接近于1，p2接近于0。[0084]使用k个随机函数实现and结构后，其结构表示为g＝(h1,h2,...,hk)。h1,h2,...,hk分别表示k个不同的哈希函数算出的哈希值。此时，若g(x)＝g(y)当且仅当g(x)、g(y)分别表示输入值分别为x、y时得到的k个哈希值。然后使用λ个不同的and结构实现or结构，其结构表示为f＝(g1∨g2∨...∨gλ)。此时，若f(x)＝f(y)当且仅当由此，可以将(d1,d2,p1,p2)-sensitive函数族变为(d1,d2,p1’,p2’)-sensitive函数族，其中p1’,p2’分表表示经过and和or操作的级联得到的不同的概率。[0085]3)布隆过滤器：[0086]布隆过滤器由一个m位的二进制向量和许多随机映射函数组成。它主要用于查找一个元素是否存在于某个集合中，它是将元素用过随机映射函数映射到二进制向量中来操作的。它的查找时间快，需要的存储空间小，但有一定的误识别率，且很难执行删除操作。[0087]本方法分为六个阶段，如图4所示，分别为密钥生成阶段、索引建立阶段、陷门生成阶段、短语搜索阶段、更新令牌生成阶段、索引更新阶段。具体如下。[0088]密钥生成阶段：[0089](1)给定安全参数β，从同一个局部敏感哈希函数族里随机选取k×λ个minhash函数h1，选取密钥生成算法skgen()，选取两个个单项散列函数h2和h3。[0090](2)sk1←skgen(1β)，sk2←skgen(1β)，sk3←skgen(1β)。认证用户之后，通过安全信道将sk2分别传送给云服务器和用户，将sk1,sk3通过安全信道传送给用户。密钥为{sk1,sk2,sk3}，公共参数为{k,λ,h1,h2,h3}。[0091]索引建立阶段：对每个wi∈wd,i∈[1,λ](wd为关键词集合，λ为关键词集合中的关键词个数)，[0092](1)将wi的每个字母ψa(a∈[1,y]，y为wi的字母的个数)的ascii码值使用单向hash函数映射成[0，1]内的小数，再将该值使用piecewiselinearchaoticmap(pwlcm)算法映射到区间[0,s]的整数(s为minhash的秘密参数)。得到的一组整数为关键词wi的编码，将该编码作为minhash的输入，如图1。[0093](2)使用and-or结构和从同一个局部敏感哈希函数族里随机选取k×λ个minhash函数，分别对wi进行运算，得到k×λ个值xi,j∈[1,m],i∈[1,λ],j∈[1,λ]，这k×λ个值形成k个hashtable。将其中每个值xi,j映射到一个大小为m的数组γ(m＞wd|×k×λ，假设哈希不发生碰撞)。m表示数组γ的大小，wd为关键词集合。[0094](3)将变为1，数组γ中和随机个对应的桶指向一个大小为|d|的数组f＝《f1,...,fi，...,f|d|》，其中每个元素为一个链表。链表的第一个元素包含文档标识符id(dk)和指向下一个元素的指针。若标识符为id(dk)的文档包含关键词wi，则链表fi＝《id(dk),fk,1,...,fk,j,...,fk,t》,i∈[1,|d|],k∈[1,|d|],j∈[1,t]，其中t为关键词wi在标识符为id(dk)的文档中的位置个数，poskj表示关键词wi在标识符为id(dk)的文档中的第j次出现的位置。若标识符为id(dk)的文档不包含关键词wi，则在链表fi中填充v个随机无效字符，v∈[1,θ]。θ表示v的取值的最大数。索引结构如图2。[0095](4)使用sk1对文档集合d进行对称加密ζ←encdoc(sk1,d)。[0096](5)数据所有者将索引γ和加密文档集合ζ送给云服务器。[0097]陷门生成阶段：查询q＝{w1,...,wb}，b为查询q中的关键词个数。[0098](1)生成一个计数器表ct，它有两个列：username和ctuser，其中ctuser的初始值为0，并且每次同一用户向cs发送搜索查询时，向ctuser加1。，设其初始值为0，同一个用户每向云服务器发送一次搜索查询，其值加1。[0099](2)对于每个wi∈q，计算k个大小为λ的hashtable:y1＝h2(xi,1,ctuser,sk2),...,yk×λ＝h2(xi,k×λ,ctuser,sk2)，其中xi,1＝h1(wi),...,xi,k×λ＝hk×λ(wi)。[0100](3)陷门t＝{y1,1,...,yb,k×λ,h2(ctuser,sk2)}。[0101]短语搜索阶段：[0102](1)对于云服务器，收到用户发来的陷门t后，[0103]①生成一个列表ct(如图3)，存储用户名和计数器值ctserver，设ctserver的初始值为0，每收到一次该用户的搜索查询，ctserver的值加1。[0104]②判断h2(ctserver,sk2)＝＝h2(ctuser,sk2)是否成立，若不成立，则返回用户“查询失败”，若成立，则对于索引中的每一个桶的位置loc计算loc表示索引中每一个桶的位置，表示使用loc得到的哈希值。[0105]③对于每个wi∈q，选取第一个hashtable中的λ个值，根据y与的值是否相等，将其映射到数组γ中的值，并判断是否成立。若不成立，依次判断k个hashtable，只要有一个hashtable能成立，则进行第④步。[0106]④若其中一个hashtable成立，则对于xi,a*λ 1表示第i个关键词使用了哈希函数得到的第a*λ 1个哈希值，即它就是数组γ中对应的桶的位置，a∈[0,k-1]，取出其所指向的数组f。[0107]⑤按照查询的顺序，将所有取出的数组发送给用户。[0108](2)用户收到云服务器发送的数组后，对于收到的每个数组的每个元素fkj：[0109]①使用式子(1)计算得出关键词wi在文档中的位置或者一个随机数，[0110][0111]得到加密之前的数组。[0112]②用户将得到的所有数组进行运算，判断在同一个文档中要查询的关键词的位置是否是相连的。计算得到文档标识符集r＝{id(di),i∈[1,n]}。用户将r发送给云服务器。[0113](3)云服务器收到回应后，将对应的文档的密文发送给用户。[0114](4)用户使用密钥sk1对收到的密文进行解密，得到要查询的文档明文。[0115]更新令牌生成阶段：[0116](1)添加文档：数据所有者对要添加的文档用第二步建立索引一样的方法生成一个子索引γ*，将γ*和加密文档ξ*作为更新令牌发送给云服务器。操作类型up＝“add”。[0117](2)删除文档：数据所有者对要删除的文档di,i∈[1,n]，将文档di的标识符id(di)作为更新令牌发送给云服务器。操作类型up＝“delete”。[0118](3)修改文档：操作类型up＝“modify”。[0119]①添加某个文档的关键词：数据所有者对要修改的文档di,i∈[1,n]，提取出di对应的一个|wd|×k维的行向量，将要添加的关键词对应的fi(i∈[1，n])中的随机数改为该关键词的位置，并用加密。另外，选取个包含随机数的对应链表，选择v(v∈[1,θ])个随机数，替换原链表元素，此时选取的v与原链表的个数可能不相同。将这个新生成的子索引γ*和加密文档ξ*作为更新令牌发送给云服务器。此操作一次可以添加同一个文档中的多个关键词。[0120]②删除某个文档的关键词：数据所有者对要修改的文档di,i∈[1,n]，提取出di对应的一个|wd|×k维的行向量，在要删除的关键词对应的fi(i∈[1，n])中将原关键词位置的加密数据用v(v∈[1,θ])个随机数替换。另外，选取个包含随机数的对应链表，选择v(v∈[1,θ])个随机数，替换原链表元素，此时选取的v与原链表的个数可能不相同。将这个新生成的子索引γ*和di的标识符id(di)作为更新令牌发送给云服务器。此操作一次可以删除同一个文档中的多个关键词。[0121]索引更新阶段：[0122](1)添加文档：云服务器收到后，分别将γ*和ξ*添加到γ和ξ中。[0123](2)删除文档：云服务器收到后，将γ中对应的链表删除，并根据id(di)将加密文档集合ζ中对应的文档di删除。[0124](3)修改文档：云服务器收到后，分别将γ*和ξ*替换γ和ξ中对应的位置。[0125]还需要说明的是，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、商品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、商品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、商品或者设备中还存在另外的相同要素。[0126]以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或修改，这些等效变化和修饰同样落入本发明权利要求所限定的范围。当前第1页12当前第1页12