(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202211022951.X (22)申请日 2022.08.25 (65)同一申请的已公布的文献号 申请公布号 CN 115098649 A (43)申请公布日 2022.09.23 (73)专利权人 北京融数联智科技有限公司 地址 100088 北京市西城区新 街口外大街 28号C座2层23 5号 (72)发明人 韩宗达　邓宇涛　陈剑　 (74)专利代理 机构 北京卓岚智财知识产权代理 有限公司 1 1624 专利代理师 沈煜华 (51)Int.Cl. G06F 16/33(2019.01) G06F 21/60(2013.01)G06F 21/62(2013.01) 审查员 谢小诗 (54)发明名称 基于双密钥不经意伪 随机函数的关键词搜 索方法和系统 (57)摘要 本发明提供基于双密钥不经意伪 随机函数 的关键词搜索方法和系统， 该方法包括： 持有方 生成比特串B； 查询方生成第一密钥k1、 第二密钥 k2和第一密钥矩阵R， 根据k1、 k2和第一密钥矩阵 R对第一关键词集合加密， 得到密文矩阵A； 持有 方根据比特串B、 第一密钥矩阵R和密文矩阵A， 得 到第二密钥矩阵C； 查询方将k1和k2发送给持有 方； 持有方根据k1、 数据库中的第二关键词集合 和第二密钥矩阵C获得键密文向量Mx， 并且根据 k2、 第二关键词集合和第二密钥矩阵C获得值密 文向量Mv； 持有方将键密文向量和值密文向量发 送给查询方； 查询方根据第一关键词集合、 k1、 k2、 R、 Mx和Mv， 获得多个查询目标值y。 其可实现 计算轻量 化。 权利要求书5页 说明书14页 附图3页 CN 115098649 B 2022.11.22 CN 115098649 B 1.基于双 密钥不经意伪随机函数的关键词搜索方法， 其特 征在于， 包括： S1： 数据持有方 预先随机生成比特串 （B） ， 以作为后续 不经意传输中的选择向量； S2： 数据查询 方随机生成第一密钥 （k1） 、 第二密钥 （k2） 和第一密钥矩阵 （R） ， 根据所述 第一密钥 （k1） 、 所述第二密钥 （k2） 和所述第一密钥矩阵 （R） 对待查询的第一关键词集合加 密， 得到所述第一关键词集 合对应的密文矩阵 （A） ； S3： 所述数据持有方与所述数据查询方执行不经意传输协议， 所述数据持有方根据所 述比特串 （B） 、 所述第一密钥矩阵 （R） 和所述密文矩阵 （A） ， 得到第二密钥矩阵 （C） ； S4： 所述数据查询方将所述第一密钥 （k1） 和所述第二密钥 （k2） 发送给所述数据持有 方； S5： 所述数据持有方根据所述第一密钥 （k1） 、 数据持有方的数据库中的第二关键词集 合和所述第二密钥矩阵 （C） 获得键密文向量 （Mx） ， 并且根据所述第二密钥 （k2） 、 所述第二关 键词集合和所述第二密钥矩阵 （C） 获得值密文向量 （Mv） ； S6： 所述数据持有方将所述键密文向量 （Mx） 和所述值密文向量 （Mv） 发送给所述数据查 询方； S7： 所述数据查询方根据所述第一关键词集合、 所述第一密钥 （k1） 、 所述第二密钥 （k2） 、 所述第一密钥矩阵 （R） 、 所述键密文向量 （Mx） 和所述值密文向量 （Mv） ， 获得对 应于所述 第一关键词集 合的多个查询目标值 （y） ； 所述比特串 （B） 的长度为 w； 步骤S2具体包括： S21： 数据查询方生成一个大小为 的第一密钥矩阵 （R） ， 其中n为数据持有方的数 据集的大小； S22： 所述数据查询 方根据所述第一密钥 （k1） 、 所述第二密钥 （k2） 、 所述第一关键词集 合、 预设的二值矩阵 （D） 和所述第一密钥矩阵 （R） ， 得到所述第一关键词 集合对应的密文矩 阵 （A） ； 步骤S22包括： S221： 所述数据查询方初始化所述 二值矩阵 （D） 为全1矩阵； S222： 所述数据查询方使用所述第一密钥 （k1） 分别加密所述第一关键词集合 中的每个 关键词， 得到多个第一关键词密文， 切分所述多个第一关键词密 文为多个第一密文 段， 确定 多个第一密文段对应的多个第一置零位置， 将所述二值矩阵 （D） 中与所述多个第一置零位 置相对应的位置的数值赋值 为0； S223： 所述数据查询方使用所述第二密钥 （k2） 分别加密所述第一关键词集合 中的每个 关键词， 得到多个第二关键词密文， 切分所述多个第二关键词密 文为多个第二密文 段， 确定 多个第二密文段对应的多个第二置零位置， 将所述二值矩阵 （D） 中与所述多个第二置零位 置相对应的位置的数值赋值 为0； S224： 所述数据查询方将经处理后的二值矩阵 （D ’） 与所述第一密钥矩阵 （R） 进行异或 操作， 得到所述密文矩阵 （A） 。 2.根据权利要求1所述的方法， 其特 征在于， 步骤S3具体包括： 所述数据查询方将所述第一密钥矩阵 （R） 和所述密文矩阵 （A） 作为 不经意传输的输入； 所述数据持有方将长度为w的比特串 （B） 作为不经意传输的选择向量， 每次不经意传输权　利　要　求　书 1/5 页 2 CN 115098649 B 2以二进制形式的比特串 （B） 的第j位数作为选择数， 在所述第一密钥矩阵 （R） 的第 j列和所述 密文矩阵 （A） 的第 j列中选择一列作为所述数据持有 方生成的第二密钥矩阵 （C） 的第 j列， 经 过w次不经意传输得到 完整的所述第二密钥矩阵 （C） 。 3.根据权利要求1所述的方法， 其特 征在于， 步骤S5具体包括： 所述数据持有方接收由所述数据查询方传输的所述第一密钥 （k1） 和所述第二密钥 （k2） ， 分别使用所述第一密钥 （k1） 、 所述第二密钥 （k2） 对数据库中的第二关键词集合进行 加密， 对应得到多个第三关键词密文以及多个第四关键词密文； 所述数据持有方切分所述多个第 三关键词密文为多个第 三密文段， 以每个第 三密文段 作为索引逐一将所述第二密钥矩阵 （C） 中与当前的第三密 文段对应的第一关联位置的值取 出， 将取出的值拼接形成所述第二关键词集合在所述第二密钥矩阵 （C） 中映射的多个键密 文 （mx1） ， 组合所有键密文 （mx1） 得到键密文向量 （Mx） ； 所述数据持有方切分所述多个第四关键词密文为多个第四密文段， 以每个第四密文段 作为索引逐一将所述第二密钥矩阵 （C） 中与当前的第四密 文段对应的第二关联位置的值取 出， 将取出的值拼接形成所述第二关键词集合在所述第二密钥矩阵 （C） 中映射的多个值密 文 （mx2） ， 使用映射的多个值密文 （mx2） 对数据库中的值进行加密得到值密文 （mv） ， 组合所有 值密文 （mv） 得到值密文向量 （Mv） 。 4.根据权利要求3所述的方法， 其特 征在于， 步骤S7 具体包括： 所述数据查询方切分所述第 一关键词密文为多个第 一密文段， 以每个第 一密文段作为 索引逐一将所述第一密钥矩阵 （R） 中与当前的第一密文段对应的第三关联位置的值取出， 将取出的值组合形成所述第一关键词集合在所述第一密钥矩阵 （R） 中映射的第五关键词密 文 （r1x） ； 所述数据查询方切分所述第 二关键词密文为多个第 二密文段， 以每个第 二密文段作为 索引逐一将所述第一密钥矩阵 （R） 中与当前的第二密文段对应的第四关联位置的值取出， 将取出的值组合形成所述第一关键词集合在所述第一密钥矩阵 （R） 中映射的第六关键词密 文 （r2x） ； 所述数据查询方在所述键密文向量 （Mx） 中寻找与所述第五关键词密文 （r1x） 相同的子 密文， 确定所述第五关键词密文 （r1x） 在所述键密文向量 （Mx） 中的目标位置， 并从所述值密 文向量 （Mv） 中取出对应所述目标位置的值密 文 （mv） ， 使用所述第六关键词密文 （r2x） 对所述 值密文 （mv） 进行解密， 最终得到所求的多个查询目标值 （y） 。 5.基于双密钥不经意伪随机函数的关键词搜索系统， 其特征在于， 包括数据持有方和 数据查询方； 所述数据持有方包括： 预处理模块， 用于预 先随机生成比特串 （B） ， 以作为后续 不经意传输中的选择向量； 第一不经意传输模块， 用于与所述数据查询方执行不经意传输协议， 根据所述比特串 （B） 、 第一密钥矩阵 （R） 和密文矩阵 （A） ， 从所述数据查询方处选择 得到第二密钥矩阵 （C） ； 第一接收模块， 用于 接收由所述数据查询方发送的第一密钥 （k1） 和第二密钥 （k2） ； 键值密文向量生成模块， 用于根据所述第一密钥 （k1） 、 数据库中的第二关键词集合和 所述第二密钥矩阵 （C） 获得键密文向量 （Mx） ， 并且根据所述第二密钥 （k2） 、 第二关键词集合 和所述第二密钥矩阵 （C） 获得值密文向量 （Mv） ；权　利　要　求　书 2/5 页 3 CN 115098649 B 3