(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210999099.5 (22)申请日 2022.08.19 (71)申请人 西安电子科技大 学 地址 710071 陕西省西安市太白南路2号 (72)发明人 王祥宇　叶子恺　韩沛霖　龚晨　 马建峰　苗银宾　马鑫迪　 (74)专利代理 机构 西安嘉思特知识产权代理事 务所(普通 合伙) 6123 0 专利代理师 王丹 (51)Int.Cl. G06F 21/60(2013.01) G06F 21/62(2013.01) (54)发明名称 一种加密的混合索引树的生成及隐私保护 的时空接 触查询方法 (57)摘要 本发明公开了一种加密的混合索引树的生 成及隐私保护的时空接触查询方法， 方法包括： 获取多组原始时空数据， 每组原始时空数据包括 原始空间位置数据和原始时间数据； 采用希尔伯 特曲线对原始空间位置数据编码， 得到包含空间 编码数据和原始时间数据的多组时空处理数据； 生成每组时空处理数据的空间编码数据的前缀 编码族； 将每组时空处理数据、 每组时空处理数 据的前缀编码族， 作为混合索引树的叶子节点； 通过对不同前缀编码族合并， 自底向上逐层生成 非叶子节 点； 每个父节点包含其所有孩子节点的 前缀编码族或合并编码族； 分别生成每个叶子节 点、 每个非叶子节点的布隆过滤器， 得到混合索 引树； 对布隆过滤器加密， 得到加密的混合索引 树。 权利要求书4页 说明书10页 附图7页 CN 115391803 A 2022.11.25 CN 115391803 A 1.一种加密的混合索引树的生成方法， 其特 征在于， 包括： 获取多个对象的多组原始时空数据； 每组原始时空数据包括原始空间位置数据， 以及 与所述原 始空间位置数据对应的原 始时间数据； 采用希尔伯特曲线， 对所述原始空间位置数据进行编码处理， 得到包含空间编码数据 和所述原 始时间数据的多组时空 处理数据； 对每组时空处理数据中的空间编码数据进行前缀编码， 生成所述每组时空处理数据的 前缀编码族； 通过将所述每组时空处理数据， 以及所述每组时空处理数据的前缀编码族， 作为混合 索引树的一个叶子节点， 得到多个叶子节点； 通过对不同的前缀编码族进行合并， 自底向上逐层生成非叶子节点； 其中， 每个非叶子 节点对应一个合并编码族， 每个非叶子节点为至少一个叶子节点或至少一个非叶子节点的 父节点， 每个父节点对应的合并编 码族包含该父节点的所有孩子节点的前缀编 码族或合并 编码族； 根据每个叶子节点对应的前缀编码族， 生成所述每个叶子节点的布隆过滤器， 以及根 据每个非 叶子节点对应的合并编码族， 生成每个非 叶子节点的布隆过滤器， 得到混合索引 树； 其中， 不同叶子节点的布隆过滤器的长度相同， 不同层的非叶子节点的布隆过滤器的长 度不同； 对每个布隆过 滤器进行对称加密， 得到加密的混合索引树。 2.根据权利要求1所述的加密的混合索引树的生成方法， 其特征在于， 所述合并编码族 包括： 第一合并编码族、 第二合并编码族和第三合并编码族； 每个前缀编码包括ω位的码 值； 所述通过对不同的前缀编码族进行合并， 自底向上 逐层生成非叶子节点， 包括： 通过对所述多个叶子节点对应的不同的前缀编码族进行合并， 得到每个叶子节点对应 的所述第一合并编码族， 将所述第一合并编码族， 作为对应的叶子节点的第一父节点； 其 中， 每个叶子节点 为对应的第一父节点的孩 子节点； 将所述叶子节点作为所述混合索引树的第ω层， 将所述第 一父节点作为所述混合索引 树的第ω ‑1层； 通过对多个第 一父节点对应的第 一合并编码族进行合并， 得到每个第 一父节点对应的 所述第二合并编码族， 将所述第二合并编码族， 作为对应的第一父节点的第二父节点； 其 中， 每个第一父节点 为对应的第二父节点的孩 子节点； 将所述第二父节点作为所述混合索引树的第ω ‑2层； 通过对多个第 二父节点对应的第 二合并编码族进行合并， 得到每个第 二父节点对应的 所述第三合并编码族， 将所述第三合并编码族， 作为对应的第二父节点的第三父节点； 其 中， 每个第二父节点 为对应的第三父节点的孩 子节点； 将所述第三父节点作为所述混合索引树的第ω ‑3层， 直至得到所述混合索引树的第 ω‑w层的节点； 其中， w 为ω‑1。 3.根据权利要求2所述的加密的混合索引树的生成方法， 其特征在于， 所述第 一合并编 码族包括： 第一原编码和第一子编码； 所述通过对所述多个叶子节点对应的不同的前缀编码族进行合并， 得到每个叶子节点 对应的所述第一合并编码族， 将所述第一合并编码族， 作为对应的叶子节点的第一父节点，权　利　要　求　书 1/4 页 2 CN 115391803 A 2包括： 将所述多个叶子节点对应的不同的前缀编码族内的前缀编码逐位进行比对， 确定前 ω‑1位码值相同、 且第ω位不同的至少 两个第一前缀编码族， 当存在所述至少 两个第一前 缀编码族时， 将所述至少两个第一前缀编 码族中不包含通配符的前缀编码的所述第ω位码 值设置为 通配符， 得到所述第一原编码； 将所述第一原编码的第ω ‑1位的码值设置为通配符， 对应得到第一子编码， 将所述第 一原编码的第ω ‑2位的码值设置为通配符， 对应得到第一子编码， 直至将所述第一原编码 的第ω‑w位的码值设置为 通配符时， 对应得到 至少一个第一子编码； w 为ω‑1； 将所述第一原编码和所述至少一个第 一子编码， 作为所述至少两个第 一前缀编码族对 应的叶子节点的所述第一父节点。 4.根据权利要求3所述的加密的混合索引树的生成方法， 其特征在于， 所述方法还包 括： 当不存在所述至少两个第 一前缀编码族时， 将所述多个叶子节点对应的不同的前缀编 码族内的前缀编码逐位进行比对， 确定前ω ‑2位码值相同的、 且第ω ‑1位码值不同的至少 两个第二前缀编码族， 当存在所述至少 两个第二前缀编码族时， 将所述至少 两个第二前缀 编码族中不包含通配符的前缀编 码的所述第ω ‑1位和第ω位码值均设置为通配符， 得到第 三原编码； 将所述第三原编码的第ω ‑2位的码值设置为通配符， 对应得到第三子编码， 将所述第 三原编码的第ω ‑3位的码值设置为通配符， 对应得到第三子编码， 直至将所述第三原编码 的第ω‑w位的码值设置为 通配符时， 对应得到 至少一个第三子编码； w 为ω‑1； 将所述第三原编码和所述至少一个第 三子编码， 作为所述至少两个第 二前缀编码族对 应的叶子节点的所述第一父节点。 5.根据权利要求3所述的加密的混合索引树的生成方法， 其特征在于， 所述第 二合并编 码族包括： 第二原编码和第二子编码； 当存在所述至少两个第 一前缀编码族时， 所述通过对多个第 一父节点对应的第 一合并 编码族进行合并， 得到每个第一父节点对应的所述第二合并编码族， 将所述第二合并编码 族， 作为对应的第一父节点的第二父节点， 包括： 将不同的第一合并编码族内的编码进行逐位比对， 确定前ω ‑2位码值相同、 且第ω ‑1 位码值不同的至少 两个合并编码族， 当存在所述至少 两个合并编码族时， 将所述至少 两个 合并编码族中， 包含通配符最少的编码的所述第ω ‑1位至第ω位码值均设置为通配符， 得 到所述第二原编码； 将所述第二原编码的第ω ‑2位的码值设置为通配符， 对应得到第二子编码， 将所述第 二原编码的第ω ‑3位的码值设置为通配符， 对应得到第二子编码， 直至将所述第二原编码 的第ω‑w位的码值设置为 通配符时， 对应得到 至少一个第二子编码； w 为ω‑1； 将所述第二原编码和所述至少一个第 二子编码， 作为所述至少两个合并编码族对应的 所述第一父节点的所述第二父节点。 6.根据权利要求1所述的加密的混合索引树的生成方法， 其特征在于， 在任意一组时空 处理数据中的一个空间编 码数据为ω位的数据时， 所述对每组时空处理数据中的空间编码 数据进行 前缀编码， 生成所述每组时空 处理数据的前缀编码族， 包括：权　利　要　求　书 2/4 页 3 CN 115391803 A 3