本发明涉及基于mlwe和msis的高效可验证解密方法，属于信息安全领域，尤其适用于基于mlwe和msis的可验证解密。
背景技术：
1、考虑以下两方安全计算场景：持有私有秘密数据、互不信任的两方想就各自所拥有的数据进行合作计算但又不想泄露各自的数据。执行计算的一方用对方的公钥对两方的加密数据进行同态运算后得到同态密文。持有私钥的一方获取该同态密文后，利用私钥对密文解密得到计算结果，需要将计算结果提供给计算方并且以零知识的方式证明这个计算结果是同态密文所对应的明文。在这个场景中，解密的一方不仅需要给计算方提供解密结果，还需要提供对正确解密的零知识证明，这是一个可验证解密的问题。现实中可验证解密问题在医疗、工业、金融、政务等领域也很常见。例如，医院之间在不泄露病人个人隐私前提下进行医疗研究数据共享实现对某种疾病的预防；银行之间数据联合建模对用户进行信用风险评估等。
2、知识的零知识证明与同态加密两种技术的结合可以用来构造可验证解密方案。例如，luo等人于2018年发表的“verifiable decryption for fully homomorphicencryption”一文基于rlwe和rsis问题，将为bgv方案提供可验证解密问题转变为形如a·s＝0的线性关系，并将该线性关系与“fiat-shamir with aborts”零知识证明技术进行结合，产生了一个几乎是“one shot”的可验证解密方案，但是这个方案也存在一些问题：首先，在bgv方案中，明文放在低位上，明文空间较小，加密效率和密文膨胀率有待进一步优化；其次，为了隐藏私钥，方案使用基于高斯分布的拒绝采样技术，但高斯分布的抽样容易受到侧信道攻击。lyubashevsky等人于2021年发表的一文“shorter lattice-based zero-knowledge proofs via one-time commitments”构造了满足b·s＝t的三元秘密向量s知识的证明，其中就包括为kyber构造的可验证解密方案，虽然该方案在对单个密文的证明上有优势，并且可以推广到其他一些基于格的密钥封装方案中，但产生的证明由对线性关系的证明、对短元素的证明和范围证明构成，较为复杂。授权发明专利cn 115150094b以及参考文献[1]为同一方法，提出了“一种基于mlwe和msis的高效可验证解密方法”，给出了正确性构造非交互式的零知识证明，但其在正确性上的要求过于苛刻，导致交互传递的信息过多，通讯开销较大且安全性较低。经过验证，在实际应用中，适当的降低减少交互信息也同样能够保证交互信息满足正确性要求的。
3、郭春彤，吴文渊.基于mlwe和msis的可验证解密方案[j].计算机科学，2024，51(05)：331-345.
技术实现思路
1、有鉴于此，本发明的目的在于针对kyber提供基于模容错学习问题(modulelearning with errors，mlwe)和模小整数解问题(module short integer solution，msis)的高效可验证解密方法，意在降低通讯开销，提高安全性，保障高效、安全、正确的可验证解密方法。具体地，将改造具有零知识特性的数字签名方案dilithium的无公钥压缩框架，为kyber的ind-cpa安全公钥加密方案解密的正确性构造非交互式零知识证明。该方法可以进一步应用在医疗研究数据共享、机构间合作进行模型训练等有隐私保护需求的现实场景中，有助于进一步打破数据孤岛、保障数据安全。
2、为达到上述目的，本发明提供如下技术方案：
3、基于mlwe和msis的高效可验证解密方法，由证明者和验证者两方参与进行实现，无需可信第三方参与，其中，为持有私钥的一方，为执行计算的一方，包括以下步骤：
4、s1：设定基于模容错学习问题(module learning with errors，mlwe)和模小整数解问题(module short integer solution，msis)的高效可验证解密方法的相关参数：λ，n，q，k，du，dv，dh，γ，η1，η2，τ，l，m；
5、其中，λ为安全参数，由预判敌手攻击次数小于等于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以及参数τ计算得出，||·||∞为无穷范数；m为选取的分量个数，为正整数。
6、s2：证明者调用kyber的ind-cpa安全公钥加密方案中的密钥生成算法，生成公私钥对(pk，sk)，证明者持有私钥并将公钥公开；
7、其中，kyber的ind-cpa安全公钥加密方案可参考文献如下：
8、bos j，ducas l，kiltz e，et al. crystals-kyber：a cca-secure module-lattice-based kem[c].in：2018 ieee european symposium on security and privacy(euros&p)，2018：353-367.[doi：10.1109/eurosp.2018.00032]。
9、s3：证明者和验证者调用kyber的ind-cpa安全公钥加密方案中的加密算法，分别利用公钥对各自的明文向量进行加密，得到密文向量并公开；
10、s4：验证者对密文向量中的各个分量进行同态计算生成同态密文，完成同态计算后，利用自举刷新同态密文，并公开刷新后的同态密文
11、s5：证明者调用kyber的ind-cpa安全公钥加密方案中的解密算法，利用私钥s对同态密文c进行解密，得到c对应的明文m＝compressq(v-stu，1)∈r2；
12、其中，压缩函数定义为y＝compressq(x，d)＝「(2d/q).x」mod+2d；输入为输出为y∈{0，...，2d-1}，「.」表示四舍五入；mod+为取模运算符，设α为正整数，定义r′＝r mod+α表示r′的取值范围是[0，α)。
13、s6：证明者构造明文0∈r2对应的kyber密文向量随机选取系数界为γ的k+1维多项式向量y，取y的前k维生成向量
14、s7：证明者首先对双方所持数据之间差异值的分布进行估计，以压缩函数的函数值出现跳变时对应的自变量取值点为跳变中心，以截取的差异值的界为半径构造跳变区间，将所持数据c′t.y和的前m个分量通过散列函数计算挑战值h，随后计算应答值并且仅当||z||∞＜γ-l且比对通过时才接受，否则回到步骤s6重新执行，将m、h、z进行连接整合成证明π＝(m，h，z)，并将该证明通过安全信道发送给验证者
15、s8：验证者接收到证明π后，计算明文0∈r2对应的kyber密文向量取应答值z的前k维作为向量利用所持数据的前m个分量并计算哈希值，然后将该哈希值与证明π中的挑战值h进行比较验证，同时验证||z||∞，若计算的哈希值与证明π中的挑战值h不相等或者|z||∞≥γ-l则验证失败，输出0表示拒绝，否则验证成功，输出1表示接受。
16、进一步，步骤s2由证明者..执行，所述的步骤s2具体为：
17、s201：在多项式环rq上随机选取k×k个多项式构成矩阵a，
18、s202：从中心二项分布中均匀随机取样私钥与噪声，
19、s203：计算t＝as+e，输出公钥私钥
20、其中，步骤s202所述的中心二项分布bη定义为：采样(a1，...，aη，b1，...，bη)←{0，1}2η，输出若v∈r，v←βη表示采样v的每个系数服从分布bη，多项式环←表示随机采样操作。
21、进一步，步骤s3所述的加密过程具体为：证明者和验证者调用kyber的ind-cpa安全公钥加密方案中的加密算法enc(pk，mi)对数据(mi)1≤i≤t中各自持有部分进行加密，其中t根据数据长度的不同会发生变化，得到密文并公开。
22、进一步，步骤s4由验证者执行，所述的步骤s4具体为：根据双方公开的密文维度t，任意构造t维输入的函数f(·)，计算同态密文随后利用自举刷新该同态密文，输出刷新后的密文并公开密文c的值。
23、进一步，步骤s5由证明者执行，其所述的解密过程具体为：
24、s501：首先，利用解压缩函数对步骤s4产生的同态密文c中的u、v分别进行解压缩处理，得到其中，表示赋值操作；
25、s502：然后，利用压缩函数解密得到明文m＝compressq(v-stu，1)∈r2；
26、其中，所述的解压缩函数定义为x′＝decompressq(y，d)＝「(q/2d).y」；输入为y∈{0，...，2d-1}、d＜「log2(q)」，输出为
27、进一步，步骤s6由证明者执行，所述的步骤s6具体为：
28、s601：构造明文0∈r2对应的密文
29、s602：随机选取多项式向量
30、s603：若y的每个分量都不可逆，返回步骤s602；
31、s604：取多项式向量y的前k个分量组成新的向量
32、其中，步骤s602所述的：集合sγ中的任意元素t∈r，||t||∞≤γ，用表示集合{t mod±2γ：t∈r}；表示k+1维向量，每个分量取自集合mod±为取模运算符，设α为正偶数(或正奇数)，定义r′＝r mod±α表示r′的取值范围是(-α/2，α/2](或)。
33、进一步，步骤s7由证明者执行，其所述的证明生成过程具体为：
34、s701：计算证明者所持第一部分数据的prover-data1＝c′t·y∈rq，并选其前m个分量prover-data1：＝prover-data1[1：m]；
35、s702：计算证明者所持第二部分数据并选其前m个分量prover-data2：＝prover-data2[：，1：m]；
36、s703：计算挑战值
37、其中，所述的挑战值空间密码散列函数
38、s704：计算应答值
39、s705：计算验证者所持第一部分数据verifier-data1＝c′t·z∈rq，并选其前m个分量verifier-data1：＝verifier-data1[1：m]；
40、s706：取应答值z的前k个分量组成新的向量计算验证者所持第二部分数据并选其前m个分量verifier-data2：＝verifier-data2[：，1：m]；
41、s707：若(compare(prover-data1，verifier-data1)or compare(prover-data2，verifier-data2))＝false或|z||∞≥γ-1，返回步骤s602；
42、s708：输出证明π＝(m，h，z)并将其发送给验证者；
43、其中，比对compare(prover-data1，verifier-data1)表示判断证明者和验证者所持第一部分数据prover-data1和verifier-data1的每个系数是否都同时在或者同时不在跳变区间[-il1+pos，il1+pos]内，如果是，则返回true，否则返回false；同理，比对compare(prover-data2，verifier-data2)表示判断证明者和验证者所持第二部分数据prover-data2和verifier-data2的每个系数是否都同时在或者同时不在跳变区间[-il2+pos，il2+pos]内，如果是，则返回true，否则返回false；其中，证明者和验证者所持第一部分数据差异值对应的跳变区间半径跳变中心计算证明者和验证者所持第二部分数据差异值对应的跳变区间半径跳变中心
44、在所述跳变中心指的是，根据压缩函数的特点，函数值在某些自变量取值点处会发生跳变，例如，当dh＝3时，compressq(x，dh)函数值发生跳变的自变量取值分别为和跳变中心个数和参数dh和有关。
45、进一步，步骤s8由验证者执行，其所述的对接收到的证明π进行验证的过程具体为：
46、s801：首先，利用解压缩函数对步骤s4产生的同态密文c中的u、v分别进行解压缩处理，得到其中，表示赋值操作；
47、s802：计算明文0∈r2对应的密文
48、s803：取证明π中k+1维多项式向量z的前k个分量组成新的向量
49、s804：计算验证者所持第一部分数据verifier-data1＝c′t·z∈rq，并选其前m个分量verifier-data1：＝verifier-data1[1：m]；
50、s805：计算验证者所持第二部分数据并选其前m个分量verifier-data2：＝verifier-data2[：，1：m]；
51、s806：若h≠h(compressq(verifier-data1，dh)，compressq(verifier-data2，dh)).或|z||∞≥γ-l则输出0，表示拒绝，否则输出1，表示接受。
52、具体地，结合参考文献[1]中的算法4和算法5，本发明方法的实现算法具体如下，其算法中调用的子程序与参考文献[1]保持一致：
53、
54、
55、
56、进一步，本发明的正确性：与参考文献[1]作对比，本发明方法降低了证明过程和验证过程的正确性要求；经理论推导：其正确性与分量个数m成正相关，当m≥10时，实施例中正确性验证的通过期望约为1.03次，已经能够满足应用的需求，而实际情况中k》m，相较于参考文献[1]的方法，本发明方法明显减少了循环判断跳变区间的次数，大幅减少了计算量。
57、本发明的安全性：相较于参考文献[1]的方法，本发明避免了传递e1、e2中的下标信息，减少了信息泄露的风险，同时减少了通讯开销，所构造的非交互式零知识证明满足合理性和零知识性，并且其合理性和零知识性可以规约到mlwe和msis困难假设。
58、本发明的有益效果在于：本发明提供一种基于mlwe和msis的高效可验证解密方法，通过改造具有零知识特性的数字签名方案dilithium的无公钥压缩框架，保证kyber的ind-cpa安全公钥加密方案解密的正确性的前提下，构造了一个基于格困难假设mlwe和msis的更加实用、高效、简洁的可验证解密方案，能够用于解决两方安全计算场景中所涉及的可验证解密问题，减少了计算量和通讯开销，提高了安全性。
1.一种基于mlwe和msis的可验证解密方法，由证明者和验证者两方参与进行实现，无需可信第三方参与，其中，为持有私钥的一方，为执行计算的一方，其特征在于：该方法包含以下步骤：
2.根据权利要求1所述的一种基于mlwe和msis的可验证解密方法，其特征在于，步骤s2由证明者执行，所述的步骤s2具体为：
3.根据权利要求1所述的一种基于mlwe和msis的可验证解密方法，其特征在于，步骤s3所述的加密过程具体为：证明者和验证者调用kyber的ind-cpa安全公钥加密方案中的加密算法enc(pk，mi)对数据(mi)1≤i≤t中各自持有部分进行加密，其中t根据数据长度的不同会发生变化，得到密文并公开。
4.根据权利要求1所述的一种基于mlwe和msis的可验证解密方法，其特征在于，步骤s4由验证者执行，所述的步骤s4具体为：根据双方公开的密文维度t，任意构造t维输入的函数f(·)，计算同态密文随后利用自举刷新该同态密文，输出刷新后的密文并公开密文c的值。
5.根据权利要求1所述的一种基于mlwe和msis的可验证解密方法，其特征在于，步骤s5由证明者执行，其所述的解密过程具体为：
6.根据权利要求1所述的一种基于mlwe和msis的可验证解密方法，其特征在于，步骤s6由证明者执行，所述的步骤s6具体为：
7.根据权利要求1所述的一种基于mlwe和msis的可验证解密方法，其特征在于，步骤s7由证明者执行，其所述的证明生成过程具体为：
8.根据权利要求1所述的一种基于mlwe和msis的可验证解密方法，其特征在于，步骤s8由验证者执行，其所述的对接收到的证明π进行验证的过程具体为：
