基于多变量多项式对消息匿名环签名的方法

摘要

本发明公开了一种基于多变量多项式对消息匿名环签名的方法，该方法按照以下步骤实施，生成系统参数，密钥生成，环签名生成，环签名的验证。基于传统密码体制的环签名方法，在量子计算机下其安全性受到威胁，而本发明基于多变量公钥密码体制的环签名方法解决了现有的环签名体制在量子计算下不安全的缺陷。本发明的方法既具有安全性又具有计算效率高的优点。

主权项

1.基于多变量多项式对消息匿名环签名的方法，其特征在于，该方法按照以下步骤实施：步骤1.生成系统参数1)设置k＝GF(q)是特征为p的有限域，其中q＝p^l，l是一个正整数；2)令是有限域k的n次扩张，其中n是一个正整数，g(x)是有限域k上的一个n次不可约多项式；3)令m为多变量方程组中方程的个数，n为变量的个数；4)选择H：{0，1}^*→k^m为密码学安全的抗碰撞单向不可逆哈希函数，系统参数为(k，q，p，l，m，n，H)；步骤2.密钥生成1)假设环中有t个用户，设为U＝{u₀，u₁，…，u_t-1}；2)根据多变量公钥密码体制，每个用户u_i(0≤i≤t-1)选择F_i是从kⁿ到k^m的可逆映射，F_i满足：a)F_i(x₁，…，x_n)＝(f_i1，…，f_im)，其中f_ij∈k[x₁，…，x_n]，j＝1，…，m；b)任何方程F_i(x₁，…，x_n)＝(y′₁，…，y′_m)，都易于求解；3)每个用户u_i(0≤i≤t-1)选择其中L_1i是从k^m到k^m的随机选择的一个可逆仿射变换L_1i(x₁，…，x_m)＝M_1i(x₁，…，x_m)^T+a_1i，其中M_1i是有限域k上的一个m×m的可逆矩阵，a_1i是有限域k上的一个m×1的列向量；4)每个用户u_i(0≤i≤t-1)选择L_2i是从kⁿ到kⁿ的随机选择的一个可逆仿射变换L_2i(x₁，…，x_n)＝x_2i(x₁，…，x_n)^T+a_2i，其中M_2i是有限域k上的一个n×n的可逆矩阵，a_2i是有限域k上的一个n×1的列向量；5)每个用户u_i(0≤i≤t-1)公布其公钥${\bar{F}}_i(x_1,...,x_n)=({\bar{f}}_{i1},...,{\bar{f}}_{\mathrm{im}})$其中每一个都是k[x₁，…，x_n]中的多项式；6)每个用户u_i(0≤i≤t-1)保密其私钥SK_i＝{L_1i，F_i，L_2i}；7)环中的t个用户的公钥集记为步骤3.环签名生成假设环成员u_π(0≤π≤t-1)代表环成员中所有成员U＝{u₀，u₁，…，u_t-1}对消息M∈{0，1}^*进行签名，环中的t个用户的公钥集记为u_π的公钥为私钥为SK_π＝{L_1π，F_π，L_2π}，签名者u_π计算环签名的步骤如下：1)签名者u_π随机选取r∈kⁿ，计算$c_{\pi +1\mathrm{mod}t}=H\left(L\right|\left|M\right|\left|{\bar{F}}_{\pi }\left(r\right)\right);$2)对i＝π+1，...，t-1，0，1，...，π-1，签名者u_π随机选取r_i∈kⁿ，计算$c_{i+1\mathrm{mod}t}=H\left(L\right|\left|M\right||{\bar{F}}_i\left(r_i\right)-c_i)\in k^m;$3)签名者u_π利用私钥计算$r_{\pi }=L_{2\pi }^{-1}{F}_{\pi }^{-1}{L}_{1\pi }^{-1}({\bar{F}}_{\pi }\left(r\right)+c_{\pi });$4)输出消息M∈{0，1}^*关于环的环签名σ＝(c₀，r₀，r₁，...，r_t-1)；步骤4.环签名的验证给定消息M∈{0，1}^*关于环的环签名σ＝(c₀，r₀，r₁，...，r_t-1)，验证者所有环成员公钥集合验证过程如下：1)对i＝0，1，...，t-1，计算$c_{i+1}=H\left(L\right|\left|M\right||{\bar{F}}_i\left(r_i\right)-c_i)\in k^m$得到c_t；2)验证c_t＝c₀是否成立，如成立，接受该环签名；否则拒绝签名。