(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211057051.9 (22)申请日 2022.08.30 (71)申请人 西安电子科技大 学 地址 710071 陕西省西安市太白南路2号 (72)发明人 樊凯　李文浩　王昊洋　肖进　 陈红艳　高楠　李晖　 (74)专利代理 机构 西安智大知识产权代理事务 所 61215 专利代理师 贺建斌 (51)Int.Cl. G06F 16/901(2019.01) G06F 21/62(2013.01) G06F 21/64(2013.01) H04L 9/08(2006.01) H04L 9/32(2006.01) (54)发明名称 安全高效的动态加密云数据多维范围查询 方法 (57)摘要 安全高效的动态加密云数据多维范围查询 方法， 数据拥有 者以安全参数、 素数作为输入， 生 成密钥集以及系统参数元组； 数据拥有者根据G ‑ 树构建用于验证查询结果及更新的加密索引， 同 时输出具有索引的验证签名； 查询用户为具有密 钥集的多维范围查询生成陷门； 云服务器通过加 密索引在加密数据库上检索范围查询， 输出检索 结果和验证辅助信息； 查询用户得到检索结果以 及验证辅助信息后， 利用哈希函数进行完整性验 证； 数据拥有者更新数据集和签名， 得到更新后 的数据集以及新签名； 本发明满足多维范围查询 的查询隐私、 一维隐私、 路径保护、 数据动态更 新、 结果验证、 前向隐私和后向隐私， 实现了查询 低成本和高安全性需求之间的均衡 。 权利要求书4页 说明书13页 附图8页 CN 115438230 A 2022.12.06 CN 115438230 A 1.一种安全高效的动态加密云数据多维范围查询方法， 其特 征在于， 包括以下步骤： S101初始化阶段： 数据拥有者DO， 以安全参数η， 素数p、 q作为输入， 生成密钥集SK以及 系统参数 元组SP； S102索引加密阶段： 数据拥有者D O根据G‑树构建用于验证查询结果及更新的加密的原 始索引I， 同时数据拥有者DO输出 具有原始索引I的验证 签名Sig； S103生成陷门： 查询用户QU执行陷门生成算法GenTrap为具有密钥元组SK的多维范围 查询Q生成陷门TR； S104查询阶段： 云服务器CS执行查询算法Query， 通过原始索引I在加密数据库上检索 范围查询TR， 云服 务器输出检索结果 和验证辅助信息A ′； S105验证阶段： 在查询用户QU 得到检索结果 以及验证辅助信息A ′后， 查询用户QU利用 哈希函数H( ·)进行完整性验证， 若验证通过输出1； 否则输出0； S106更新阶段： 数据拥有者DO通过更新数据记录Dup、 原始签名A和更新算法Update更新 数据集和签名， 得到更新后的数据集D ′以及新签名Anew。 2.根据权利要求1所述的方法， 其特 征在于， 所述的始化阶段包括： 数据所有者DO选择一个安全参数η， 两个大素数p、 q， 数据所有者DO生成密钥集SK＝ {SKleaf,SKnon‑leaf,SKdata}， 计算公式如下： 此外， 数据所有者DO计算N＝pq， 选择一个大基数a， 生成一个安全的哈希函数H( ·)， 两 个置换函数π1(·)、 π2(·)， 置换函数对应的密钥分别为 3.根据权利要求1所述的方法， 其特 征在于， 所述的索引加密阶段包括： (1)首先， 数据所有者DO加密原始索引I＝{L1,…,Ln,N1,…,Nt,P}， 其中 代表叶 子结点， 代表非叶子结点， P代 表孩子结点的指针集 合， 之后数据所有者DO将加密索引I*＝{EL1,…,ELi,EN1,…,ENj,P}以及密文C外包给云服 务器CS， 其中 分别表示加密后的叶子结点和 加密后的非叶子结点； (2)数据所有者DO利用哈希函数H( ·)计算加密数据点Ci的哈希值， 即xi←H(Ci)， 数据 所有者DO计算密文C的RSA累积值， 即 DO通过组合累积值A和当前时间戳t得到元组(A,t)， 并使用签名私钥SKs对(A,t)进行签 名； 加密索引I*及签名Sig(A,t)将通过数据所有者D O一并上传CS， 签名公钥SKp被分发至各 授权用户D S。 4.根据权利要求1所述的方法， 其特 征在于， 所述的陷门生成阶段包括：权　利　要　求　书 1/4 页 2 CN 115438230 A 2输入密钥元组SK以及多维范围查询MRQ， 陷门生成的过程如下 所示： 之后数据所有者DO将陷门 分配给授权的查询用户QU。 5.根据权利要求1所述的方法， 其特 征在于， 所述的查询阶段包括： 输入查询陷门TRMRQ、 加密索引I*， 云服务器CS逐级检索加密 索引I*； (1)云服务器CS开始从加密索引I*的根结点检索， 对于非叶子结点ENj， 当且仅当 时， 继续检索该结点下的子结点， 否则它停 止检索该 结点； ( 2 ) 对 于 叶 子 结 点 E Li，当 且 仅 当 数 据 点 Ci∈ M R Q ，即 时， 将数据点Di的标识符IDi放入结果列表ResultMRQ； (3)同时， 云服务器CS在删除ResultMRQ中的每个数据点后计算剩余数据点的累积值， 即 A′由云服务器CS使用私钥SKs签名； 最后， 云服务器CS返回结果列表ResultMRQ， 使用验证辅助签名 Sig(A′)， 验证签名Sig (A， t)发送给查询用户QU。 6.根据权利要求1所述的方法， 其特 征在于， 所述的验证阶段包括： 输入辅助签名Sig(A ′)， 验证签名Sig(A,t)， 结果列表ResultMRQ以及哈希函数H( ·)； (1)查询用户QU首先用skp解密Sig(A,t)来获得初 始累积值A以及时间戳t， 并且 通过t来 检查签名的有效性； (2)查询用户利用H( ·)计算结果列表ResultMRQ中每个数据点的相关值， 计算公式如 下： 之后， 查询用户计算并检查累积值 并且将其与A进行比较， 当且仅当A*＝A 时， 表示结果 集是完整的； 否则， 结果 集不完整。 7.根据权利要求1所述的方法， 其特 征在于， 所述的更新阶段包括： 插入： 在G树中， 插入操作由两个函数实现， “分配”和“搜索”；“分配”函数用于生成插入 结点在树中的相应位置， “搜索”函数用于查找树中相应位置的特定分区； 如果插入不会导 致分区溢出， 则直接执 行插入操作； 否则， 应先分割分区， 然后插 入； (1)直接插入： 当数据所有者DO插入一组新的数据Dnew时， 首先需要判断Dnew的插入位 置， 数据所有者DO使用 “等价查询 ”操作进行评估； 也就是说， 数据所有者DO将 转 换 为 范 围 向 量 其 中 数据所有者DO通过执 行GenTrap和EncI ndex算法， 获得相应的陷门 TRnew、 密文_Cnew和基于MRnew的更新签名Anew； 收到更新元组(TKnew,Cnew,A′)后， 从数据所有 者 DO开始， 查询用户QU运行查询算法以获取数据插入位置， 并将C ′存储在数据库中； 在加密权　利　要　求　书 2/4 页 3 CN 115438230 A 3