(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210473281.7 (22)申请日 2022.04.29 (71)申请人 太原理工大 学 地址 030024 山西省太原市迎泽西大街79 号 (72)发明人 蔚晓玲　徐磊　黄鑫　许春根　 (74)专利代理 机构 太原高欣科创专利代理事务 所(普通合伙) 14109 专利代理师 崔浩　冷锦超 (51)Int.Cl. H04L 9/08(2006.01) H04L 9/32(2006.01) H04L 9/30(2006.01) H04L 9/06(2006.01) H04L 9/40(2022.01) (54)发明名称 基于格的前向安全的密文数据检索方法 (57)摘要 本发明提供了基于格的前向安全的密文数 据检索方法， 属于信息安全技术领域； 所要解决 的技术问题 为： 提供基于格的前向安全的密文数 据检索方法的改进； 解决上述技术问题采用的技 术方案为： 主要由系统初始化、 密钥更新算法、 关 键词加密算法、 令牌生成算法、 测试算法五个步 骤组成； 采用格结构构造了密文数据检索方案， 可以实现抗量子计算的攻击； 同时可实现前向安 全性， 降低了因用户密钥泄露带来的隐私保护问 题， 使得系统更加安全； 方案结合二叉树结构与 最小覆盖集实现数据接收方私钥的更新， 无需公 钥随之更新， 降低了存储开销， 且可以实现对密 钥更新的查询下的安全性， 弥补了同类方案的缺 陷； 本发明应用于密文数据检索。 权利要求书3页 说明书8页 附图1页 CN 114844634 A 2022.08.02 CN 114844634 A 1.基于格的前向安全的密文数据检索方法， 其特 征在于： 包括如下步骤： S1： 系统初始化阶段： 设置安全参数、 二叉树结构的层数， 预定义关键词域， 运行格陷门 生成算法， 输出系统公共参数、 数据接收方的公钥和私钥， 并将上述公钥、 私钥发送给接收 方， 设置hash函数及随机均匀选取矩阵； S2： 密钥更新阶段： 输入系统公共参数， 根据接收方的公钥和与当前时间段相关的私 钥， 结合二叉树结构与最小覆盖集合， 利用格基扩展算法， 实现时间段的更新并计算下一个 时间段的接收方私钥实现密钥更新， 生成的私钥由接 收方秘密保存， 同时删除当前时间段 的私钥； S3： 关键词加密阶段： 数据发送方输入要加密的关键词， 利用接收方的公钥和时间段， 根据格LWE的基于身份的加密思想计算与关键词关联的密文第一个分量； 根据时间段选取相应的随机矩阵组成与当前时间段关联的矩阵， 然后依据LWE上的基 于身份加密思想计算与关键词关联的密文第二个分量； 将两个密文分量所组成的关键词密文发送给云服 务器； S4： 令牌生成阶段： 接收方输入想要搜索的关键词和接收方当前时段的私钥， 采用格原 像抽样算法抽取一个向量作为本时间段的搜索令牌， 将上述令牌作为接收方的搜索请求 发 送给服务器； S5： 测试阶段： 服务器将接收到的关键词密文拆分为密文第一个分量与密文第二个分 量， 将两个分量与搜索令牌结合计算一个噪声项， 将上述噪声项的值与 比较， 若噪声小于 输出1， 返回搜索结果给数据接收方， 表明服务器测试搜索令牌中包含的关键词与密文 中一致， 且搜索令牌是在关键词加密后的时间段生成的； 否则输出0， 此次搜索失败； 其中q 为系统参数。 2.根据权利要求1所述的基于格的前向安全的密文数据检索方法， 其特征在于： 所述步 骤S1系统初始化阶段的具体步骤如下： S1.1： 设置参数： 设系统安全参数为n， 所使用二叉树结构的层 数为l， 设置系统参数q＝ ploy(n)是素数， m＝O(nlogq)， 设置 ψα是离散高斯噪声 分布， 其中α 是高斯分布参数； 为保证 原像抽样算法正常运行， 设置原像抽样算法的安全参数为σ； S1.2： 设置函数： hash函数： S1.3： 均匀随机 选择2l个n ×m矩阵： S1.4： 运行格陷门生成算法计算数据接收方的公钥、 私钥： 运行格陷门生成算法 TrapGen(n,m,q)生成一个均匀随机矩阵 和格Λ⊥(A0)的基 S1.5： 构建系统公共参数为 数据接收方的 公钥pk＝A0， 接收方的私钥 3.根据权利要求2所述的基于格的前向安全的密文数据检索方法， 其特征在于： 所述步权　利　要　求　书 1/3 页 2 CN 114844634 A 2骤S2密钥更新阶段的具体步骤如下： 输入公共参数p p， 公钥pk和时间段t的私钥skt： S2.1： 定义叶子节点的最小覆盖集： 对于二叉树上任意叶子节点t， 一个最小覆盖Node (t)表示包含时间t之后的所有叶子结点的一个祖先节点的最小集合， 即{t,t+1,...,T ‑1}， 其中T是时间段的数量； S2.2： 时间段t的私钥skt的组成： 根据二叉树各节点的格陷门生成方法， 二叉树的每个 节点有自己对应的矩阵及其格陷门， 时间段t的私钥skt是由集合Node(t)的所有元素节点 的格陷门组成的陷门集 合； S2.3： 从skt到skt+1的密钥更新： 接收方首先确定最小覆盖Node(t+1)， 然后计算集合 Node(t+1)\Node(t)的所有节点的格陷门， 并删除集合Node(t)\Node(t+1)的所有节点的格 陷门， 最后， 接收方确定更新后的私钥； S2.4： 返回更新后的私钥skt+1。 4.根据权利要求3所述的基于格的前向安全的密文数据检索方法， 其特征在于： 所述步 骤S2.2的二叉树各节点的格陷门生成的具体步骤如下： S2.2.1： 设置二叉树： 设置l层的二叉树结构， 其从左到右的叶子结点分别代表时间段t ∈{0,1,. ..,2l‑1}； S2.2.2： 对二叉树各个节点设置标记： 对于每个时间段t， t为叶子节点， 标记为其唯一 从根节点到该叶子结点的路径t＝(t1,...,tl)， 其中对于第i层， 如果该节点是左节 点， 则ti ＝0； 若该节点 为右节点， 则ti＝1； 类似地， 对于第i层 结点Θ(i)， Θ(i)为非叶子结点， i≠l， 根据从根节点到该结点的唯一 路径记作Θ(i)＝( θ1,..., θi)， 其中θi∈{0,1}的定义与ti一致； S2.2.3： 设置根节点 的对应矩阵及其格陷门： 运行TrapGen(n,m,q)算法获得根节点 的 对应矩阵为随机矩阵 和格Λ⊥(A0)的陷门 步骤2.2.4： 设置各节点的对应矩阵： 定义 Θ(i)的对应矩阵为 时间段t的对应矩阵为 对于i∈{1 ,2 ,...,l}与b∈{0 , 1}， 是均匀随机 选取的矩阵； S2.2.5： 计算各节点矩阵对应的格陷门： 对于二叉树上的任一节点Θ(i)， 对应陷门记作 采用格基扩展ExtBasis算法， 选择以下两种方式之一实现计算得到； 给定根节点陷门 按照如下 方式计算陷门 其中 或者 也能够通过其任意祖 先的陷门计算， 方法如下： 假设给定 权　利　要　求　书 2/3 页 3 CN 114844634 A 3