(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210408193.9 (22)申请日 2022.04.19 (71)申请人 北京理工大 学 地址 100081 北京市海淀区中关村南大街5 号 (72)发明人 祝烈煌　张璨　徐畅　张诗珧　 丁瑶玲　 (74)专利代理 机构 北京正阳理工知识产权代理 事务所(普通 合伙) 11639 专利代理师 张利萍 (51)Int.Cl. G06F 21/60(2013.01) G06F 21/62(2013.01) H04L 9/00(2022.01) H04L 9/32(2006.01)H04L 9/40(2022.01) H04L 67/10(2022.01) H04L 67/12(2022.01) (54)发明名称 车联网中支持标签范围查询的道路交通网 络图加密方法 (57)摘要 本发明提出了车联网中支持标签范围查询 的道路交通网络图加密方法， 属于车联网与图加 密技术领域。 本发明使用分布式解密的公钥加密 方法， 对距离值进行加密， 并利用对称密钥加密 密码系统和伪随机函数对顶点信息和关键词信 息进行加密与混淆处理。 云服务器的所有操作均 在密文数据下进行， 因此无法知 道图数据的原始 信息以及用户的当前位置、 进行标签范围查询的 关键词和对应范围， 保护了图数据的隐私和用户 的查询隐私。 本发明支持车联网场景下对加密 道 路交通网络图的标签范围查询， 具有很强的实用 性。 本发明提出的图加密方法， 对范围阈值没有 限制， 同时加密与存储成本较低， 可以实现100％ 的查询准确率。 权利要求书4页 说明书9页 附图1页 CN 115080989 A 2022.09.20 CN 115080989 A 1.车联网中支持标签范围查询的道路交通网络图加密方法， 其特征在于， 包括以下步 骤： 步骤1： 可信机构进行系统初始化； 步骤1.1： 根据给定的安全参数， 随机生成两个长度和安全参数相同的共享密钥， 分别 为K0和K； 步骤1.2： 设有m个车联网用户， 可信机构使用具有分布式解密的公钥加密方法生成一 个强私钥， 并将其拆 分为两个部 分A和B； 可信机构为数据拥有者和m个用户生成各自的公私 钥对， 总共生成m+1个公私钥对； 步骤1.3： 通过安全信道， 向图数据所有者和用户发送密钥K0和K， 以及步骤1.2生成的公 私钥对； 每 个用户拥有独立且不同于图数据所有者和其 他用户的公私钥对； 步骤1.4： 将步骤1.2中拆分出的强私钥 的A部分以及所有的公钥， 发送给一号云服务 器； 将拆分出的强私钥的B部分以及所有的公钥， 发送给二 号云服务器； 步骤2： 图数据所有者加密道路交通网络图数据； 步骤2.1： 图数据所有者基于自己拥有的道路交通网络图数据， 提取出顶点集合中每个 点对应的关键词， 得到一个关键词集 合； 其中， 道路交通网络 图数据包括一个顶点集合与一个边集合， 其中点集合中的每个顶 点都对应至少一个关键词， 边 集合中记录着顶点之间的联通关系； 步骤2.2： 图数据所有者 生成道路交通网络图的两 跳覆盖标签索引； 步骤2.3： 对顶点集合中的每个顶点v， 首先使用对称加密算法对v加密， 其中密钥为步 骤1.3中由可信机构发送给图数据所有者的密钥K0； 之后， 对与顶点v相关联的所有两跳覆盖标签项进行加密， 生成一个与顶点v相关联的 加密标签项集 合； 当点集合中所有顶点均生成相关联的加密标签项集合后， 图数据 所有者将得到整个图 的加密标签； 其中， 每个两跳覆盖标签项由一个中间顶点u以及顶点与中间顶 点之间的距离 d构成； 步骤2.4： 对步骤2.1中生成的关键词集合中的每个关键词w进行混淆处理， 构造加密字 典； 最终， 图数据所有者得到一个通过步骤2.3生成的加密标签和一个通过步骤2.4生成的 加密字典； 步骤3： 用户生成标签范围查询令牌； 步骤3.1： 用户生成一个标签范围查询请求， 其中包 含源点、 关键词和阈值； 步骤3.2： 通过步骤1.3中由可信机构发送给用户的密钥K0对查询请求中的源点进行加 密， 得到加密后的节点； 步骤3.3： 使用查询请求中的关键词和步骤1.3中由可信机构发送给用户的密钥K， 生成 索引混淆密钥和关键词异或密钥； 步骤3.4： 使用步骤1.2中的具有分布式解密的公钥加密 方法， 对阈值进行加密， 其中密 钥为步骤1.3中由可信机构发送给用户的公钥； 步骤3.5： 生成查询令牌， 令牌中包括加密顶点、 索引混淆密钥、 关键词异或密钥、 加密 后的阈值； 之后， 将查询令牌 通过路旁 单元发送给一 号云服务器；权　利　要　求　书 1/4 页 2 CN 115080989 A 2步骤4： 云服 务器执行基于密文的标签范围查询； 当一号云服务器接收到查询令牌后， 和二号云服务器共同执行基于密文的标签范围查 询； 步骤5： 用户解密查询结果列表； 用户使用步骤1.3中由可信机构发送给用户的私钥， 对查询结果列表中的顶点信息进 行解密； 之后， 使用步骤1.3中由可信机构发送给用户的密钥K0进行再次解密， 恢复明文形式的 查询结果。 2.如权利要求1所述的车联网中支持标签范围查询的道路交通网络图加密方法， 其特 征在于， 步骤2.3包括以下步骤： 步骤2.3.1： 使用对称加密算法对中间顶点u进行加密， 其中， 密钥为步骤1.3中由可信 机构发送给图数据所有者的密钥K0； 步骤2.3.2： 使用步骤1.2所述的具有分布式解密的公钥加密方法中的加密算法， 对顶 点与中间顶点之间的距离d加密， 其中， 密钥为步骤1.3中由可信机构发送给图数据所有者 的公钥； 步骤2.3.3： 将步骤2.3.1中对u加密的结果和步骤2.3.2中对d加密的结果， 添加到顶点 v相关联的加密标签项集 合中。 3.如权利要求1所述的车联网中支持标签范围查询的道路交通网络图加密方法， 其特 征在于， 步骤2.4包 含如下步骤： 步骤2.4.1： 使用步骤1.3中由可信机构发送给图数据所有者的密钥K， 生成索引混淆密 钥和关键词异或密钥； 步骤2.4.2： 初始化 一个计数器， 值 为0； 步骤2.4.3： 对和关键词w相关联的所有顶点进行混淆。 4.如权利要求3所述的车联网中支持标签范围查询的道路交通网络图加密方法， 其特 征在于， 步骤2.4.3包 含如下步骤： 步骤2.4.3.1： 利用步骤2.4.1中的索引混淆密钥和关键词异或密钥和步骤2.4.2中的 计数器， 分别生成索引和关键词异或子密钥； 步骤2.4.3.2： 使用对称加密算法对顶点进行加密， 其中， 密钥为步骤1.3中由可信机构 发送给图数据所有者的密钥K0； 步骤2.4.3.3： 向加密字典中添加数据， 索引为步骤2.4.3.1中生成的索引， 值为将步骤 2.4.3.1中生成的关键词异或子密钥与步骤2.4.3.2中加密后的顶点信息进行异或后的结 果。 5.如权利要求1所述的车联网中支持标签范围查询的道路交通网络图加密方法， 其特 征在于， 步骤4包 含如下步骤： 步骤4.1： 一号云服务器将查询令牌解析为四部分： 加密顶点、 索引混淆密钥、 关键词异 或密钥、 加密后的阈值； 步骤4.2： 一 号云服务器初始化 一个临时集 合， 并初始化 一个计数器， 其 值为0； 步骤4.3： 一号云服务器使用计数器和索引混淆密钥计算索引， 在步骤2.4生成并上传 到一号云服务器的加密字典中查找索引对应的值；权　利　要　求　书 2/4 页 3 CN 115080989 A 3