(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211106644.X (22)申请日 2022.09.13 (71)申请人 哈尔滨工业大 学 （深圳） （哈尔滨工 业大学深圳科技创新研究院） 地址 518055 广东省深圳市南 山区桃源街 道深圳大 学城哈尔滨工业大 学校区 (72)发明人 王轩　金磊　蒋琳　刘洋　漆舒汉　 姚霖　罗文坚　 (74)专利代理 机构 广州市华学知识产权代理有 限公司 4 4245 专利代理师 李斌 (51)Int.Cl. G01C 21/34(2006.01) H04L 67/12(2022.01) H04L 9/00(2022.01)H04L 9/40(2022.01) (54)发明名称 基于同态加密和匿名伪装的导航服务隐私 保护方法及装置 (57)摘要 本发明公开了一种基于同态加密和匿名伪 装的导航服务隐私保护方法及装置， 方法包括： LBS服务商进行同态加密方案的初始化； 用户利 用匿名伪装算法分别生成出匿名伪装区域； 用户 根据匿名伪装区域的路网信息， 随机选取出发点 附近满足伪装距离L的出发地伪装点和目的地伪 装点， 同步规划出真实出发地到伪装 出发地的路 线； 云服务商 规划出一组候选路线， 同时 向LBS服 务商请求实时路况信息； 云服务商对候选路线组 的开销进行进一步计算， 利用全同态加密的比较 运算， 将密文比较结果传输给LBS服务商； 从候选 路线组中选取最佳路线并在本地将和伪装区域 内的路线连接， 生成最终的出行路线。 本发明采 用全同态加密和匿名伪装技术实现高质量的导 航服务隐私保护。 权利要求书3页 说明书13页 附图2页 CN 115200603 A 2022.10.18 CN 115200603 A 1.基于同态加密和匿名伪装的导 航服务隐私保护方法， 其特 征在于， 包括下述 步骤： 由LBS服务商进行同态加密 方案的初始化、 生成公钥pk、 私钥sk和评估密钥evk， 然后将 初始化参数param s、 公钥pk和评估密钥evk发送给云服 务商进行初始化； 用户利用匿名伪装算法分别生成出匿名伪装区域， 并向云服务商请求该匿名伪装区 域， 云服务商收到匿名伪装区域请求后， 将该匿名伪装区域的路网信息传输给用户； 所述匿 名伪装区域包括出发地匿名伪装区域和目的地匿名伪装区域； 所述匿名伪装算法是基于K ‑ 匿名算法进行改造， 将K ‑匿名算法前置条件满足的K个在线用户改变成随机生成的K个坐 标； 用户根据匿名伪装区域的路网信息， 随机选取出发点附近满足伪装距离L的出发地伪 装点和目的地伪装点， 并将该出发地伪装点和目的地伪装点发送给云服务商； 同时根据匿 名伪装区域的路网信息， 同步 规划出真实出发地到伪装出发地的路线； 云服务商收到出发地伪装点和目的地伪装点后， 规划出一组候选路线{ w1,…，wn}， 其中 w1,…，wn分别代表一条候选路线， 同时向LBS服务商请求候选路线涉及 路网区域R的实时路 况信息， LBS服 务商将路网区域R的实时路况信息利用全同态公钥加密后传输给云服 务商； 云服务商收到路网区域R加密后的实时路况信 息， 并根据实时路况信 息， 对之前的候选 路线组的开销进行进一步计算， 得到密文后的路线开销， 利用全同态加密的比较运算， 将 每 条路线相互比较， 将密文比较结果传输给LBS服 务商； LBS服务商收到密文比较结果， 利用私钥sk进行解密， 并对比较结果进行排序， 获得最 佳路径的序号， 将该序号传输给用户； 用户收到序号， 将从候选路线组{ w1,…，wn}中选取的 最佳路线在本地和伪装区域内的路线连接， 生成最终的出 行路线。 2.根据权利要求1所述基于同态加密和匿名伪装的导航服务隐私保护方法， 其特征在 于， 所述匿名伪装算法具体为： 用户拥有出发地经纬度坐标S， 目的地经纬度坐标D， 设定伪装距离L、 伪装等级K； 用户基于伪装距离L和伪装等级K， 在半径L处生成K ‑1个随机坐标。 3.根据权利要求1所述基于同态加密和匿名伪装的导航服务隐私保护方法， 其特征在 于， 所述根据匿名伪装区域的路 网信息， 同步规划出真实出发地到伪装出发地的路线， 具体 为： 在本地加载地图后， 采取调用用户系统内部的常规路径规划算法， 分别生成从真实出 发地到伪装出发地以及从伪装目的地到真实目的地的两条导 航路线。 4.根据权利要求1所述基于同态加密和匿名伪装的导航服务隐私保护方法， 其特征在 于， 所述候选路线通过 下述方法进行规划： 根据路径规划的策略要求， 生成一条距离最短的路线， 再根据道路的限速生成一条用 时最短的路线， 这是两条基础路线； 增加定制化的策略， 策略包括避免收费、 费用最少、 不走高速路或不走快速路， 进而生 成多条定制路线； 在用户允许的前提下， 云服 务商在服 务结束后进行路线的优化， 具体流 程如下： 当用户允许时， 收集并存储所有请求的路径规划{伪装出发地S， 伪装目的地D， 发起时 间T}三元组集 合； 在第二天的同一时间T， 由云服务商请求LBS服务商进行{伪装出发地S， 伪装目的地D}权　利　要　求　书 1/3 页 2 CN 115200603 A 2的路径规划， 生成导 航路线； 在收到LBS服务商的路线后， 对比自己根据策略选出的路线， 找出不同之处， 找出首次 出现分叉后的地图节点， 标记为中继点； 在下一次涉及到匿名伪装区域内的路线时， 将该中继点加入路径规划， 生成多组经过 中继点的导航路线{伪装出发地， 中继点 1， 伪装目的地}， …， {伪装出发点， 中继点n， 伪装目 的地}。 5.根据权利要求1所述基于同态加密和匿名伪装的导航服务隐私保护方法， 其特征在 于， 所述LBS服务商将路网区域R的实时路况信息利用全同态公钥加密传输给云服务商， 具 体为： 所述LBS服务商收到来自云服务商 的路网区域R的实况地 图信息请求， LBS服务商将对 应地图数据结构中每条边 edge的路况权重加密， 整个地图的其他数据结构不会进行加密， 再将路网区域R的实时路况地图数据结构传送给云服 务商， 由云服 务商解析使用。 6.根据权利要求1所述基于同态加密和匿名伪装的导航服务隐私保护方法， 其特征在 于， 所述根据实时路况信息， 对之前的候选 路线组的开销进 行进一步计算， 得到密 文后的路 线开销， 具体为： 云服务商收到来自LBS 服务商的权重信息后， 将自己生成的候选路线组{ w1,…，wn}中的 每一条路线都进行开销计算， 所述开销计算具体为： 每一条候选路线由多条边 edge连接起 来， 将第i条边edgei的距离长度利用公钥加密为密文长度信息 enc(edgei.len)， 再获取来自 LBS服务商的地图数据中这条边 edgei的密文权重信息 enc(edgei.weight)， 将enc (edgei.len)和enc(edgei.weight)做密文乘法运算， 得到该条边 edgei的开销， 再将每条边 的密文乘法结果累加起 来， 得到该 条候选路线； 计算完所有路线后， 得到最终每条路线的开销结果。 7.根据权利要求1所述基于同态加密和匿名伪装的导航服务隐私保护方法， 其特征在 于， 所述LBS服务商收到密文比较结果， 利用私钥sk进行解密， 并对比较结果进 行排序， 获得 最佳路径的序号， 具体为： 根据隐私要求 不同， 当隐私等级为K时， 对于当前候选路线数目N>2K时， 采取 “淘汰制”: （1） 候选路线组中的候选路线两两采用密文比较算法进行密文比较运算， 得到N/2个比 较结果密文， 将比较结果密文传输给LBS服 务商进行解密； （2） LBS服务商解密后得到N/2个比较结果明文， 再将比较结果 明文传输云服务商， 云服 务商将开销过 大的路线 进行剔除； （3） 令N=N/2， 如果 N>2K， 重复 （1） ‑（2） 步骤的过程， 如果 N<=2K,执行第 （4） 步； （4） 将候选路线组中候选路线的开销， 每条候选路线依次与其他候选路线比较一次， 得 到 个比较结果密文,构造开销的比较结果序列； （5） LBS服务商在解密 个开销的比较结果序列后， 根据明文比较结果， 对N条候选 路线进行排序， 获得开销最小候选路线的序号。 8.基于同态加密和匿名伪装的导航服务隐私保护系统， 其特征在于， 包括预处理模块、 伪装区域生成模块、 伪装点选取模块、 路径规划模块、 路线开销计算模块以及路径生成模权　利　要　求　书 2/3 页 3 CN 115200603 A 3