多变量密码：PMI+加密、Rainbow签名

多变量密码：PMI+加密、Rainbow签名"/>

多变量密码：PMI+加密、Rainbow签名

参考文献：Jintai Ding and Bo-Yin Yang. Multivariate Public Key Cryptography. Post-quantum cryptography. Springer, Berlin, Heidelberg, 2009.

MPKCs

定义

基于多变量的公钥密码系统（multivariate public key cryptosystem），它们的安全性基于求解有限域上非线性方程组属于NP-hard类。为了计算效率，同时也为了安全性，MPKC的带陷门OWF都是多元二次多项式映射（ multivariate quadratic polynomial map）：
P : = ( p 1 ( w 1 , ⋯ , w n ) , ⋯ , p m ( w 1 , ⋯ , w n ) ) \mathbb P := (p_1(w_1,\cdots,w_n),\cdots,p_m(w_1,\cdots,w_n)) P:=(p1​(w1​,⋯,wn​),⋯,pm​(w1​,⋯,wn​))
其中
p k ( w ) : = ∑ i P i k w i + ∑ i Q i k w i 2 + ∑ i > j R i j k w i w j p_k(\pmb w) := \sum_i P_{ik} w_i + \sum_i Q_{ik} w_i^2 + \sum_{i>j} R_{ijk} w_i w_j pk​(www):=i∑​Pik​wi​+i∑​Qik​wi2​+i>j∑​Rijk​wi​wj​
都是 K = F q K = F_q K=Fq​上的（二次）非线性多项式。

MPKCs的优势是加密解密、签名验签的速度很快（比ECDSA还快），缺点是密钥存储的开销很高（几万字节）。

安全性

Problem MQ：求解非线性系统 p 1 ( x ) = ⋯ = p m ( x ) = 0 p_1(x) = \cdots = p_m(x) = 0 p1​(x)=⋯=pm​(x)=0，其中 p i p_i pi​都是关于 x = ( x 1 , ⋯ , x n ) x=(x_1,\cdots,x_n) x=(x1​,⋯,xn​)的二次多项式，所有的系数和所有的变量都属于域 K = F q K=F_q K=Fq​；这个问题是NP-hard的。

当然，随机的二次方程组不一定有陷门。在MPKC中要用到多项式方程组的代数结构，即多元多项式环的理想。这也导致MPKC的安全性实际上不再等同于MP问题的NP困难性。就如同RSA依赖数论，MPKC依赖代数几何（ algebraic geometry）。

标准结构（Standard Bipolar Construction）

MPKC利用两个可逆仿射变换（affine map） S : K n → K n , T : K m → K m S:K^n \to K^n,\,\,T:K^m \to K^m S:Kn→Kn,T:Km→Km来隐藏中心映射（central map） Q : K n → K m Q:K^n \to K^m Q:Kn→Km，即 P = T ∘ Q ∘ S : K n → K m P = T \circ Q \circ S:K^n \to K^m P=T∘Q∘S:Kn→Km
P : w ↦ S x = M S w + c S ↦ Q y ↦ T z = M T y + c T P: \pmb w \overset{S}{\mapsto} \pmb x = M_S\pmb w+c_S \overset{Q}{\mapsto} \pmb y \overset{T}{\mapsto} \pmb z = M_T\pmb y+c_T P:www↦S​xxx=MS​www+cS​↦Q​y​y​​y↦T​zzz=MT​y​y​​y+cT​
其中 Q Q Q是容易求逆的多元二次多项式映射。 S S S用来打乱 w w w， T T T用来打乱 Q Q Q，使得 P P P与随机二次方程组不可区分。一般地， S , T S,T S,T取做线性映射。

上述的 x \pmb x xxx的 x j x_j xj​叫做中心变量（central variables），从 x \pmb x xxx映射到 y i y_i yi​的多项式叫做中心多项式（central polynomials），记做 y i = q i ( x ) y_i=q_i(\pmb x) yi​=qi​(xxx)。一般地，我们总设计 P ( 0 ) = ( p 1 ( 0 ) , ⋯ , p m ( 0 ) ) = 0 P(0)=(p_1(0),\cdots,p_m(0))=0 P(0)=(p1​(0),⋯,pm​(0))=0

MPKCs是算法的三元组：

1. K e y G e n KeyGen KeyGen：设计中心映射 Q Q Q，随机的仿射变换 S , T S,T S,T，公钥为 P = T ∘ Q ∘ S P = T \circ Q \circ S P=T∘Q∘S，私钥为 ( S , T , Q ) (S,T,Q) (S,T,Q)
2. P u b M a p PubMap PubMap：用于加密或者验签， z = P ( w ) \pmb z = P(\pmb w) zzz=P(www)
3. S e c M a p SecMap SecMap：用于解密或者签名， w = S − 1 ∘ Q − 1 ∘ T − 1 ( z ) \pmb w = S^{-1} \circ Q^{-1} \circ T^{-1}(\pmb z) www=S−1∘Q−1∘T−1(zzz)

为了用于加密算法，基本要求是解密得到的信息与原始信息一致，从而 Q : K n → K m Q:K^n \to K^m Q:Kn→Km应为单射，于是选取 n ≤ m n \le m n≤m

为了用于签名算法，需要保证每个消息都有原像，从而 Q : K n → K m Q:K^n \to K^m Q:Kn→Km应为满射，于是选取 n ≥ m n \ge m n≥m

隐形式（Implicit Form）

隐形式的公开多项式：
P ( w , z ) = ( p 1 ( w , z ) , ⋯ , p l ( w , z ) ) = ( 0 , ⋯ , 0 ) P(\pmb w,\pmb z) = (p_1(\pmb w,\pmb z),\cdots,p_l(\pmb w,\pmb z)) = (0,\cdots,0) P(www,zzz)=(p1​(www,zzz),⋯,pl​(www,zzz))=(0,⋯,0)
对应的中心多项式为：
Q ( x , y ) = ( q 1 ( x , y ) , ⋯ , q l ( x , y ) ) = ( 0 , ⋯ , 0 ) Q(\pmb x,\pmb y) = (q_1(\pmb x,\pmb y),\cdots,q_l(\pmb x,\pmb y)) = (0,\cdots,0) Q(xxx,y​y​​y)=(q1​(xxx,y​y​​y),⋯,ql​(xxx,y​y​​y))=(0,⋯,0)
需要满足以下性质：

1. 给定任意的 x ′ x' x′，求解关于 y y y的 Q ( x ′ , y ) = 0 Q(x',y)=0 Q(x′,y)=0是容易的
2. 给定任意的 y ′ y' y′，求解关于 x x x的 Q ( x , y ′ ) = 0 Q(x,y')=0 Q(x,y′)=0是容易的
3. 方程 Q ( x ′ , y ) = 0 Q(x',y)=0 Q(x′,y)=0是线性的，而方程 Q ( x , y ′ ) = 0 Q(x,y')=0 Q(x,y′)=0是非线性的

那么我们构造
P = Q ( S ( w ) , T − 1 ( z ) ) = ( 0 , ⋯ , 0 ) P = Q(S(\pmb w),T^{-1}(\pmb z)) = (0,\cdots,0) P=Q(S(www),T−1(zzz))=(0,⋯,0)
其中 S , T S,T S,T是可逆仿射变换。

MPKCs是算法的三元组：

1. K e y G e n KeyGen KeyGen：设计中心映射 Q Q Q，随机的仿射变换 S , T S,T S,T，公钥为 P P P，私钥为 ( S , T , Q ) (S,T,Q) (S,T,Q)
2. P u b M a p PubMap PubMap：用于加密或者验签，求解方程 P ( w , z ) = 0 P(\pmb w,\pmb z)=0 P(www,zzz)=0得到 z \pmb z zzz（因为 Q ( x ′ , y ) = 0 Q(x',y)=0 Q(x′,y)=0是线性的，容易求解）
3. S e c M a p SecMap SecMap：用于解密或者签名，求解方程 Q ( S ( w ) , T − 1 ( z ) ) Q(S(\pmb w),T^{-1}(\pmb z)) Q(S(www),T−1(zzz))得到 w \pmb w www

MI

1988年 Matsumoto 和 Imai 提出的一种基于多变量的加密方案。

令 K = G F ( q ) K=GF(q) K=GF(q)，它的 n n n次扩张 L / K L/K L/K，可以将 L L L视作 K K K上的向量空间。考虑 K − K- K−线性双射 ϕ : L → K n \phi:L \to K^n ϕ:L→Kn，令 Q ˉ : L → L \bar Q:L \to L Qˉ​:L→L是可逆映射，做映射 Q : K n → K n Q:K^n \to K^n Q:Kn→Kn
Q = ϕ ∘ Q ˉ ∘ ϕ − 1 Q = \phi \circ \bar Q \circ \phi^{-1} Q=ϕ∘Qˉ​∘ϕ−1
Matsumoto 和 Imai 建议选取 K K K的特征为 2 2 2，同时选取
Q ˉ : x ↦ y : = x 1 + q α \bar Q: x \mapsto y:= x^{1+q^\alpha} Qˉ​:x↦y:=x1+qα
其中 g c d ( 1 + q α , q n − 1 ) = 1 gcd(1+q^\alpha,q^n-1)=1 gcd(1+qα,qn−1)=1，从而存在逆元 h ( 1 + q α ) ≡ 1 m o d q n − 1 h(1+q^\alpha) \equiv 1 \mod q^n-1 h(1+qα)≡1modqn−1，那么 Q Q Q可逆
Q ˉ − 1 : y ↦ y h \bar Q^{-1}: y \mapsto y^h Qˉ​−1:y↦yh
上述得到的映射 Q Q Q被记做 C n , q , α ∗ C^*_{n,q,\alpha} Cn,q,α∗​，简记为 C ∗ C^* C∗；它总是二次的（quadratic），因为 L L L的 K − K- K−自同构（Frobenius map） x ↦ x q α x \mapsto x^{q^\alpha} x↦xqα的线性性。 C ∗ C^* C∗的一个重要性质是，
y q α − 1 = x q 2 α − 1 y^{q^\alpha-1} = x^{q^{2\alpha}-1} yqα−1=xq2α−1
利用标准结构构造MPKC，使用 K n K^n Kn上的仿射线性可逆映射来隐藏 C ∗ C^* C∗的结构。MI方案被攻破了，由于 C ∗ C^* C∗的双线性关系（bilinear relations）

PMI+

下面给出更安全的 Perturbed Matsumoto-Imai Plus 加密方案。

同样的， n n n次域扩张 L / K L/K L/K， K = G F ( 2 ) K=GF(2) K=GF(2)，映射 C ∗ C^* C∗的定义同上，然后

1. 选择关于 x \pmb x xxx的 r r r个线性型（linear forms） v = ( v 1 , ⋯ , v r ) \pmb v = (v_1,\cdots,v_r) vvv=(v1​,⋯,vr​)，将 v ( x ) \pmb v(\pmb x) vvv(xxx)作为扰动项（perturbation term）
2. 选择关于 v \pmb v vvv的 n n n个随机二次函数 f = ( f 1 , ⋯ , f n ) \pmb f = (f_1,\cdots,f_n) f​f​​f=(f1​,⋯,fn​)，
3. 选择关于 x \pmb x xxx的 a a a个随机二次函数 g = ( g 1 , ⋯ , g a ) \pmb g = (g_1,\cdots,g_a) g​g​​g=(g1​,⋯,ga​)，

定义中心映射为 Q : = ( C ∗ + f ( v ) ) ∥ g Q:=(C^*+\pmb f(\pmb v)) \| \pmb g Q:=(C∗+f​f​​f(vvv))∥g​g​​g，从 K n K^n Kn映射到 K n + a K^{n+a} Kn+a上，其各个分量多项式为
q i ( x ) : = { c i ∗ ( x ) + f i ( v ( x ) ) , i = 1 , ⋯ , n g i − n ( x ) , i = n + 1 , ⋯ , n a q_i(\pmb x) := \left\{ \begin{aligned} c_i^*(\pmb x) + f_i(\pmb v(\pmb x)),&& i=1,\cdots,n\\ g_{i-n}(\pmb x),&& i=n+1,\cdots,n_a \end{aligned} \right. qi​(xxx):={ci∗​(xxx)+fi​(vvv(xxx)),gi−n​(xxx),​​i=1,⋯,ni=n+1,⋯,na​​

最后的 a a a个分量用于保证密文的正确性。给定 y \pmb y y​y​​y，为了求逆 x : = Q − 1 ( y ) \pmb x := Q^{-1}(\pmb y) xxx:=Q−1(y​y​​y)，令 h h h是求逆 C ∗ C^* C∗的指数。我们先将 y \pmb y y​y​​y最后的 a a a个分量丢弃，然后随机猜测：将 y \pmb y y​y​​y的前 n n n个分量记做 y ′ \pmb y' y​y​​y′，然后对于所有可能的扰动项的值 b ∈ K r \pmb b \in K^r bbb∈Kr，计算 x ← ( y ′ − f ( b ) ) h \pmb x \leftarrow (\pmb y'- \pmb f(\pmb b))^h xxx←(y​y​​y′−f​f​​f(bbb))h，然后检验是否满足 v ( x ) = b \pmb v(\pmb x) = \pmb b vvv(xxx)=bbb。如果找到了满足等式的，那么这个 x \pmb x xxx就满足 y = Q ( x ) \pmb y = Q(\pmb x) y​y​​y=Q(xxx)，它就是 y \pmb y y​y​​y的原像。

因此，解密算法中需要尝试 2 r 2^r 2r次，这比直接求逆 C ∗ C^* C∗慢了 2 r 2^r 2r倍。一种参数的选择为： ( n , r , a , α ) = ( 136 , 6 , 18 , 8 ) (n,r,a,\alpha) = (136,6,18,8) (n,r,a,α)=(136,6,18,8)，公钥大小 167688 B 167688B 167688B，私钥大小 26324 B 26324B 26324B，设计安全性（design security）为 2 83 2^{83} 283

Oil and Vinegar

对于 o , v ∈ N + o,v \in N^+ o,v∈N+，令 n = v + o n = v+o n=v+o，定义如下的油醋多项式
p ( x 1 , ⋯ , x n ) = ∑ i = 1 v ∑ j = i v α i j x i x j + ∑ i = 1 v ∑ j = v + 1 n β i j x i x j + ∑ i = 1 n γ x i + δ p(x_1,\cdots,x_n) = \sum_{i=1}^v \sum_{j=i}^v \alpha_{ij} x_ix_j + \sum_{i=1}^v \sum_{j=v+1}^n \beta_{ij} x_ix_j + \sum_{i=1}^n \gamma x_i + \delta p(x1​,⋯,xn​)=i=1∑v​j=i∑v​αij​xi​xj​+i=1∑v​j=v+1∑n​βij​xi​xj​+i=1∑n​γxi​+δ

1. 醋变量（vinegar variables）： x 1 , ⋯ , x v x_1,\cdots,x_v x1​,⋯,xv​
2. 油变量（oil variables）： x v + 1 , ⋯ , x n x_{v+1},\cdots,x_n xv+1​,⋯,xn​
3. Not fully mixed：
   • 不含 o × o o \times o o×o个油油项
   • 二次项： v × v v \times v v×v个醋醋项、 v × o v \times o v×o个油醋项
   • 线性项： v v v个醋项、 o o o个油项。

定义中心映射 Q : K n → K m Q:K^n \to K^m Q:Kn→Km，它有 o o o个分量
Q ( x ) = ( q 1 ( x ) , ⋯ , q o ( x ) ) Q(\pmb x) = (q_1(\pmb x), \cdots, q_o(\pmb x)) Q(xxx)=(q1​(xxx),⋯,qo​(xxx))

每个分量都为油醋多项式，系数随机取自域 K K K，没有常数项。

容易看出，只要确定了所有的醋变量 x 1 , ⋯ , x v x_1,\cdots,x_v x1​,⋯,xv​的值，那么油醋多项式就变成了仅关于油变量 x v + 1 , ⋯ , x n x_{v+1},\cdots,x_n xv+1​,⋯,xn​的线性多项式。我们随机确定醋变量的值，那么 Q Q Q中的 o o o个多项式将成为关于 o o o个油变量的线性系统，容易求解。

令公钥为 P = Q ∘ S P = Q \circ S P=Q∘S，这里 S S S是 K n K^n Kn上的可逆线性映射。将 ( Q , S ) (Q,S) (Q,S)作为私钥。令 m = o = v = n / 2 m=o=v=n/2 m=o=v=n/2，可构造原始的油醋签名方案（Oil and Vinegar signature scheme，OV）。由于油变量与醋变量数量是相等的，这导致可以用线性代数给予十分有效的Kipnis-Shamir攻击。当 o < v o<v o<v时，得到不平衡油醋签名方案（unbalance Oil and Vinegar signature scheme，UOV）

Rainbow

彩虹算法是一种不平衡油醋结构的签名算法。

设置严格递增系列 0 < v 1 < ⋯ < v u + 1 = n 0 < v_1 < \cdots < v_{u+1} = n 0<v1​<⋯<vu+1​=n，令 V l = [ v l ] = { 1 , ⋯ , v l } V_l=[v_l]=\{1,\cdots,v_l\} Vl​=[vl​]={1,⋯,vl​}，那么 ∅ ⊂ V 1 ⊂ ⋯ ⊂ V u + 1 = [ n ] \empty \sub V_1 \sub \cdots \sub V_{u+1} = [n] ∅⊂V1​⊂⋯⊂Vu+1​=[n]。定义一阶差分 o l : = v l + 1 − v l o_l := v_{l+1}-v_l ol​:=vl+1​−vl​，以及对应的 O l : = V l + 1 \ V l O_l := V_{l+1} \backslash V_l Ol​:=Vl+1​\Vl​

令中心映射 Q Q Q的分量为 q v 1 + 1 , q v 1 + 2 , ⋯ , q n q_{v_1+1},q_{v_1+2},\cdots,q_{n} qv1​+1​,qv1​+2​,⋯,qn​，一共 n − v 1 n-v_1 n−v1​个多项式，它们定义为：
k ∈ Q l , y k = q k ( x ) = ∑ i = 1 v l ∑ j = i v l + 1 α i j ( k ) x i x j + ∑ i < v l + 1 β i ( n ) x i k \in Q_l,\,\, y_k = q_k(\pmb x) = \sum_{i=1}^{v_l} \sum_{j=i}^{v_{l+1}} \alpha_{ij}^{(k)} x_ix_j + \sum_{i < v_{l+1}} \beta_i^{(n)} x_i k∈Ql​,yk​=qk​(xxx)=i=1∑vl​​j=i∑vl+1​​αij(k)​xi​xj​+i<vl+1​∑​βi(n)​xi​

明显，对于 k ∈ O l k \in O_l k∈Ol​的多项式 q k q_k qk​，它不含 i , j ∈ O l i,j \in O_l i,j∈Ol​的交叉项 x i x j x_ix_j xi​xj​（油油项）；从而只要给定所有的函数值 y i , v l < i ≤ v l + 1 y_i,\,\,v_l < i \le v_{l+1} yi​,vl​<i≤vl+1​以及所有的醋变量 x j , j ≤ v l x_j,\,\,j \le v_l xj​,j≤vl​，那么方程组
y v l + 1 = q v l + 1 ( x 1 , ⋯ , x v l ; x v l + 1 , ⋯ , x v l + 1 ; 0 , ⋯ , 0 ) y v l + 2 = q v l + 2 ( x 1 , ⋯ , x v l ; x v l + 1 , ⋯ , x v l + 1 ; 0 , ⋯ , 0 ) ⋮ y v l + 1 = q v l + 1 ( x 1 , ⋯ , x v l ; x v l + 1 , ⋯ , x v l + 1 ; 0 , ⋯ , 0 ) \begin{aligned} y_{v_l+1} = q_{v_l+1}(x_1,\cdots,x_{v_l};x_{v_l+1},\cdots,x_{v_{l+1}};0,\cdots,0)\\ y_{v_l+2} = q_{v_l+2}(x_1,\cdots,x_{v_l};x_{v_l+1},\cdots,x_{v_{l+1}};0,\cdots,0)\\ \vdots\\ y_{v_{l+1}} = q_{v_{l+1}}(x_1,\cdots,x_{v_l};x_{v_l+1},\cdots,x_{v_{l+1}};0,\cdots,0)\\ \end{aligned} yvl​+1​=qvl​+1​(x1​,⋯,xvl​​;xvl​+1​,⋯,xvl+1​​;0,⋯,0)yvl​+2​=qvl​+2​(x1​,⋯,xvl​​;xvl​+1​,⋯,xvl+1​​;0,⋯,0)⋮yvl+1​​=qvl+1​​(x1​,⋯,xvl​​;xvl​+1​,⋯,xvl+1​​;0,⋯,0)​

是关于 O l O_l Ol​的 x v l + 1 , ⋯ , x v l + 1 x_{v_l+1},\cdots,x_{v_{l+1}} xvl​+1​,⋯,xvl+1​​的 o l o_l ol​个线性方程，因此计算油变量 x v l + 1 , ⋯ , x v l + 1 x_{v_l+1},\cdots,x_{v_{l+1}} xvl​+1​,⋯,xvl+1​​是容易的。

为了对 Q Q Q求逆，先随机选取 V 1 V_1 V1​对应的 x 1 , ⋯ , x v 1 x_1,\cdots,x_{v_1} x1​,⋯,xv1​​。那么 O 1 O_1 O1​所对应的那 o 1 o_1 o1​个 q k ( ⋅ ) q_k(\cdot) qk​(⋅)成为仅关于 x v 1 + 1 , ⋯ , x v 2 x_{v_1+1},\cdots,x_{v_2} xv1​+1​,⋯,xv2​​的线性系统，我们便获得了 x 1 , ⋯ , x v 2 x_1,\cdots,x_{v_2} x1​,⋯,xv2​​的值。那么 O 2 O_2 O2​对应的那 o 2 o_2 o2​个 q k ( ⋅ ) q_k(\cdot) qk​(⋅)成为仅关于 x v 2 + 1 , ⋯ , x v 3 x_{v_2+1},\cdots,x_{v_3} xv2​+1​,⋯,xv3​​的线性系统，我们便获得了 x 1 , ⋯ , x v 3 x_1,\cdots,x_{v_3} x1​,⋯,xv3​​的值。继续迭代，可以获得全部的 x 1 , ⋯ , x n x_1,\cdots,x_n x1​,⋯,xn​的值。从而中心映射 Q Q Q是容易求逆的。

注意，求逆算法 Q − 1 Q^{-1} Q−1是随机的，同一个 y \pmb y y​y​​y会对应很多的 x \pmb x xxx，因此构造出的MPKC可以用于签名算法，但不能直接用做加密算法。

实现技巧

对于 K = G F ( q ) K=GF(q) K=GF(q)，一般选取 q = 2 k q=2^k q=2k， k k k很小。从而

1. K K K中元素可以被存储在一个字节里
2. K K K中元素的加法就是字节的异或
3. K K K中元素的乘法可以这么计算，
   • 寻找 K K K的本原元 g g g，那么非零元都可以表示为 g i g^i gi
   • 制作对数表 { x : i ∣ x = g i } \{ x:i|x=g^i \} {x:i∣x=gi}和指数表 { j : g j } \{ j:g^j \} {j:gj}
   • 为了计算 x , y ∈ K x,y \in K x,y∈K的乘积，先查对数表得到 log ⁡ g x , log ⁡ g y \log_g x,\log_g y logg​x,logg​y，然后用它们的和 log ⁡ g x + log ⁡ g y \log_g x + \log_g y logg​x+logg​y来索引指数表，得到 x ⋅ y x \cdot y x⋅y
4. 如果只做乘法，那么可以将所有元素 x x x都存储为离散对数 log ⁡ g x \log_g x logg​x，计算乘法时只需要计算加法即可

对于扩域 L / K L/K L/K上的运算，视作 K K K上多项式的加法和乘法。乘法可以使用 schoolbook乘法、Karatsuba算法、NTT算法，然后再做长除法或者Barrett算法。

对于 C ∗ C^* C∗的计算，由于 x ↦ x q α + 1 = x q α x x \mapsto x^{q^\alpha+1}=x^{q^\alpha}x x↦xqα+1=xqαx，且 ϕ : x ↦ x q α \phi:x \mapsto x^{q^\alpha} ϕ:x↦xqα是域 L / K L/K L/K上的线性映射：

1. ( x + y ) q α = x q α + y q α (x+y)^{q^\alpha} = x^{q^\alpha} + y^{q^\alpha} (x+y)qα=xqα+yqα
2. ( k x ) q α = k x q α (kx)^{q^\alpha} = kx^{q^\alpha} (kx)qα=kxqα

因此可以将 ϕ \phi ϕ写作矩阵 M M M（每一列是单位向量的像），令 L = G F ( q ) n L=GF(q)^n L=GF(q)n是向量空间。从而 C ∗ ( x ) = ( M x ) ⋅ x C^*(x) = (Mx) \cdot x C∗(x)=(Mx)⋅x，线性映射花费 n 2 n^2 n2次操作，多项式模乘花费 2 n 2 2n^2 2n2次操作。

效率对比

可以看出，MPKC的运算速度很快，但密钥规模过大。