(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210030502.3 (22)申请日 2022.01.12 (71)申请人 重庆邮电大 学 地址 400065 重庆市南岸区南 山街道崇文 路2号 (72)发明人 周由胜　刘可馨　刘媛妮　 (74)专利代理 机构 重庆市恒信知识产权代理有 限公司 5 0102 专利代理师 刘小红 (51)Int.Cl. H04L 9/00(2022.01) H04L 9/08(2006.01) H04L 9/32(2006.01) G06F 16/33(2019.01) (54)发明名称 一种基于前向和后向隐私的高效容错动态 短语搜索方法 (57)摘要 本发明请求保护一种基于前向和后向隐私 的高效容错动态短语搜索方法， 包含数据所有 者、 云服务器和用户。 包括以下步骤： 密钥生成阶 段， 生成密钥和公共参数。 索引构建阶段， 数据所 有者使用分段线 性混沌映射、 AND ‑OR结构级联的 minhash函数、 布隆过滤器、 倒排索引和矩阵设计 了一种索引结构。 陷门生成阶段， 用户利用短语 生成陷门。 短语搜索 阶段， 云服务器检查存储的 加密索引， 并返回中间加密结果。 用户收到后， 将 其解密， 并将获取的文件标识符返回给云服务 器。 云服务器返回响应的加密文件， 用户解密文 件。 更新令牌生成阶段， 用户生成令牌发送给云 服务器。 索引更新阶段， 云服务器根据令牌更新 索引和文档。 本发明实现了 前向隐私、 后向隐私、 高效搜索和动态更新。 权利要求书4页 说明书9页 附图3页 CN 114531220 A 2022.05.24 CN 114531220 A 1.一种基于前向和后向隐私的高效容错动态短语搜索方法， 其特征在于， 包括以下步 骤： 密钥生成阶段， 生成密钥和公共参数； 索引构建阶段， 数据所有者使用分段线性混沌映射、 AND ‑OR结构级联的minhash函数、 布隆过滤器、 倒排索引和矩阵设计了一种索引结构； 陷门生成阶段， 用户利用短语生成陷门； 短语搜索阶段， 云服务器检查存储的加密索引， 并返回中间加密结果； 用户收到后， 将 其解密， 并将获取的文件标识符返回给云服务器； 云服务器返回响应的加密 文件， 用户解密 文件； 更新令牌 生成阶段， 用户生成令牌发送给云服 务器； 索引更新阶段， 云服 务器根据令牌更新索引和文档。 2.根据权利要求1所述的一种基于前向和后向隐私的高效容错动态短语搜索方法， 其 特征在于， 所述密钥生成阶段， 生成密钥和公共参数， 具体包括： (1)给定安全参数β， 从同一个局部敏感哈希函数族里随机选取k ×λ个minhash函数H1， 选取密钥生成算法SKGen()， 选取两个单项散列函数H2和H3； (2)sk1←SKGen(1β)， sk2←SKGen(1β)， sk3←SKGen(1β)， 认证用户之后， 通过安全信道将 sk2分别传送给云服务器和用户， 将sk1,sk3通过安全信道传送给用户； 密钥为{sk1,sk2, sk3}， 公共参数为{k, λ,H1,H2,H3}。 3.根据权利要求2所述的一种基于前向和后向隐私的高效容错动态短语搜索方法， 其 特征在于， 所述分段线性混沌映射具体包括： Piecewise Linear Chaotic Map(PWLCM)被描述 为： 其中， 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的函数值。 4.根据权利要求3所述的一种基于前向和后向隐私的高效容错动态短语搜索方法， 其 特征在于， 所述AND ‑OR结构的mi nhash函数， 具体包括： minhash是一种LSH函数族， 它用于Jaccard距离， Minhash对集合中的每个元素使用随 机hash函数， 并选取 所有hash值中的最小值； 满足以下两个条件的hash函数称为(d1,d2,p1,p2) ‑sensitive: (1)如果d(x,y)≤d1， 则h(x)＝h(y)的概 率至少为p1； (2)如果d(x,y)≥d2， 则h(x)＝h(y)的概 率至多为p2； 其中， d(x,y)表示x和y之间的距离度量； d1表示情况(1)的距离， d2表示情况(2)的距 离， p1表示情况(1)下的概 率， p2表示情况(2)下的概 率； 而AND和OR操作的级联 可以生成更多的hash  table， 使p1更接 近于1， p2接 近于0；权　利　要　求　书 1/4 页 2 CN 114531220 A 2使用k个随机函数实现AND结构后， 其结构表示为g＝(h1,h2,...,hk)； h1,h2,...,hk分别 表 示 k 个 不同 的 哈 希 函 数 算 出 的 哈 希 值 。此 时 ， 若 g (x) ＝ g (y) 当 且 仅 当 g(x)、 g(y)分别表示输入值分别为x、 y时得到的k个哈希值； 然后使 用 λ个不同的AND结构实现OR结构， 其 结构表示为 此时， 若f(x)＝f(y) 当且仅当 由此， 可以将(d1,d2,p1,p2) ‑sensitive函数族变为 (d1,d2,p1 ’,p2’)‑sensitive函数族， 其中 p1’,p2’分表 表示经过AND和OR操作的级联 得到的不同的概 率。 5.根据权利要求4所述的一种基于前向和后向隐私的高效容错动态短语搜索方法， 其 特征在于， 所述布隆过滤器由一个m位的二进制向量和许多随机映射函数组成， 它主要用于 查找一个元素是否存在于某个集合中， 它是将元素用过随机映射函数映射到二进制向量中 来操作的。 6.根据权利要求5所述的一种基于前向和后向隐私的高效容错动态短语搜索方法， 其 特征在于， 所述索引构建阶段 具体包括： 对每个wi∈WD,i∈[1,Λ]， WD为关键词集 合， Λ为关键词集 合中的关键词个数； (1)将wi的每个字母ψa的ASCII码值使用单向hash函数映射成[0， 1]内的小数， a∈[1, Y]， Y为wi的字母的个数， 再将该值使用Piecewise  Linear Chaotic Map(分段混沌线性映 射)算法映射到区间[0,s]的整数， s为minhash的秘密参数， 得到的一组整数为关键词wi的 编码， 将该编码作为mi nhash的输入； (2)使用AND ‑OR结构和从同一个局部敏感哈希函数族里随机选取k ×λ个minhash函数， 分别对wi进行运算， 得到k ×λ个值xi,j∈[1,m],i∈[1,Λ],j∈[1, λ]， 这k ×λ个值形成k个 hash table， 假设哈希不发生碰撞， 将其中每个值xi,j映射到一个大小为m的数组γ， m＞|WD |×k×λ， m表示数组γ的大小， WD为关键词集 合。 (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的取值的最大 数； (4)使用sk1对文档集 合D进行对称加密 ζ ←EncDoc(sk1,D)； (5)数据所有者将索引γ和 加密文档集 合ζ送给云服 务器。 7.根据权利要求6所述的一种基于前向和后向隐私的高效容错动态短语搜索方法， 其 特征在于， 所述短语搜索阶段， 具体包括： (1)对于云服 务器， 收到用户发来的陷门T后， ①生成一个列表CT， 存储用户名和计数器值ctserver， 设ctserver的初始值为0， 每收到一权　利　要　求　书 2/4 页 3 CN 114531220 A 3