多变量密码学（Multivariate cryptography）是在有限域 $F$ 上多元多项式上实现的密码学，多用于非对称加密，亦称多变量公钥密码学（Multivariate Public Key Cryptography abbr. MPKC）。通常使用二次多项式（Multivariate Quadratic abbr. MQ ）来保证其非线性，多元多次多项式的求解问题证明是 NP-Complete 的，因此 MPKC 是后量子密码体系内重要的研究方向。该篇博客是 Multivariate Public Key Cryptography 文献中有关 Matsumoto-Imai Cryptosystem 以及其变体的内容研究总结。

 

Matsumoto-Imai Cryptosystem

MI 是第一个影响比较大的 MQPC 体制，假设 k 是一个有限域， MI 不是直接在 $k^n$ 向量空间上寻找可逆映射，而是在 k 的 n 次扩域上寻找可逆的映射。由于其高效率和在实际应用中的潜在应用而引起了广泛的关注，事实上，MI密码系统被日本政府作为备选的安全标准。然而，在最终的轮之前，Jacques Patarin 使用线性化方程的代数攻击破解了 MI [Patarin, 1995]。该方法利用了MI中某些特定的隐藏代数结构。

通常情况下，人们会认为这就是MI的结局，但是接下来的故事走向了相反的方向。其中一个原因是 MI 密码系统代表了概念层面上的根本性突破，它为该领域带来了全新的数学思想，并因此得到了广泛的探索和推广。另一个原因是MI密码系统的许多新变体似乎具有很大的潜力，尤其是 Sflash 签名方案被选为 New European Schemes for Signatures, Integrity, and Encryption project [NESSIE, 1999] 的标准方案。

 

MI 的基本符号系统

一些符号说明：

• 定义 $k$ : a. finite field of characteristic two and cardinality q. 即形如 $GF (2^a)$ 的有限域 ($characteristic(k) = 2$ 非必需条件)。

• 定义 $k[x]$ :定义在有限域 k 上的多项式环，$k\left[x_1, \ldots, x_n\right]$ 为有限域 k 上多元多项式环。

• 定义 $K=k[x] / g(x)$ : a degree $n$ extension of $k$ , $g(x) \in k[x]$ to be any irreducible polynomial of degree $n$. 多项式环 $k[x]$ 模 $g(x)$ 的商环， 当 $g(x)$ 为 $k[x]$ 不可约多项式是，$K$ 是一个有限域，即 k 的 n 次扩域。

• 标准线性同构 : Let $\phi: K \longrightarrow k^n$ be the standard $k$-linear isomorphism between $K$ and $k^n$ given by ：

  $$\phi\left(a_0+a_1 x+\cdots+a_{n-1} x^{n-1}\right)=\left(a_0, a_1, \ldots, a_{n-1}\right)$$

• 定义 $K$ 上映射 $\tilde{F}$ ：

  $$\tilde{F}(X)=X^{1+q^0}$$

  其中 $0<\theta<n, \ \operatorname{gcd}\left(q^\theta+1, q^n-1\right)=1$，保证上述映射的可逆性。

• 定义 $K$ 上映射 $\tilde{F}$ 的逆 $\tilde{F}^{-1}$ ：

  $$\tilde{F}^{-1}(X)=X^t$$

  其中 t 满足 ： $t\left(1+q^\theta\right) \equiv 1 \bmod \left(q^n-1\right)$

• 定义 $k^n$ 上映射 $F$ ：

  $$F\left(x_1, \ldots, x_n\right)=\phi \circ \tilde{F} \circ \phi^{-1}\left(x_1, \ldots, x_n\right)=\left(f_1, \ldots, f_n\right)$$

  其中 $f_1, \ldots, f_n \in k\left[x_1, \ldots, x_n\right]$

• 定于 $L_1 , \ L_2$ 为 $k^n$ 上可逆仿射变换，即：

  $$L(\vec{x}) = A \cdot \vec{x} + b,\ \vec x \ \in k^n$$

  其中 $A$ 是 $k$ 上 $n \times n$ 的可逆矩阵，b 是 k 上的 n 维向量。

• 定义 $k^n$ 上映射 $\bar{F}$ ：

  $$\bar{F}\left(x_1, \ldots, x_n\right)=L_1 \circ F \circ L_2\left(x_1, \ldots, x_n\right)=\left(\bar{f}_1, \ldots, \bar{f}_n\right)$$

  其中 $\bar{f}_1, \ldots, \bar{f}_n \in k\left[x_1, \ldots, x_n\right]$

则上述定义的各类映射一个完整的关系示意图如下：

 

MI 公钥加密

公钥 Public Key

• 有限域 $k$ 以及其加法、乘法代数结构。
• 映射 $\bar{F}$ 产生的 n 个多项式 ： $\bar{f}_1, \ldots, \bar{f}_n \in k\left[x_1, \ldots, x_n\right]$

私钥 Private Key

• 参数 $k^n$ 上可逆仿射变换： $L_1 , \ L_2$
• 参数 $\theta$ （可公开，因为 $\theta$ 的取值只在 0 到 n 之间，数量级很小）

编码

给定明文消息 m，按照有限域 k 的阶（即为 q）进行 q 进制分解得到数组 M （长度为 n），在有限域 $k$ 上定义编码，对 M 中每个数进行编码，得到 $k^n$ 上向量 $\left(x_1^{\prime}, \ldots, x_n^{\prime}\right)$ .

$$\textsf{Bytes} \rightarrow \mathbb Z_{q^n} \rightarrow \mathbb Z_{q}^n \rightarrow k^n$$

加密过程 Encryption

给定 $k^n$ 上明文向量 $m = \left(x_1^{\prime}, \ldots, x_n^{\prime}\right)$ ，密文 $\left(y_1^{\prime}, \ldots, y_n^{\prime}\right)$ 即

$$y_i^{\prime}=\bar{f}_i\left(x_1^{\prime}, \ldots, x_n^{\prime}\right)$$

解密过程 Decryption

给定密文 $\left(y_1^{\prime}, \ldots, y_n^{\prime}\right)$，明文就为求上述多项式的逆 ：

$$\begin{aligned} \bar{F}^{-1}\left(y_1^{\prime}, \ldots, y_n^{\prime}\right) & =L_2^{-1} \circ F^{-1} \circ L_1^{-1}\left(y_1^{\prime}, \ldots, y_n^{\prime}\right) \\ & =L_2^{-1} \circ \phi \circ \tilde{F}^{-1} \circ \phi^{-1} \circ L_1^{-1}\left(y_1^{\prime}, \ldots, y_n^{\prime}\right) . \end{aligned}$$

由于 $\bar{F}^{-1}$ 次数很高，一般计算过程如下：

• First compute $\left(z_1^{\prime}, \ldots, z_n^{\prime}\right)=L_1^{-1}\left(y_1^{\prime}, \ldots, y_n^{\prime}\right)$
• Then compute $\left(\bar{z}_1, \ldots, \bar{z}_n\right)=\phi \circ \tilde{F}^{-1} \circ \phi^{-1}\left(z_1^{\prime}, \ldots, z_n^{\prime}\right)$;
• Finally compute $\left(x_1^{\prime}, \ldots, x_n^{\prime}\right)=L_2^{-1}\left(\bar{z}_1, \ldots, \bar{z}_n\right)$.

 

思考：

• Q： 为什么说私钥是 $L_1,L_2,\theta$，不能直接保存 $\bar{F}^{-1}$ 函数为私钥吗？
• Q ：为什么要选取形如 $q^\theta+1$ 这样的指数？

在尝试使用 sagemath 实现 MI 公钥体制后，笔者认为上述问题的答案都是因为：为了计算效率，由于 $\bar{F}^{-1}$ 函数次数太高，如果我们使用变量 $\left(y_1^{\prime}, \ldots, y_n^{\prime}\right)$ 直接计算表达式，相当于在 n + 1 个变量的多项式商环上求乘法幂，计算量（随着n迅速增大）是非常之大的，在 sagemath 中选择 $k = GF(2^8), n = 6$ 计算就已经非常慢了，但是如果带入具体值进行计算，相当于在 1 个变量的多项式商环上求乘法幂，其速度显著提升。

选择 $q^\theta+1 = 2^{a \cdot \theta } + 1$ 这样的指数，第一感觉是便于快速幂计算，这样即使公钥的次数很大，乘法计算次数也比较少，但是考虑代数结构的话，计算方法是特别简单的，因为形如 $X^{q^\theta}$ 这样的映射是著名的 Frobenius map，有着很好的性质。下一节就详细讨论了 MI 的公钥次数。

 

MI 的公钥次数

Frobenius map：

关于 Frobenius map 更多的性质可以参考下面两个链接：

• 中文参考 ：Frobenius同态.
• 英文参考：Frobenius endomorphism

在本文中，我们只关注次数上的性质。

 

有限域上的多项式环

首先公钥 $\bar{f}_1, \ldots, \bar{f}_n \in k\left[x_1, \ldots, x_n\right]$ ，但是 $k$ 是一个阶为 q 的有限域，则 $x^q = x \quad \forall \ x \in k$，即

$$\operatorname{Fun}\left(k^n, k\right)=k\left[x_1, \ldots, x_n\right] /\left(x_1^q-x_1, \ldots, x_n^q-x_n\right)$$

我们直接用 $k\left[x_1, \ldots, x_n\right]$ 表示上述商环，因为在有限域上两者是等价的。

同样的，$K$ 是有限域 $k$ 的 n 次扩域，其阶为 $q^n$， 定义多项式环 $K[X]$，等价于 $K[X] /\left(X^{q^n}-X\right)$。

 

而在公钥的产生过程中 $T_i(X)=X^{q^i}$ on $K$, for $i=0,1, \ldots, n-1$，就是著名的 Frobenius maps，实际上，这些映射就是伽罗瓦群 Galois group : $\operatorname{Gal}(K/k)$ : the group of all automorphisms of $K$ that fix the subfield $k$. 也就是 $K$ 上保持子域 $k$ 不变的所有自同构。

 

上面都是一些数学上的概念，这里我们用的是 Frobenius maps 的性质， 重点在于对于任意 $H(X) \in$ $K[X]$，我们想了解 $\phi \circ H \circ \phi^{-1}$ 与 $H(x)$ 的次数之间的关系。

• $q$ Hamming weight （q-汉明权值）定义：对于任意单项式 $X^e \in K[X]$，其 q-汉明权值为对指数 e 做 q 进制展开后的系数之和，比如 $q = 2, e = 0b11011$ , 其 q-汉明权值为 4。
• 对于多项式 $H(X) \in K[X]$ ，其 q-汉明权值为其单项式q-汉明权值的最大值。

对于 $H(X) \in K[X]$ ， 其 q-汉明权值为 d，则 $\phi \circ H \circ \phi^{-1}$ 的最高项次数也是 $d$ ，在 MI 公钥体系中选取的指数 e 是 $q^\theta + 1$，其 q-汉明权值为 2，$\phi \circ \tilde F \circ \phi^{-1}$ 的次数也是 2， $L_1,L_2$ 都是线性变换，不会改变次数，因此 MI 公钥算法得到的多项式次数一定不大于 2。

另外，经过推敲，虽然文献上没有提到，笔者觉得值得说明的一点是 $\tilde F$ 的快速计算，这里就用到了 Frobenius maps 保持环同态的性质，也就是：

$$\begin{aligned} \tilde F(X) & = X^{q^\theta + 1} \\ & = (\sum_0^{n-1} l_i(x_1,\cdots,x_n) x^i) (\sum_0^{n-1} l_i(x_1,\cdots,x_n) x^i)^{q^\theta} \\ & = (\sum_0^{n-1} l_i(x_1,\cdots,x_n) x^i) (\sum_0^{n-1} l_i(x_1,\cdots,x_n)^{q^\theta} x^{iq^\theta}) \\ & = (\sum_0^{n-1} l_i(x_1,\cdots,x_n) x^i) (\sum_0^{n-1} l_i(x_1,\cdots,x_n) x^{iq^\theta}) \end{aligned}$$

我们实际上只需要进行一次多项式乘法！另外 给定 $H(X) \in K[X]$ ， 其 q-汉明权值为 d，则 $\phi \circ H \circ \phi^{-1}$ 的最高项次数也是 $d$ 这个结论也可以从上述计算过程中推导出来！ 一个通用性的证明也是简单的，这里不再给出。

上述优化并没有在 sagemath 上实现，因此直接利用库函数计算多项式的次幂速度会很慢。

 

MI 的密钥尺寸与计算效率

MI 的公钥是 n 个多项式 $\bar{f}_1, \ldots, \bar{f}_n \in k\left[x_1, \ldots, x_n\right]$，每个多项式有最多有 $n+1 + \frac{n(n+1)}{2} = \frac{(n+1)(n+2)}{2}$ 项（单项式），即 $\frac{(n+1)(n+2)}{2}$ 个定义在有限域 k 上的系数，当 $q = 2$ 时，由于$x^2 = x$，上述次数衰减至 $n + 1$，因此 GF(2) 上的 MI 密钥尺寸会显著减少。

与RSA相比，这个参数是相当大的，即使我们选择 $k = GF(2^8),\ n = 32$，这是Matsumoto-Imai最初在1988年提出的参数。然而，对于像RSA这样的系统，还有其他的考虑因素，特别是软件，而对于mpkc，实现只需要最少的工作，而不仅仅是公钥。

虽然 MI 的公钥尺寸可能比RSA等其他方案要大，但 MI 最大的优势在于它的计算效率。如果我们选择 $q - k$ 很小，那么我们可以使用 k 的非零元素形成循环乘法群的性质将乘法表存储起来（Look-Up Table LUT 加速）。这使得其加密比RSA等必须处理大整数的方案要快得多。这个技术细节也可以用在解密过程中，包括 $\tilde F^{-1}$ 计算。事实上，MI最初引起了很多人的兴奋，正是在承诺相同的安全级别的情况下， MI 的实际实现比RSA快得多。

 

Linearization Equations Attack

线性化方程的攻击方法。

Definition Let $\mathcal{G}=\left\{g_1, \ldots, g_m\right\}$ be any set of $m$ polynomials in $k\left[x_1, \ldots, x_n\right]$. A linearization equation for $\mathcal{G}$ is any polynomial in $k\left[x_1, \ldots, x_n, y_1, \ldots, y_m\right]$ of the form

$$\sum_{i=1}^n \sum_{j=1}^m a_{i j} x_i y_j+\sum_{i=1}^n b_i x_i+\sum_{j=1}^m c_j y_j+d$$

such that we obtain the the zero function in $k\left[x_1, \ldots, x_n\right]$ upon substituting in $g_j$ for $y_j$, for $j=1, \ldots, n$. Equivalently, a linearization equation is any equation in $k\left[x_1, \ldots, x_n\right]$ of the form

$$\sum_{i=1}^n \sum_{j=1}^m a_{i j} x_i g_j\left(x_1, \ldots, x_n\right)+\sum_{i=1}^n b_i x_i+\sum_{j=1}^m c_j g_j\left(x_1, \ldots, x_n\right)+d=0$$

which holds for all $\left(x_1^{\prime}, \ldots, x_n^{\prime}\right) \in k^n$.

此处只简单阐述线性化攻击的思想（Chosen-Plaintext Attack，因为公钥是公开的，我们可以选取任意我们想要的密文密文对），首选是获取 $a_{i j}, b_i, c_j, d \in k$ 这些系数，这里阐述 CPA 的思想

• 第一步，构建线性化方程：

  $$g : \sum_{i=1}^n \sum_{j=1}^m a_{i j} x_i y_j+\sum_{i=1}^n b_i x_i+\sum_{j=1}^m c_j y_j+d = 0$$

• 第二步，构建已知明文密文对 $\left(x_1^{\prime}, \ldots, x_n^{\prime}\right), \left(y_1^{\prime}, \ldots, y_n^{\prime}\right) \in k^n$ , 把单项式系数 $a_{i j}, b_i, c_j, d \in k$ 视为未知元，一共 $(n+1)^2$ 个未知元，因此我们需要计算 $(n+1)^2$ 个明密文对，时间复杂度为 $O(n^4)$. （注：这里复杂度应该指的是 k 上的乘法次数，但是可以制作 LUT，k 上的乘法复杂度忽略不计，另外可以用 NTT 加速多项式乘法）。

• 第三步 ： 解关于 $(n+1)^2$ 个变量的 $(n+1)^2$ 个线性方程，大概 $O\left(n^6\right)$ 的复杂度。

另外一种（建议使用这个，速度应该更快）获取 $a_{i j}, b_i, c_j, d \in k$ 这些系数的方法是直接带入公钥函数 $\bar{f}_1, \ldots, \bar{f}_n \in k\left[x_1, \ldots, x_n\right]$ ，然后上述多项式恒等于 0 ， 就可以最多获取 $\frac{(n+1)(n+2)(n+3)}{6}$ 个方程，这些方程的就完全够阶上述方程，文献中给出证明，会出现 $a_{i j}, b_i, c_j, d \in k$ 某些系数是自由变量的情况，就可以利用这些自由变量恢复出给定密文对应的明文或者大大减少穷举空间。

在获取了线性化方程之后，假设我们需要求解的密文是 $\left(y_1^{\prime}, \ldots, y_n^{\prime}\right)$ ，作为 $\left(y_1, \ldots, y_n \right)$ 代入线性化方程 g 中，此时会有部分自由变量，因为给定 $\vec{x},\vec{y}$ ，方程 g 恒等于0，因此自由变量的系数就一定为 0 ，由此可以得到明文 $\vec{x}$ 相关的线性方程组。会出现两种情况：

1. 直接由线性方程组解出 $\left(x_1^{\prime}, \ldots, x_n^{\prime}\right)$ ，成功恢复出明文
2. 方程的数量不足，但是 $\left(x_1^{\prime}, \ldots, x_n^{\prime}\right)$ 中自由变量已经足够少了

针对上述第二种情况，有两种方法：

1. 穷举空间足够少，直接穷举。
2. 把代入 $\left(x_1^{\prime}, \ldots, x_n^{\prime}\right)$ 的关系方程代回公钥 $\bar{f}_1, \ldots, \bar{f}_n \in k\left[x_1, \ldots, x_n\right]$ 的多项式中，等于密文，即可解。

该部分省略了大部分数学证明，有兴趣读者请参考原文献，另外强烈建议读者看文献中的 Toy Example，脉络清晰，易于理解。

 

Matsumoto-Imai Variants

此节讨论 Matsumoto-Imai 体制的相关变体，虽然 Matsumoto-Imai 已经被攻破了，但是其相关变体后续得到了广泛研究和应用。

为了提高 Matsumoto-Imai 密码系统的安全性，提出了两种方法。一种被称为 “Minus” 变体，旨在抵抗 Patarin 提出的线性化攻击。另一种被称为 “Plus” 变体，用于制作密码单射，从而使我们能够解密密文。在Matsumoto-
Imai 提出的所有实际使用的变体中，最成功的是 Minus 变体 $Sflash^{v2}$

 

The Minus Method for Digital Signature

Minus Method [ Shamir, 1993 ] 是 MQC 中一类从公钥加密算法转化为签名算法的一般化方法，它的核心思想就是从 MI 公钥中删除若干个个多项式。假设 $\bar{F}: k^n \longrightarrow k^l$ 是一个公钥体系，其中公钥为 $\bar{f}_1, \ldots, \bar{f}_l \in k\left[x_1, \ldots, x_n\right]$ （大部分情况下 $l=n$ ）。那么我们从中删除 r 个多项式，比如删去最后 r 个多项式，即 $\bar{F}^{-}: k^n \longrightarrow k^{l-r}$ ：

$$\bar{F}^{-}\left(x_1, \ldots, x_n\right)=\left(\bar{f}_1, \ldots, \bar{f}_{l-r}\right)$$

 

公钥 Public Key

• 有限域 $k$ 以及其加法、乘法代数结构。
• k 上的 $n-r$ 个多项式 ： $\bar{f}_1, \ldots, \bar{f}_{n-r} \in k\left[x_1, \ldots, x_n\right]$

 

私钥 Sceret Key

与原 MI 体系一致。

 

签名 The Signing Process

需要签名的消息或者其哈希编码为 $Y^{\prime-}=\left(y_1^{\prime}, \ldots, y_{n-r}^{\prime}\right)$, a vector in $k^{n-r}$. 签名者在 $k$ 上随机选取 $n-r$ 随机值 $y_{n-r+1}^{\prime}, \ldots, y_n^{\prime}$ , 附加到 $Y^{\prime-}$ 得到 $Y^{\prime}=\left(y_1^{\prime}, \ldots, y_n^{\prime}\right)$ in $k^n$，则根据 MI 的解密过程签名为：

$$X^{\prime}=\left(x_1^{\prime}, \ldots, x_n^{\prime}\right)=\bar{F}^{-1}\left(Y^{\prime}\right)$$

其中 $X^{\prime}$ 就是消息 $Y^{\prime-}$ 的签名

 

验签 The Verifying Process

任何收到原始消息 $Y^{\prime}-$ 和其对应签名 $X^{\prime}$ 的用户，首先获取到签名使用的公钥 $\bar{f}_1, \ldots, \bar{f}_{n-r} \in k\left[x_1, \ldots, x_n\right]$ ，然后验证下面等式

$$\left(\bar{f}_1\left(X^{\prime}\right), \ldots, \bar{f}_{l-r}\left(X^{\prime}\right)\right)=Y^{\prime} .$$

如果成立，则验签成功，否则验签失败。

 

Flash and Sflash

NESSIE 选取的最终签名方案就是 $Sflash^{v2}$ ，最初的 $Sflash^{v1}$ 被证明是有缺陷的，是因为它为了减少密钥大小选取了 $GF(2)$ 作为其有限域，因此 $Sflash^{v2}$ 选取了 $GF(2^7)$ 作为其有限域，即能抵抗相关攻击，其公钥大小为 15 KB，签名长度 259 比特。

 

具体参数 Specific Parameters

Sflash uses $k = GF(2^7)$ , $n=37$ and $r=11$ so that $\bar{F}^{-}: k^{37} \longrightarrow k^{26}$ is defined by

$$\bar{F}^{-}\left(x_1, \ldots, x_n\right)=\left(\bar{f}_1, \ldots, \bar{f}_{n-r}\right)$$

where $\bar{f}_1, \ldots, \bar{f}_{26} \in k\left[x_1, \ldots, x_{37}\right]$.

后续具体流程略，其基本签名方案和上面的 Minus 是一致的，但是加入了很多细节，感兴趣读者可以自行探索。

 

Hidden Field Equations

Hidden Field Equations （abbr. HFE）也可以认为是 MI 密码体制的变体。在使用 Minus 和 Plus 方法对Matsumoto-Imai 密码系统进行直接泛化之后，Patarin进一步推动了他的工作，寻找用其他可以使密码系统更安全的东西取代 F 映射的方法。最终，他提出了 隐藏域方程密码系统 (HFE) [Patarin, 1996b]。

HFE的设计依赖于一个参数d，该参数d决定了密码系统的效率。然而，如果 d 过于小就容易收到攻击 ：[Kipnis and Shamir, 1999] 、[Courtois, 2001]。 HFE 密码体制也可以通过 Minus 、 Plus 方法进行变体，得到对应的签名算法 $\mathrm{HFE}^{-}$ (HFE-Minus) or $\mathrm{HFE}^{ \pm}$(HFE-Plus-Minus)。但是 HFE 更多地关注是 $\mathrm{HFEv}$ 和 $\mathrm{HFEv}^{-}$ 变体。

Basic HFE

仍然是 Matsumoto-Imai 密码体系，笔者这里只叙述 HFE 中核心地改变，即映射 $\tilde{F}=X^{q^\theta+1}$ 改成了：

$$\tilde{F}(X)=\sum_{i=0}^{r_2-1} \sum_{j=0}^i a_{i j} X^{q^i+q^j}+\sum_{i=0}^{r_1-1} b_i X^{q^i}+c$$

其中 $a_{i j}, b_i, c \in K$ 随机选取， $r_1, r_2$ 的选取使得 $\tilde{F}$ 的次数小于 $d$，其公钥为：

$$\bar{F}=L_1 \circ F \circ L_2 = L_1 \circ \phi \circ \tilde{F} \circ \phi^{-1} \circ L_2$$

其中 $\tilde{F}$ 要求是秘密的，即保存为私钥。 除此之外，与 MI 密码体制差别在于解密函数的不同。

 

解密过程 Decryption

Given the ciphertext $\left(y_1^{\prime}, \ldots, y_n^{\prime}\right)$, decryption includes the following steps.

1. Compute $\left(\bar{y}_1, \ldots, \bar{y}_n\right)=L_1^{-1}\left(y_1^{\prime}, \ldots, y_n^{\prime}\right)$.

2. Let $\bar{Y}=\phi^{-1}\left(\bar{y}_1, \ldots, \bar{y}_n\right)$. Compute the set

   $$\mathcal{Z}=\{Z \in K \mid \tilde{F}(Z)=\bar{Y}\}$$

   To compute $\mathcal{Z}$ we will use a variant of the Berlekamp algorithm suitable for use over the field $K$. If $d=\operatorname{deg} \tilde{F}(X)$, then the complexity of this step will be $O\left(n d^2 \log d+d^3\right)$; or we can use an even more efficient method by first finding the gcd of this polynomial with $X^{q^n}-X$ [Geddes et al., 1992] with slightly lower complexity. From this we see that the degree of $\tilde{F}$ cannot be too large, since otherwise the decryption process is inefficient. Equivalently, we must not choose $r_1, r_2$ to be too large.

3. For each element $Z_i \in \mathcal{Z}$, compute

   $$\left(x_{i 1}, \ldots, x_{i n}\right)=L_2^{-1} \circ \phi\left(Z_i\right)$$

值得注意的是 $\tilde{F}$ 此时很可能不是一个双射或者说 1-1 映射，所以第三步可能得到多个 $Z$，此时就需要额外的信息来进行验证第三步得到的明文，比如提供额外哈希或者明文解码后全部是 ASCII 字符。