(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210787173.7 (22)申请日 2022.07.04 (71)申请人 贵州财经 大学 地址 550000 贵州省贵阳市花溪大 学城 (72)发明人 于莹莹　丁红发　刘海　蒋合领　 吴宁博　傅培旺　唐明丽　 (74)专利代理 机构 北京和联顺知识产权代理有 限公司 1 1621 专利代理师 张俊生 (51)Int.Cl. H04L 9/00(2022.01) H04L 9/06(2006.01) H04L 9/08(2006.01) H04L 9/32(2006.01) H04L 45/12(2022.01) (54)发明名称 一种加法同态加密和密码累加器计算的方 法 (57)摘要 本发明涉及一种加法同态加密和密码累加 器计算的方法。 本发明提出的一种基于加法同态 和双线性映射累加器的图数据可验证外包计算 方法， 首先， 利用同态密码加密邻接表实例化的 图数据， 并结合加法同态加密和混淆电路基于优 先队列实现广度优先Dijk stra算法， 计算加密图 数据上的精确最短路径； 其次， 基于加密图数据 构造二项堆结构并利用双线性映射累加器计算 加密最短路径结果的验证证据， 实现加密图数据 外包最短路径 查询计算结果的正确性可验证； 此 外， 方案还利用无证书短签名保障了云服务器的 最短路径查询结果和验证结果的真实性和不可 篡改性， 实现加密图数据最短路径 查询外包计算 结果的概 率正确性验证 。 权利要求书2页 说明书5页 附图1页 CN 115021890 A 2022.09.06 CN 115021890 A 1.一种加法同态加密和密码累加器 计算的方法， 其特 征在于， 包括 步骤如下： 步骤一、 权威机构设置参数， 具体为： 权威机构随机选取一个安全参数λ， 根据安全参数 生成伪随机函数值k1,k2,k3←{0,1}λ， 并由Paillier算法计算出基础密钥对(skp,pkp)， 二者 结合生成客户端密钥(pkc,skc)； 步骤二、 客户端图数据邻接表实例化， 具体为： 客户端对原始图数据进行邻接表实例 化， 用邻接表存储原始图数据的节点和边信息， 邻接表中包含 各个节点和其邻接点， 存储邻 接点及其 边的长度； 步骤三、 客户端加密图数据， 具体为： 客户端获取原始图数据G的顶点集V， 边集E， 获取 秘密哈希值skh， 客户端初始化数组AG、 字典TD和TG， 遍历并获取图中节点元素， 客户端计算 当前节点的伪随机函数值Ku， 遍历当前节点的出度值deg+(u)， 依 次加密边的 长度len(u,vi)， 得到 通过判断当前节点的出度情况来设定节点 Ni的组成和其邻接节点Di的组成； 采用随机预言机模型H:{0,1}*→{0,1}*异或计算节点Ni将其加密存储在数组AG中， 遍历数组， 使用共 享秘密哈希值 skh对数组AG中的每个 元素计算哈希形 成哈希集H1＝h1, h2,...,hn， 其中hi＝H(skh,AG[i])； 使用密码累加器 计算集合H1的累加值 结合伪随机函数 及 存储邻接节点Di在字典TD中， 其中 数组中每个头结点的地址array(Ni)加密存储在字典TG中， 头结点的地址即为每个邻接 表头的指针， 最终生成加密图ΩG＝(AG,TG, TD)和累加器 并将ΩG发送给服 务器； 步骤四、 客户端根据查询请求生成查询令牌， 具体为： 客户端获取查询请求q＝(s,t)， 包括源点s和终点t； 客户端计算 生成查询令牌 步骤五、 云服 务器密文查询计算， 具体为： 云服 务器获取加密图数据ΩG和查询令牌 τq； 云服务器解析查询令牌τq＝( τ1, τ2, τ3)， 获取密文查询源点τ1， 密文查询终点τ2， 辅助条 件 τ3； 判断密文查询源点τ1和终点τ2是否在密文图数据中存在， 存在则继续， 不存在则退出查 询， 返回NUL L； 云服务器初始化 二项堆H， 存放节点 值的字典path及存放 边长的字典ξ； 结合数组AG及字典TG和TD， 重构密文图数据的邻接关系； 以密文 查询源点τ1为起始位置， 构造二项堆H直至构建完成； 将构建二项堆H过程中未使用的节点 遍历并累加得到ac c(Hother)； 采用基于广度优先的Dijkstra算法， 从构造完整的二项堆H中计算最短路径， 循环获取权　利　要　求　书 1/2 页 2 CN 115021890 A 2堆H中的最小节点Ext ractMin(Heap)， 将该节点与边长存放在字典path和字典ξ 中. 若当前获取的最小节点与查询的尾 结点相同时， 即ExtractMin(Heap)＝＝τ2， 最短路径 查询结束， 返回反向迭代计算后的路径path与密文长度ξ， 二者构成加密结果Dq； 将堆中未 用以计算最短路径path的节点 进行累加得到acc(Huseless)； acc(Hother)与acc(Huseless)的 和为密文图数据最短路径的验证证据， 即累加值acc(H2)， acc(H2)＝acc(Hother)+acc (Huseless)； 云服务器对计算结果Dq与验证证据acc(H2)签名， 生成WitD， 将签名同Dq和acc(H2)一同 发送给客户端； 步骤六、 客户端验证云服 务器签名与解密， 具体为： 客户端获取云服务器发送的加密最短路径Dq， 验证证据累加值acc(H2)和签名WitD； 根 据云服务器的身份ID对签名进 行SignVer ify验证， 如果验证成功， 则继续解密， 否则退出验 证； 对密文最短路径结果Dq进行解析， 得到Dq＝＜Dpath,Ddist＞， 即密文 最短路径节点集合及 密文最短路径边长集 合； 客户端对密文最短路径节点 的集合Ddist进行累加， 计算密文最短路径累加值acc (Hdist)； 通过比对 云服务器返回的验证证据累加值acc(H2)是否等同acc(H1)与acc(Hdist)的 差值判断Dq的正确性； 验证通过， 则对密文计算结果Dq进行解密， 获取明文状态的最短路径distpath和最短距 离distq， 验证不通过， 则返回NUL L。权　利　要　求　书 2/2 页 3 CN 115021890 A 3