(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210739095.3 (22)申请日 2022.06.12 (71)申请人 中国科学院重庆绿 色智能技 术研究 院 地址 400714 重庆市北碚区水土镇水土高 新园方正大道 266号 (72)发明人 吴文渊　郭春彤　杨文强　 (51)Int.Cl. H04L 9/32(2006.01) H04L 9/40(2022.01) (54)发明名称 一种基于MLWE和MSIS的可验证解密方法 (57)摘要 本发明为一种基于MLWE和MSIS的可验证解 密方法， 属于信息安全领域。 该方法包含以下步 骤： S1： 设定可验证解密方法的相 关参数； S2： 根 据安全参数生成密钥； S3： 利用公钥对明文向量 进行加密并公开； S4： 验证者进行同态计算； S5： 证明者利用私钥解密； S6证明者和验证者执行非 交互式零知识 证明。 本发明改造具有零知识特性 的数字签名方案Dilithium的无公钥压缩框架， 为Kyber的IND ‑CPA安全公钥加密方案解密的正 确性构造了一个基于格困难假设MLWE和MSIS的 实用、 高效、 简洁的可验证解密方案， 能够用于解 决两方安全计算场景中所涉及的可验证解密问 题。 权利要求书3页 说明书8页 附图2页 CN 115150094 A 2022.10.04 CN 115150094 A 1.一种基于MLWE和MS IS的可验证解密方法， 由证明者 和验证者 两方参与进行实现， 无需可信第三方参与， 其中， 为持有私钥的一方， 为执行计算的一方， 其特征在于： 该方 法包含以下步骤： S1： 设定MLWE和MSIS的可验证解密方法的相关参数： λ， n， q， k， du， dv， dh， γ， η1， η2， τ， l； 其中， λ为安全参数， 由预判敌手攻击次数小于等于2λ计算得出； n为多项式环 的次数， 为2的幂次； q为模数， 满足q≡1  mod 2·n； k为向量维数， 是根据安 全参数 λ选取的正整数； du、 dv分别对应调用Kyber的IND ‑CPA安全公钥加密方案产生的密文 c ＝(u， v)压缩后的比特数； dh为压缩函数的参数， 表示数据压缩后的比特数； γ为k+1维多项 式向量y的系数界； η1为Kyber中私钥s、 噪声向量 e、 随机向量r的系数界； η2为Kyber中密文噪 声e1、 e2的系数界； τ是挑战值h中含有 ±1的个数， 根据安全参数λ、 Rq上多项式的次数n选取， 需满足 l为||(‑s， 1)·h||∞的界， 根据私钥s的系数界η1以及参数τ计算得出， | |·||∞为无穷范 数； S2： 证明者 调用Kyber的IND ‑CPA安全公钥加密方案中的密钥生成算法， 生成公私钥对 (pk， sk)， 证明者 持有私钥 并将公钥 公开； S3： 证明者 和验证者 调用Kyber的IND ‑CPA安全公钥加密方案中的加密算法， 分别利 用公钥对各自的明文向量进行加密， 得到密文向量并公开； S4： 验证者 对密文向量中的各个分量进行同态计算生成同态密文， 完成同态计算后， 利用自举刷新同态密文， 并公开刷新后的同态密文 S5： 证明者 调用Kyber的IND ‑CPA安全公钥加密方案中的解密算法， 利用私钥s对同态 密文c进行解密， 得到 c对应的明文m＝Compres sq(v‑sTu， 1)∈R2； 其中， 压缩函数定义为y＝Compressq(x， d)＝ 「(2d/q)·x」 mod+2d； 输入为 d＜ 「 log2(q)」 ， 输出为y∈{0， ...， 2d‑1}， 表示四舍五入； mod+为取模运算符， 设α 为正整数， 定义 r′＝r mod+α 表示r′的取值范围是[0， α )； S6： 证明者 构造明文0∈R2对应的Kyber密文 向量 随机选取 系数界为γ的k+1 维多项式向量y， 取y的前k维生成向量 S7： 证明者 首先对 双方所持数据之间差异值的分布进行估计， 以压缩函数的函 数值出现跳变时对应的自变量取值点为中心， 以截取 的差异值的界为半径构造跳变区间， 将 所持数据c ′T·y和 处于跳变区间的系数下标分别保存于集合E1、 E2中， 并置零这些 系数， 然后通过散列函数计算挑战值h， 随后计算应答值 并且仅当||z| |∞＜γ‑l时才接受， 否则回到步骤S6重新执行， 将m、 h、 z、 E1、 E2进行连接整合成证明π＝ (m， h， z， E1， E2)， 并将该证明通过安全信道发送给验证者 S8： 验证者 接收到证明π后， 计算明文0∈R2对应的Kyber密文向量 取应答值z的前k维作为向量 再利用集合E1、 E2中的系数下标将 所持数据c ′T·z、 对应的系数分别置零并计算哈希值， 然后将该哈希值与证 明π中的挑战值h进行比 较验证， 同时验证||z| |∞， 若 计算的哈希值与证明π 中的挑战值h不相等或者| |z||∞≥γ‑l 则验证失败， 输出0表示拒绝， 否则验证成功， 输出1表示接受。 2.根据权利要求1所述的一种基于MLWE和MSIS的可验证解密 方法， 其特征在于， 步骤S2权　利　要　求　书 1/3 页 2 CN 115150094 A 2由证明者 执行， 所述的步骤S2具体为： S201： 在多 项式环Rq上随机选取k×k个多项式构成矩阵A， S202： 从中心二项分布中均匀随机取样私钥与噪声， S203： 计算t＝As+e， 输出公钥 私钥 其中， 步骤S202所述的中心二项分布Bη定义为： 采样(a1， ...， aη， b1， ...， bη)←{0， 1}2η， 输出 若v∈R， v ←βη表示采样v的每个系数服从分布Bη， 多项式环 ← 表示随机采样 操作。 3.根据权利要求1所述的一种基于MLWE和MSIS的可验证解密 方法， 其特征在于， 步骤S3 所述的加密过程具体为： 证明者 和验证者 调用Kyber的IND ‑CPA安全公钥加密方案中的 加密算法Enc(pk， mi)对数据(mi)1≤j≤t中各自持有部分进行加密， 其中t根据数据长度的不同 会发生变化， 得到密文 并公开。 4.根据权利要求1所述的一种基于MLWE和MSIS的可验证解密 方法， 其特征在于， 步骤S4 由验证者 执行， 所述的步骤S4具体为： 根据双方公开的密文维度t， 任意构造t维输入的函 数f(·)， 计算同态密文 随后利用自举刷新该同态密 文， 输出刷新后的密 文 并公开密文c的值。 5.根据权利要求1所述的一种基于MLWE和MSIS的可验证解密 方法， 其特征在于， 步骤S5 由证明者 执行， 其所述的解密过程具体为： S501： 首先， 利用解压缩函数对步骤S4产 生的同态密文c中的u、 v分别进行解压缩 处理， 得到 其中， 表示赋值操作； S502： 然后， 利用压缩函数解密得到明文m＝Compres sq(v‑sTu， 1)∈R2； 其中， 所述的解压缩函数定义为x ′＝Decompressq(y， d)＝ 「(q/2d)·y」 ； 输入为y∈ {0， ...， 2d‑1}、 d＜ 「l og2(q)」 ， 输出为 6.根据权利要求1所述的一种基于MLWE和MSIS的可验证解密 方法， 其特征在于， 步骤S6 由证明者 执行， 所述的步骤S6具体为： S601： 构造明文0∈R2对应的密文 S602： 随机选取多项式向量 S603： 若y的每 个分量都不可逆， 返回步骤S6 02； S604： 取多项式向量y的前k个分量组成新的向量 其中， 步骤S602所述的 集合Sγ中的任意元素t∈R， ||t||∞≤γ， 用 表示集合(t   mod±2γ： t∈R}； 表示k+1维向量， 每个分量取自集合 mod±为取模运算符， 设α 为正偶 数(或正奇数)， 定义r ′＝rmod±α 表示r′的取值范围是( ‑α /2， α /2](或 )。 7.根据权利要求1所述的一种基于MLWE和MSIS的可验证解密 方法， 其特征在于， 步骤S7 由证明者 执行， 其所述的证明生成过程具体为： S701： 根据证明者和验证者事先约定的对话格式， 计算证明者和验证者所持第一部分权　利　要　求　书 2/3 页 3 CN 115150094 A 3