(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210562457.6 (22)申请日 2022.05.23 (71)申请人 北京理工大 学 地址 100081 北京市海淀区中关村南大街5 号 (72)发明人 祝烈煌　张璨　徐畅　丁瑶玲　 (74)专利代理 机构 北京正阳理工知识产权代理 事务所(普通 合伙) 11639 专利代理师 张利萍 (51)Int.Cl. G06F 21/60(2013.01) G06F 21/62(2013.01) G06F 16/901(2019.01) (54)发明名称 一种支持加密道路网络图的标签范围查询 方法 (57)摘要 本发明涉及一种支持加密道路网络图的标 签范围查询方法， 属于车联网及隐私保护技术领 域。 本方法根据车联网场景中针对道路交通网络 的标签范围查询特点， 为道路网络图数据构建了 高效的范围查询索引与混淆关键词哈希表， 实现 了支持加密 道路网络图的高效标签范围查询。 通 过使用对称加密、 PCDD方案等密码学原语， 对明 文形式的道路网络图进行加密， 并对明文形式的 标签范围查询请求进行加密混淆。 与车联网中现 有的基于明文的道路网络图标签范围查询方案 相比， 本方法实现了对道路网络图数据拥有者的 数据隐私保护和用户的查询隐私保护。 和基于安 全多方计算、 不经意传输、 茫然存储等复杂密码 学原语的图隐私保护方案相比， 本方法实现了高 效查询。 权利要求书3页 说明书8页 附图1页 CN 115186276 A 2022.10.14 CN 115186276 A 1.一种支持加密道路网络图的标签范围查询方法， 其特 征在于， 包括以下步骤： 步骤1： 数据拥有者 生成密钥并进行分发； 数据拥有者拥有道路网络图数据， 道路网络图数据表示为G＝(V,E)， V代表道路网络图 的顶点集合， E代表道路 网络图的边集合， V中的每一个点 都有一个对应的关键词， 关键词的 集合为W； 步骤1.1： 数据拥有者随机生成两个密钥K0和K； 步骤1.2： 采用具有分布式解密的公钥加密 方案， 简称PCDD方案， 生成一个强私钥和m+1 个公私钥对， m表示用户数； 步骤1.3： 将K0、 K和第i个公私钥对， 通过安全信道发送给用户i； 将第m+1个公私钥对作 为自己使用的公私钥对， 并将K0、 K和私钥秘密保存； 步骤1.4： 使用PCDD方案的强私钥拆分算法， 将强私钥拆分为两个部分私钥； 将步骤1.2 中生成的所有m+1个公钥和步骤1.3中拆分得到的第一个部分私钥通过安全信道发送给云 服务器A， 将m+1个公钥和第个二部 分私钥通过安全信道发送给云服务器B； 其中， 云服务器A 和云服务器B是两个 独立的云服 务器； 步骤2： 数据拥有者对道路网络图进行加密； 预先给定一个范围阈值的最大值， 生成一个范围索引RI； 之后， 使用密码学原语对生成 的范围索引进行加密； 在用户执行查询时， 只要其设定的范围阈值小于系统设定的阈值最 大值即可； 步骤2.1： 初始化 一个空的加密 索引和一个值 为0的混淆关键词哈希 表； 步骤2.2： 对道路网络图数据G的顶点集合V中的每个顶点， 找到与该顶点的距离不超过 给定阈值 最大值中的所有顶点， 并构造范围索引RI； 步骤2.3： 利用顶点集合V和关键词集合W， 生成对应的关键词字典D； 关键词字典D中给 出了V中的每 个顶点分别对应关键词集 合W中的哪个关键词； 步骤2.4： 生成加密 索引； 对顶点集合V中的每个顶点v∈V， 生成和该顶点v相关联的加密范围索引项， 将其添加 到加密索引中； 步骤2.5： 生成混淆关键词哈希 表； 对关键词集合W中的每个关键词， 将混淆关键词哈希表中与该关键词相关联的索引项 置为1； 步骤2.6： 数据拥有者将加密 索引和混淆关键词哈希 表发送到云服 务器A； 步骤3： 用户生成标签范围查询令牌； 用户生成标签范围查询请求q， q＝(s,w, θ )， s代表用户当前所在的源顶点， w代表需要 查询的关键词， θ为范围阈值， 且θ不大于所允许的查询阈值最大值； 之后， 用户利用从数据 拥有者处得到的密钥对查询请求进行加密混淆， 得到密文形式的查询令牌； 步骤4： 云服 务器响应查询请求， 并返回密文形式的查询结果； 当收到用户的查询令牌后， 两个云服务器A和B共 同合作， 执行基于加密道路网络图的 标签范围查询操作， 向用户返回密文形式的查询结果； 步骤5： 用户恢复出明文形式的查询结果； 当收到云服务器A发来的查询结果集合后， 用户对查询结果进行解密， 恢 复出明文形式权　利　要　求　书 1/3 页 2 CN 115186276 A 2的查询结果。 2.如权利要求1所述的一种支持加密道路网络图的标签范围查询方法， 其特征在于， 步 骤2.4包括以下步骤： 步骤2.4.1： 使用对称加密算 法对顶点v加密， 密钥为步骤1.1中生成的密钥K0， 得到加密 后的顶点； 步骤2.4.2： 对范围索引RI中的每个和顶点v相关联的范围索引 项进行加密； 每个范围 索引项包括中间顶点u， 以及u到v之间的距离d。 3.如权利要求2所述的一种支持加密道路网络图的标签范围查询方法， 其特征在于， 步 骤2.4.2包括以下步骤： 步骤2.4.2.1： 使用对称加密算 法对中间顶点u加密， 密钥为步骤1.1中生成的密钥K0， 得 到加密后的中间顶点； 步骤2.4.2.2： 使用PCDD方案中的加密算法对距离d加密， 密钥为步骤1.1中生成的数据 拥有者的公钥， 得到加密后的距离； 步骤2.4.2.3： 将加密后的中间顶点和加密后的距离， 作为加密范围索引 项， 并添加到 加密索引中。 4.如权利要求1所述的一种支持加密道路网络图的标签范围查询方法， 其特征在于， 步 骤2.5包括以下步骤： 步骤2.5.1： 使用关键词和步骤1.3中生成的密钥K， 计算第一索引密钥和第二索引密 钥； 步骤2.5.2： 对字典D中和关键词相关联的每个顶点， 生成混淆后的关键词索引， 将混淆 关键词哈希 表中索引对应的值置为1。 5.如权利要求4所述的一种支持加密道路网络图的标签范围查询方法， 其特征在于， 步 骤2.5.2包括以下步骤： 步骤2.5.2.1： 使用对称加密算法对顶点进行加密， 密钥为步骤1.1中生成 的密钥K0， 得 到加密后的顶点； 步骤2.5.2.2： 使用第一索引密钥和加密后的顶点生成第一索引， 使用第二索引密钥和 加密后的顶点 生成第二索引； 步骤2.5.3.3： 将混淆关键词哈希 表中第一索引和第二索引对应的值置为1。 6.如权利要求4所述的一种支持加密道路网络图的标签范围查询方法， 其特征在于， 步 骤3包括以下步骤： 步骤3.1： 使用对称加密算 法对源顶点 s加密， 密钥为步骤1.1中生成的密钥K0， 得到加密 后的源顶点； 步骤3.2： 使用关键词w和步骤1.1中生成的密钥K， 计算第一索引密钥和第二索引密钥； 步骤3.3： 使用PCDD方案中的加密算法， 对范围阈值θ进行加密， 密钥为步骤1.3中由数 据拥有者发来的用户的公钥， 得到加密后的范围阈值； 步骤3.4： 将 “加密后的源顶点， 第一索引密钥， 第二索引密钥， 加密后的范围阈值 ”作为 查询令牌， 并发送给云服 务器A。 7.如权利要求4所述的一种支持加密道路网络图的标签范围查询方法， 其特征在于， 步 骤4包括以下步骤：权　利　要　求　书 2/3 页 3 CN 115186276 A 3