(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111399432.0 (22)申请日 2021.11.19 (71)申请人 北京数牍科技有限公司 地址 100083 北京市海淀区成府路28号10 层2-1002 (72)发明人 蔡超超　单进勇　王昊昱　牛子儒　 凌国玮　 (74)专利代理 机构 重庆辉腾律师事务所 5 0215 代理人 王海军 (51)Int.Cl. H04L 9/00(2022.01) H04L 9/08(2006.01) H04L 9/40(2022.01) (54)发明名称 一种用于同态加密方案的快速解密方法 (57)摘要 本发明涉及数据安全技术领域， 具体涉及一 种同态加密方案的快速解密方法， 该方法包括： 加密用户与解密用户事先约定使用的同态加密 方案， 双方用户端预计算系统参数； 解密用户端 接收经过加密后的密文； 解密用户端接收到密文 后计算密文参数； 根据获取的系统参数采用改进 的BSGS算法对密文参数进行明文恢复， 得到明 文； 若同态加密方案的解密算法需要对解密结果 进行校验， 则进行密文校验， 即校验结果正确， 则 输出解密结果， 校验结果错误， 则解密失败； 本发 明能在幂指数较小时快速求解离散对 数问题， 具 有一定通用性； 相比于传统的此类同态加密方 案， 本发明所提出的快速解密方法能将此类同态 加密方案的解密速度提升10倍以上。 权利要求书2页 说明书7页 附图4页 CN 114124349 A 2022.03.01 CN 114124349 A 1.一种用于同态加密方案的快速解密方法， 其特征在于， 包括： 获取加密用户与解密用 户采用的同态加密方案， 加密用户端和 解密用户端根据同态加密方案预计算系统参数； 解 密用户端接 收经过加密用户端加密后的密文， 根据加密后的密文计算密文参数； 根据系统 参数采用改进的BSGS算法对密文参数进行明文恢复， 得到明文； 解密用户对恢复的明文进 行校验， 若校验结果 正确， 则输出解密结果， 若校验结果 错误， 则解密失败。 2.根据权利要求1所述的一种用于同态加密方案的快速解密方法， 其特征在于， 加密用 户端与解密用户端采用的同态加密方案为椭圆曲线的同态加密方法或者实数域的加密方 法。 3.根据权利要求1所述的一种用于同态加密方案的快速解密方法， 其特征在于， 加密用 户端和解密用户端根据同态加密方案预计算系统参数 的过程包括： 获取系统公共参数； 确 定加密用户端对明文进行加密的方案； 若加密方案为公钥同态加密方案， 则加密用户端获 取加密公钥pk， 解密用户端获取解密私钥sk， 解密用户端根据加密公钥和解密私钥得到表 T1和表T2； 若加密方案 为基于身份的 同态加密方案， 则引入密钥生成中心KGC， 密钥生成中心 KGC生成加密主密钥 对； 用户端直接得到解密用户端的身份标识ID， KGC生成解密私钥skID， 并发送给解密用户端， 解密用户端根据解密私钥skID得到预计算表T1和T2。 4.根据权利要求3所述的一种用于同态加密方案的快速解密方法， 其特征在于， 得到表 T1和表T2的过程包括： 步骤1： 自定义正整数ilen和jlen， 使得mlen＝ilen+jlen成立； 其中， ilen表示表T1的长 度取2的对数值， jlen表示表T2的长度取2的对数值， mlen表示明文空间的比特长度； 步骤2： 根据自定义正整数ilen和jlen构 建键值对型数据结构， 将构 建得到的数据进行 保存， 得到预计算表T1； 步骤3： 根据自定义正整数ilen和jlen构 建集合型数据结构， 将构 建得到的数据进行保 存， 得到预计算表T2； 其中， T2表示集合型数据结构。 5.根据权利要求1所述的一种用于同态加密方案的快速解密方法， 其特征在于， 解密用 户端接收经加密后的密 文的过程包括： 判断密 文的加密方案， 若为 公钥同态加密方案， 则加 密用户端使用加密公钥pk加密明文m得到密文c； 若为基于身份的同态加密方案， 加密用户 端使用解密用户标识ID加密明文m得到密文c； 加密用户端将密文c安全的发送给解密用户 端。 6.根据权利要求1所述的一种用于同态加密方案的快速解密方法， 其特征在于， 解密用 户端计算密文参数 的过程包括： 根据同态加密方案采用对应的解密算法对密文进行解密， 得到密文参数[m]G或gmmod N； 其中， [m]G是椭圆曲线点G的m倍点， gmmod N是群元素g的m次 幂模阶数N， mod  N表示模阶数N。 7.根据权利要求1所述的一种用于同态加密方案的快速解密方法， 其特征在于， 采用改 进的BSGS算法对密文参数进行明文恢复的过程包括： 解密用户端判断同态加密方法； 若为 椭圆曲线的同态加密方法， 则采用基于椭圆曲线的BSGS算法对密文参数进行明文恢复； 若 为实数域的加密方法， 则采用基于实数域的BSGS算法对密文参数进行明文恢复。 8.根据权利要求7所述的一种用于同态加密方案的快速解密方法， 其特征在于， 采用基 于椭圆曲线的BSGS算法对密文参数进行明文恢复的过程包括： 步骤31： 计算[m]G与T2[j]的横坐标之差并保存， 其中j∈[ 0,2jlen‑1]； 计算过程为： 设置权　利　要　求　书 1/2 页 2 CN 114124349 A 2循环次数j∈[0,2jlen‑1]； 计算 其中 是椭圆曲线点T2[j]的横坐标， x[m]G是椭圆曲线点[m]G的横坐标， zj为椭圆曲线点[m]G与椭圆曲线点T2[j]的横坐标之差， 将横坐标之差存入表L:{zj}， L为椭圆曲线点[m]G与椭圆曲线点T2[j]的横坐 标之差的集合， 重复上述计算过程， 直到跳出循环； 其中， j表示BSGS算法的循环次数， m表示明文， G表示椭 圆曲线基点， T2[j]表示表T2的第j个元 素， zj表示第j个横坐标之差； 步骤32： 以L为叶子结点， 根据位于父节点下一级的两个子节点数据的乘积作为该父节 点数据的生成规则， 从下至上生成 “乘法二叉树 ”Tree1， 并记Tre e1的根值为A； 步骤33： 计算Tree1的根值A关于p的逆元A‑1， 以A‑1为初始节点从上至下生成 “逆元二叉 树”Tree2， 生成规则为当前子节点等于该子节点的父节点的值乘以Tree1在兄弟节点位置的 节点值； Tree2的叶子节点Tre e2[j]为L[j]模p的逆元， j∈[0,2jlen‑1]； p表示大 素数； 步骤34： 执 行BSGS算法， 计算m ′， 其中m′为通过密文还原的明文。 9.根据权利要求7所述的一种用于同态加密方案的快速解密方法， 其特征在于， 采用基 于实数域的BSGS算法对密文参数进行明文恢复的过程包括： S31： 设表T2中的元素为 “乘法二叉树 ”Tree1的叶子结点， 以位于父节点下一级的两个子 节点数据在模N下的积作为父节点中的数据为生成规则， 从下至上生成Tree1， 并记Tree1的 根值为A； S32： 计算Tree1根值A关于N的逆元A‑1， 以A‑1为初始节点从上至下生成 “逆元二叉树 ” Tree2， 生成规则为当前子节点等于该子节点的父节点的值乘以Tree1在兄弟节点位置的节 点值； Tree2的所有叶子节点Tre e2[j]为T2[j]模N的逆元， j∈[0,2jlen‑1]； S33： 执行BSGS算法， 计算m ′， 其中m′为通过密文还原的明文。 10.根据权利要求1所述的一种用于同态加密方案的快速解密方法， 其特征在于， 对明 文进行校验的过程包括： 对解密后的明文采用与解密前相同的加密算法进行加密， 计算重 新加密后的密文参数； 根据重新计算的密文参数与原始计算的密文参数进行对比， 若密文 参数相同， 则解密得到的明文正确， 否则解密失败。权　利　要　求　书 2/2 页 3 CN 114124349 A 3