本文主要介绍 linear code 的相关编码理论基础。然后简单阐述 Code-based Challenges 上一系列用于后量子密码设计的 code-based 问题。本文并不涉及具体的密码学算法设计，旨在对编码理论中的线性编码进行一个简单的介绍。

 

线性编码基础

主要参考：

1. Ron Roth, Introduction to Coding Theory, Cambridge University Press, 2006,
2. A Survey on Code-based Cryptography : paper link.

读者应有线性代数、群环域、代数数论的数学基础。

 

线性编码 Linear Code

记 $\mathbb{F}_q = GF(q)$ 是阶为 $q$ 的伽罗瓦域，一个 $(n,M,d)$ 编码的空间 $\mathcal{C}$ ，其中 $M$ 是明文空间，$n$ 是码字个数，$d$ 是最短码字距离， 如果 $\mathcal{C}$ 是 $\mathbb{F}^n$ 的线性子空间，则 $\mathcal{C}$ 称为线性编码。 即对于任意 $\mathbf{c}_1, \mathbf{c}_2 \in \mathcal{C}$ 和任意 $a_1,a_2 \in \mathbb{F}$ 使得 $a_1 \mathbf{c}_1+a_2 \mathbf{c}_2 \in \mathcal{C}$ 。

注记 ：

1. 线性空间 $\mathcal{C}$ 更一般的记法是 $[n,k]$ ，表明编码长度（code length）为 $n$ ，线性子空间的维度是 $k$ 。
2. 线性编码 $[n,k]$ 的总空间是 $q^n$ , 可编码空间是 $q^k$ 。
3. 线性编码的码率 Code Rate ： 可编码的空间是 $|\mathcal{C}| = q^k$ ，因此码率是 $R = (log_q M)/n = k/n$ 。

 

Linear Code 生成矩阵

代数上定义的概念还比较抽象，实际上直接从生成矩阵看 Linear Code 是很直观的。线性编码 $[n,k]$ 的一个生成矩阵可以看作一个 $k \times n$ 的矩阵 $\mathbf{G} \in \mathbb{F}_q^k$，其 $k$ 个线性无关的行向量构成整个线性子空间的基 $\{\mathbf{b}_1, \mathbf{b}_2,\cdots, \mathbf{b}_k \}$ .

$$\mathcal{C} = \{a_1 \mathbf{b_1} + a_2 \mathbf{b}_2 + \cdots + a_k \mathbf{b_k} \ | \ a_i \in \mathbb{F}_q \} \\ \implies \mathcal{C} = \big\{ x \mathbf{G}\ |\ x \in \mathbb{F}_q^k \bigr\}$$

 

Linear Code 编解码

既然涉及到编码，就一定涉及到编解码的操作。编码需要构造映射 $\mathbb{F}^k \mapsto \mathcal{C}$ ，利用生成矩阵定义下面映射：

$$\mathbf{u} \mapsto \mathbf{u}G$$

矩阵 $G$ 满秩，即上面映射为双射。

解码过程：记码字为 $c = \mathbf{u}G \in F^{n}$ ，解码操作，可以任意选取 $G$ 线性无关的 $k$ 列，对应的码字为 $c^\prime$ ，得到可逆矩阵 $U$ ，计算 $c^\prime U^{-1}$ ，即可恢复出明文 $u$ 。注意到，实际上解码只需要 $k$ 列，其他的列向量是线性编码中的冗余，可用于纠错。

 

Linear Code 校验矩阵（Parity Check Matrix）

知道编码矩阵，不论是正向编码（矩阵乘法），和反向解码（解超定方程），都是简单的。校验矩阵是用于验证目标码字是否是正确的。令 $\mathcal{C}$ 是定义在 $\mathbb{F}_q$ 上 $[n,k]$ 的线性编码，其奇偶校验矩阵 $H \in \mathbb{F}^{r \times n}$ （$r = n - k$）满足：

$$\forall \mathbf{c} \in \mathbb{F}^n, \mathbf{c} \in \mathcal{C} \iff H \mathbf{c}^T = \mathbf{0}$$

也就是说编码的空间是校验矩阵 $H$ 的 kernel space（核空间）。对于任意的 $x \in \mathbb{F}_q^n$ ，我们称 $x \mathbf{H}^T$ 为 Syndrome 。

 

汉明度量 Hamming Metric

• 汉明度量（Hamming Metric）： 对于 $\mathbf{x} \in \mathbb{F}_q^n$ ，汉明度量为其非 0 元的个数，

  $$\mathrm{wt}_H(\mathrm{x})=\left|\left\{i \in\{1, \ldots, n\} \mid x_i \neq 0\right\}\right| \text {. }$$

• 汉明距离（Hamming Distance）：对于 $\mathbf{x}, \mathbf{y} \in \mathbb{F}_q^n$ ，汉明距离为，

  $$\mathrm{d}_H(\mathrm{x}, \mathrm{y})=\left|\left\{i \in\{1, \ldots, n\} \mid x_i \neq y_i\right\}\right| \text {. }$$

• 最短距离（Minimum Distance） ：编码 $\mathcal{C}$ 的最短汉明距离为，

  $$d_H(\mathcal{C})=\min \left\{d_H(\mathbf{x}, \mathbf{y}) \mid \mathbf{x}, \mathbf{y} \in \mathcal{C}, \mathbf{x} \neq \mathbf{y}\right\}$$

 

注记：

1. 对于线性编码 $\mathcal{C}$ ，其最短汉明距离为：

   $$d_H(\mathcal{C})=\min \left\{\mathrm{wt}_H(\mathbf{x}) \mid \mathbf{x} \in \mathcal{C}, \mathbf{x} \neq \mathbf{0}\right\} .$$

2. 向量 $x$ 距离编码空间 $\mathcal{C}$ 的最短距离记为 ：

   $$d_H(\mathbf{x}, \mathcal{C}) =\min \left\{\mathrm{d}_H(\mathbf{x}, \mathbf{y}) \mid \mathbf{y} \in \mathcal{C}\right\} .$$

3. Hamming sphere ：汉明球即所有汉明重量小于 $r$ 的向量集合，记为，

   $$B_H(r, n, q)=\left\{\mathrm{x} \in \mathbb{F}_q^n \mid \mathrm{wt}_H(\mathrm{x}) \leq r\right\}$$

   汉明球的集合大小为：

   $$\left|B_H(r, n, q)\right|=\sum_{i=0}^r\left(\begin{array}{c} n \\ i \end{array}\right)(q-1)^i .$$

 

实际上，在基于编码的密码学中，有常见的两种度量方式，其一是汉明度量，其二是秩度量（Rank-Metric），本文中只关注基于汉明度量的线性编码和相关性质，对 Rank-Metric 感兴趣的读者可以参考 A Survey on Code-Based Cryptography 。

 

线性编码的性质

定理 Singleton Bound

令正整数 $k \le n$ ，令 $\mathcal{C}$ 是一个定义在 $\mathbb{F}_q$ 上 $[n,k]$ 的线性编码，则其最短汉明距离的上界为：

$$d_H \le n - k + 1$$

证明思路：只需要证明 k 维的线性编码，删去 $d_H - 1$ 个位置就一定是单射。（证明汉明重量大于 $d_H$ 的汉明球集合的大小一定小于 k 维的线性子空间大小）

 

定义 Maximum Distance Separable (MDS)

达到 Singleton bound 的最短汉明距离上界的编码称为 MDS 编码。在实际使用中 MDS 编码具有非常好的性质，因为固定线性编码的参数 $[n,k]$ ，MDS 编码能够最大化纠错能力。

 

性质 1 ：最短汉明距离与校验矩阵

令 $\mathcal{C}$ 是一个定义在 $\mathbb{F}_q$ 上 $[n,k]$ 的线性编码， $\mathbf{H}$ 是其校验矩阵，则 $\mathcal{C}$ 的最短汉明距离为 $d_H$ 当且仅当 $\mathbf{H}$ 的任意 $d_H - 1$ 列是线性无关的，并且存在 $d_H$ 个列向量是线性相关的。

 

定义 Dual Code 对偶编码

令正整数 $k \le n$ ， $\mathcal{C}$ 是一个定义在 $\mathbb{F}_q$ 上 $[n,k]$ 的线性编码，其对偶编码 $\mathcal{C}^{\perp}$ 是一个定义在 $\mathbb{F}_q$ 上 $[n,n-k]$ 的线性编码，定义如下：

$$\mathcal{C}^{\perp}=\left\{\mathbf{x} \in \mathbb{F}_q^n \mid\langle\mathbf{x}, \mathbf{y}\rangle=\sum_{i=1}^n x_i y_i = \mathbf{0} \forall \mathbf{y} \in \mathcal{C}\right\} .$$

 

性质 2 ： 对偶编码

一个 MDS 编码的对偶编码仍然是 MDS 的。

 

定义 ：Systematic Form 矩阵

令 $\mathcal{C}$ 是一个定义在 $\mathbb{F}_q$ 上 $[n,k]$ 的线性编码，那么存在某个置换矩阵（Permutation Matrix）$\mathbf{P}$ ，和一个可逆矩阵 $\mathbf{U}$，使得生成矩阵变成系统形式（Systematic Form）：

$$\mathbf{U G P}=\left(\begin{array}{ll} \operatorname{Id}_k & \mathbf{A} \end{array}\right)$$

其中 $Id_k$ 是 $k \times k$ 的单位矩阵， 并且 $\mathbf{A} \in \mathbb{F}_q^{k \times(n-k)}$ 。

对应地，也能将校验矩阵也转换成系统形式，存在某个置换矩阵（Permutation Matrix）$\mathbf{P}^\prime$ ，和一个可逆矩阵 $\mathbf{U}^\prime$，使得：

$$\mathbf{U}^{\prime} \mathbf{H} \mathbf{P}^{\prime}=\left(\begin{array}{ll} \mathbf{B} & \mathrm{Id}_{n-k} \end{array}\right)$$

 

Remarks

置换矩阵顾名思义，它的作用就是重新排列矩阵的列顺序或者行顺序，形式上等价于一个单位阵进行任意置换后的矩阵。

 

定理 ： Gilbert-Varshamov bound

定义 1 令 $q$ 是一个素数的幂， $k \le n$ ，记 $V_H(r, n, q)=\left|B_H(r, n, q)\right|$ 为汉明球的容量， $d_H$ 是正整数使得：

$$V_H\left(d_H-2, n-1, q\right)<q^{n-k} .$$

那么存在一个定义在 $\mathbb{F}_q$ 上 $[n,k]$ 的线性编码，它的最小汉明距离至少是 $d_H$ 。

 

更为广泛的 Gilbert-Varshamov bound 定义是从编码的最大维数（$k$ 值）来阐述的，记 $A L(n, d, q)$ 为 $\mathbb{F}_q^n$ 上最短汉明距离为 d 的编码的最大维数（$k$ 值）。

定义 2 令 $q$ 是一个素数的幂， $n,d$ 是正整数，则：

$$A L(n, d, q) \geq \frac{q^n}{V_H(d-1, n, q)} .$$

事实证明，随机生成的 code 以高概率到达渐进的 Gilbert-Varshamov bound 。

 

常见线性编码

某些特定方式生成的线性编码具有良好的性质，本节简单介绍一些在密码学、编解码方向常用的线性编码。

 

Generalized Reed-Solomon Code

定义 ： Generalized Reed-Solomon Code

正整数 $k \le n \le q$ ，令 $\alpha \in \mathbb{F}_q^n$ 是不同元素的 n-元组，即 $\alpha=\left(\alpha_1, \ldots, \alpha_n\right)$ ，其中 $\alpha_i \neq \alpha_j, \forall i \neq j \in\{1, \ldots, n\}$ ；令 $\beta \in \mathbb{F}_q^n$ 是非零的 n-元组，即 $\beta=\left(\beta_1, \ldots, \beta_n\right)$, 其中 $\beta_i \neq 0 , i \in\{1, \ldots, n\}$，广义的里德-所罗门编码（Generalized Reed-Solomon Code），码字长度为 $n$ ，线性子空间维数为 $k$ ，记为 $\operatorname{GRS}_{n, k}(\alpha, \beta)$ ，其生成矩阵定义如下：

$$\operatorname{GRS}_{n, k}(\alpha, \beta)=\left\{\left(\beta_1 f\left(\alpha_1\right), \ldots, \beta_n f\left(\alpha_n\right)\right) \mid f \in \mathbb{F}_q[x], \operatorname{deg}(f)<k\right\} .$$

在 $\beta=(1, \ldots, 1)$ 时，我们称其为 Reed-Solomon (RS) 编码，记为 $\operatorname{RS}_{n, k}(\alpha)$ 。

 

Remarks

GRS 编码的生成矩阵可以解释为类似于 Vandermonde 矩阵乘以对角矩阵，其中每一行对应多项式的不同次数的项（从 0 到 $k-1$），每列对应不同的评估点 $a_i$，乘以权重向量中相应的 $\beta_i$。

例 范德蒙矩阵就是最常见的 RS 编码，取 $f(x) = \sum_{i=0}^{k-1} x^i$

$$\left(\begin{array}{ccc} 1 & \cdots & 1 \\ \alpha_1 & \cdots & \alpha_n \\ \vdots & & \vdots \\ \alpha_1^{k-1} & \cdots & \alpha_n^{k-1} \end{array}\right)$$

性质 1 ：GRS 编码都是 MDS 编码，即 GRS 的最小汉明距离达到最大上界 Singleton Bound。

$$d_H\left(\operatorname{GRS}_{n, k}(\alpha, \beta)\right)=n-k+1 .$$

性质 2 ：GRS 编码的对偶编码都是 GRS 编码。

性质 3 ：GRS 的对偶编码满足 ：

$$\operatorname{GRS}_{n, k}(\alpha, \beta)^{\perp}=G R S_{n, n-k}(\alpha, \gamma),$$

其中：

$$\gamma_i=\beta_i^{-1} \prod_{\substack{j=1 \\ j \neq i}}^n\left(\alpha_i-\alpha_j\right)^{-1} .$$

 

q-ary Goppa Code

补充定义 ： $m$ 是正整数，$n = q^m$ ，定义有限域 $\mathbb{F}_q^m$ ，令 $G \in \mathbb{F}_q^m[x]$ ，定义多项式商环：

$$S_m=\mathbb{F}_{q^m[x]} /\langle G\rangle .$$

引理 ：令 $\alpha \in \mathbb{F}_q$ 使得 $G(\alpha) \neq 0$ ，那么 $(x-\alpha)$ 在 $S_m$ 内是可逆的，其逆为 ：

$$(x-\alpha)^{-1}=-\frac{1}{G(\alpha)} \frac{G(x)-G(\alpha)}{x-\alpha}$$

定义 ： Classical Goppa Code

令 $\alpha=\left(\alpha_1, \ldots, \alpha_n\right) \in \mathbb{F}_{q^m}^n$ ，使得 $\alpha_i \neq \alpha_j \forall i\ne j \in\{1, \ldots, n\}$ ，并且 $G\left(\alpha_i\right) \neq 0$ for all $i \in\{1, \ldots, n\}$ ，则 Classical q-ary Goppa 编码定义为：

$$\Gamma(\alpha, G)=\left\{a \in \mathbb{F}_q^n \mid \sum_{i=1}^n \frac{a_i}{x-\alpha_i}=0 \text { in } S_m\right\} .$$

性质 1 ：Goppa 编码 $\Gamma(\alpha, G)$ 的最小汉明距离满足 $d_H(\Gamma(\alpha, G)) \geq \operatorname{deg}(G)+1$ ，线性子空间维数满足 $k \geq n-m \operatorname{deg}(G)$ 。

 

Goppa Code 校验矩阵

令 $\beta=$ $\left(G\left(\alpha_1\right)^{-1}, \ldots, G\left(\alpha_n\right)^{-1}\right)$ ，$\Gamma(\alpha, G)$ 的校验矩阵由下面带权值的范德蒙矩阵给出：

$$\mathbf{H}=\left(\begin{array}{ccc} \beta_1 & \cdots & \beta_n \\ \beta_1 \alpha_1 & \cdots & \beta_n \alpha_n \\ \vdots & & \vdots \\ \beta_1 \alpha_1^{r-1} & \cdots & \beta_n \alpha_n^{r-1} \end{array}\right)$$

注意到 $\mathbf{H} \in \mathbb{F}_{q^m}^{(n-k) \times n}$ ，编码 $\Gamma(\alpha, G)$ 是矩阵 $\mathbf{H}$ 的 $\mathbb{F}_{q^{-}}$kernel 。实际上，以 $\mathbf{H}$ 作为生成矩阵，可以构成一个 GRS 编码，由此可见 GRS 编码和 q-ary Goppa 编码之间的联系。

 

Cyclic Code

如果任何码字的循环移位也是一个码字，我们称其为循环码。循环编码 $\mathcal{C}$ 能够只通过一个向量 $c$ （和它的循环移位）来表示。令 $c = (c_1,\cdots,c_n) \in \mathbb{F}_q^n$ ，定义 $\sigma$ 为循环移位函数，即

$$\sigma(c_1,\cdots,c_n) = \sigma(c_n,c_1,\cdots,c_{n-1})$$

定义 ：Cyclic Code （循环编码）

正整数 $k \le n$ ， $\mathcal{C}$ 是一个定义在 $\mathbb{F}_q$ 上 $[n,k]$ 的线性编码， 我们称 $\mathcal{C}$ 是循环码，即满足 $\sigma(\mathcal{C}) = \mathcal{C}$ 。

 

注记

1. 令正整数 $k \le n \le q - 1$ ，$\alpha \in \mathbb{F}_q^n$ 为元素互异的向量，则 $\operatorname{RS}_{n, k}(\alpha)$ 是一个循环编码。
2. 定义在 $\mathbb{F}_q$ 上长度为 $n$ 的循环编码 $\mathcal{C}$ 是多项式商环 $\mathbb{F}_q [x] /(x^n -1)$ 上的理想（ideals）。因此循环编码 $\mathcal{C}$ 存在生成多项式。我们做如下定义，循环码 $\mathcal{C}$ 的生成多项式是其在 $\mathbb{F}_q[x]/(x^n − 1)$ 中最小次数理想对应的首一多项式。

 

性质 ： 循环码的生成多项式

令 $\mathcal{C}$ 是 $\mathbb{F}_q$ 上长度为 $n$ 的循环编码，其生成多项式为 $g(x) = \sum_{i=0}^r g_i x^i$ ，次数为 $r$ ，则满足：

1. 生成多项式 $g(x) | x^n -1$ （由理想的性质立得）

2. 循环码 $\mathcal{C}$ 的维数为 $k = n - r$ 。

3. 生成矩阵 $G \in \mathbb{F}_q^{(n-r) \times n}$ 可以表示如下（该形式的矩阵也被称为循环矩阵）：

   $$G=\left(\begin{array}{lllll} g_0 & \cdots & g_r & & \\ & \ddots & & \ddots & \\ & & g_0 & \cdots & g_r \end{array}\right)$$

4. 循环码 $\mathcal{C}$ 的对偶编码的生成多项式 $h(x)$ 满足 ：$g(x)h(x) = x^n -1$ ，即 $\langle g(x)\rangle^{\perp}=\langle h(x)\rangle$。

 

除了循环编码之外，密码学中常见的编码是准循环编码（Quasi-Cyclic Code），简记为 QC 编码。类似地定义 $\ell$ 循环移位，令 $c = (c_1,\cdots,c_n) \in \mathbb{F}_q^n$ ，记 $\sigma_{\ell}(x)$ 如下：

$$\sigma_{\ell}(c_1,\cdots,c_n) = \sigma(c_{1+\ell},\cdots,c_{n+\ell})$$

上述下标均在模 $n$ 的意义下进行计算。

 

定义：Quasi-Cyclic Code（准循环编码）

令正整数 $k \le n$ ， $\mathcal{C}$ 是一个定义在 $\mathbb{F}_q$ 上 $[n,k]$ 的线性编码，$\mathcal{C}$ 是准循环的，即存在 $\ell \in \{1,\cdots, n\}$， 使得 $\sigma_{\ell}(\mathcal{C}) = \mathcal{C}$ 。

 

编码理论的 NP 困难问题

前面提到过，线性编码的编码、解码问题是简单的。但是我们注意到编码领域一个重要研究方向就是纠错，如果编码后的 codeword 在不可靠信道上传输部分比特出现了错误，线性编码的纠错能力如何？准确而言，一个 $[n,k]$ 的二元线性编码 $\mathcal{C}$ 最大能够纠错多少个比特数？纠错解码的时间复杂度如何？

第一个问题的答案将在本节给出，第二个问题的答案是纠错算法是 NP 困难的，目前最好的算法是 Information Set Decoding （ISD）类算法及其变体，拥有指数级别的复杂度，也因此用于设计一系列后量子密码体制。

 

线性编码的纠错能力

这里我们重新审视线性编码的本质，记 $[n,k]$ 的二元线性编码 $\mathcal{C}$ 的生成矩阵为 $\mathbf{G} \in \mathbb{F}_q^k$，其 $k$ 个线性无关的行向量构成整个线性子空间的基 $\{\mathbf{b}_1, \mathbf{b}_2,\cdots, \mathbf{b}_k \}$ 。记明文 $\mathbf{m} = (a_1,\cdots,a_k)$ ，其对应的码字满足：

$$c = (c_1,\cdots,c_n) = a_1 \mathbf{b_1} + a_2 \mathbf{b}_2 + \cdots + a_k \mathbf{b_k} = \mathbf{mG}$$

本质上就是我们有 $k$ 个变量 ，但是我们构建了 $n \ge k$ 组线性方程：

$$\textsf{(n,k) Overdetermined Equations }\left\{ \begin{array}{lr} b_{11} a_1 + b_{21} a_{2} + \cdots + b_{k1} a_k = c_1 \\ b_{12} a_1 + b_{22} a_{2} + \cdots + b_{k2} a_k = c_2 \\ \cdots \\ b_{1n} a_1 + b_{2n} a_{2} + \cdots + b_{kn} a_k = c_n \end{array} \right.$$

上述是一个超定方程组，存在 $n - k$ 组冗余方程组。假设错误向量为 $\mathbf{e}$ ，汉明重量为 $\mathbf{wt(e)} = w$ ，则一个含有错误向量的码字为 $\mathbf{c}^\prime = \mathbf{mG + e}$ ，本质上即 $n$ 组 $k$ 变量的超定线性方程组中，有 $w$ 组方程是错的，如何恢复出原始的 $\mathbf{m}$ 。从解方程的角度容易得到纠错的最多比特数不超过 $n -k$ 。但是实际上线性编码的纠错能力小于 $n - k$ ，其一是，我们并不确定出错的比特位数，即使知道，也无法确定正确的明文，因为不能假设原始消息存在某种可验证的格式（比如 ASCII 码）；其二，码字长度 $n$ 比较大时，随着纠错比特数增大，纠错的时间复杂度是指数级别的（NP 困难）。

实际计算中，只要满足错误向量的汉明重量比较短时，认为此时解出的码字时正确的，一般我们认为最大纠错的比特数为 Gilbert-Varshamov Distance，记为 $d_{\rm GV}(n,k)$ ，指的是最小的整数 $d$ 使得 ：

$$\sum_{j=0}^{d-1} \binom{n}{j} \ge 2^{n-k}.$$

这个界有一个直观的解释，也就是说找一个上界 $d_{\rm GV}(n,k)$ ，使得我们搜索完整个所有可能的错误方程出现的位置 $\sum_{j=0}^{d-1} \binom{n}{j}$ 恰好覆盖整个冗余方程组的空间 $2^{n-k}$ ，在小于这个 $d_{\rm GV}(n,k)$ 时，对于随机编码，纠错大概率能够得到唯一解，一旦大于 $d_{\rm GV}(n,k)$ ，此时可能存在两个或者多个汉明权重相同的错误向量，解密得到两个不同消息，此时我们是无法区分正确消息的。（在后续 SDP 中的解释更为直观）

下面我们正式定义编码领域两个重要问题（本质上是同一个问题）

• Decoding Problem ：给定整数 $n,k,w$ , 使得 $k \le n$ 并且 $w\le n$ ， 给定一个生成矩阵 （generator matrix） ${\rm \bf G} \in \mathbb{F}_2^{ k\times n}$，以及一个目标向量（编码后）${\rm \bf y} \in \mathbb{F}_2^{n}$ ，上述问题的一个解是找到一个向量 ${\rm \bf e} \in \mathbb{F}_2^n$ 使得其汉明重量 $\le w$ ，并且满足存在某个 $\mathbf{m} \in \mathbb{F}_q^k$ 使得 ${\rm m \bf G + e} = {\rm \bf y }$ 。
• Syndrome Decoding Problem ：给定整数 $n,k,w$ , 使得 $k \le n$ 并且 $w\le n$ ， 一个 $\mathrm{SD}(n,k,w)$ 问题实例即，给定一个奇偶校验矩阵 （parity-check matrix） ${\rm \bf H} \in \mathbb{F}_2^{(n-k) \times n}$，以及一个目标向量（编码后）${\rm \bf s} \in \mathbb{F}_2^{n-k}$ （称为 syndrome），上述问题的一个解是找到一个向量 ${\rm \bf e} \in \mathbb{F}_2^n$ 使得其汉明重量 $\le w$ ，并且满足 ${\rm \bf He^{\top}} = {\rm \bf s^{\top}}$ .

前一个解码纠错问题实际可以转换成 SDP，即：

$$\mathbf{y}=\mathbf{m G}+\mathbf{e} \\ \implies y \mathbf{H}^T = (m \mathbf{G})\mathbf{H}^T + e\mathbf{H}^T \\ \implies \underbrace{y \mathbf{H}^T}_{\mathbf{s}} = e\mathbf{H}^T \\ \implies {\rm \bf He^{T}} = {\rm \bf s^{T}}$$

我们在 SDP 问题中考虑Gilbert-Varshamov Distance 的值 $d_{\rm GV}(n,k)$ ，${\rm \bf s} \in \mathbb{F}_2^{n-k}$ ，可能的值为 $2^{n-k}$ 个， 搜索完所有可能的错误方程出现的位置 $\sum_{j=0}^{d-1} \binom{n}{j}$ ， 也就有 $\sum_{j=0}^{d-1} \binom{n}{j}$ 个可能的 Syndrome 值，如果这个值比整个 Syndrome 可能的的空间 $2^{n-k}$ 小，那么给定一个 Syndrome 值，得到的错误向量 $\mathbf{e}$ 大概率是唯一的。否则当 $w \ge d_{\rm GV}(n,k)$ ，由抽屉原理，对于某个 Syndrome 值，可能存在两个错误向量 $\mathbf{e_1,e_2}$ 同时满足 ${\rm \bf He^{T}} = {\rm \bf s^{T}}$ 。

 

Decoding Challenge

本节简单介绍 Code-based Challenges 上的三个困难问题，这些问题是许多后量子密码体制的底层数学困难问题。

 

Syndrome Decoding Problem

定义：给定整数 $n,k,w$ , 使得 $k \le n$ 并且 $w\le n$ ， 一个 $\mathrm{SD}(n,k,w)$ 问题实例即，给定一个奇偶校验矩阵 （parity-check matrix） ${\rm \bf H} \in \mathbb{F}_2^{(n-k) \times n}$，以及一个目标向量（编码后）${\rm \bf s} \in \mathbb{F}_2^{n-k}$ （称为 syndrome），上述问题的一个解是找到一个向量 ${\rm \bf e} \in \mathbb{F}_2^n$ 使得其汉明重量 $\le w$ ，并且满足 ${\rm \bf He^{\top}} = {\rm \bf s^{\top}}$ .

注记：

1. $\mathrm{SD}(n,k,w)$ 问题其实就是给了一个 $\mathbb{F}_2$ 上的欠定线性方程组，$n$ 个变量 ， 方程个数比变量个数少 $k$ 个，因此解空间大小为 $2^k$，我们的目标就是在 $2^k$ 的空间中寻找汉明重量不大于 $w$ 的目标解。
2. Syndrome Decoding Problem 的在线挑战以及现有记录：https://decodingchallenge.org/syndrome

3. 上述挑战的码率（Code-Rate）取为 $R = 0.5$ ，即 $n = 2k$ ，一般而言可快速求解的汉明重量下界是 Gilbert-Varshamov bound ，上述挑战选取的值稍大（保证对于任意 ${\rm \bf s} \in \mathbb{F}_2^{n-k}$ 解的存在性），为 $w = \lceil 1.05 \, d_{\rm GV}\rceil$ 。

    

Low-weight Codeword Problem

定义：给定整数 $n,k,w$ , 使得 $k \le n$ 并且 $w\le n$ ， 一个 $\mathrm{LWC}(n,k,w)$ 问题实例即，给定一个满秩奇偶校验矩阵 （parity-check matrix） ${\rm \bf H} \in \mathbb{F}_2^{(n-k) \times n}$，上述问题的一个解是找到一个非零向量 ${\rm \bf c} \in \mathbb{F}_2^n$ 使得其汉明重量 $\le w$ ，并且满足 ${\rm \bf Hc^{\top}} = {\rm \bf 0 }$ .

注记：

1. 该问题可以视为特殊 syndrome $\bf{0}$ 对应的 $\mathrm{SD}(n,k,w)$ 问题实例。
2. Low-weight Codeword Problem 的在线挑战以及现有记录 https://decodingchallenge.org/low-weight 。
3. 上述挑战的码率（Code-Rate）取为 $R = 0.5$ ，即 $n = 2k$ ，固定 $n = 1280$ , 此时根据 Gilbert-Varshamov bound ，存在一个汉明重量为 144 的目标解。
4. 解法 ： 使用 BJMM algorithm 渐进需要 $2^{0.0999852\, n}$ 的复杂度，对于上述参数即是 $2^{128}$ .

 

Large Weight Syndrome Decoding Problem

定义：给定整数 $n,k,w$ , 使得 $k \le n$ 并且 $w\le n$ ， 一个 $\mathrm{LW3SD}(n,k,w)$ 问题实例即，给定一个奇偶校验矩阵 （parity-check matrix） ${\rm \bf H} \in \mathbb{F}_3^{(n-k) \times n}$，以及一个目标向量（编码后）${\rm \bf s} \in \mathbb{F}_3^{n-k}$ （称为 syndrome），上述问题的一个解是找到一个向量 ${\rm \bf e} \in \mathbb{F}_3^n$ 使得其汉明重量 $\ge w$ ，并且满足 ${\rm \bf He^{\top}} = {\rm \bf s^{\top}}$ .

注记：

1. 类似 Syndrome Decoding Problem ，环改为 $\mathbb{F}_3$ ，目标改为寻找的是大于某个汉明重量的解。
2. Large Weight Syndrome Decoding Problem 的在线挑战以及现有记录 https://decodingchallenge.org/large-weight .
3. 上述挑战的码率 $R = \log_3(2) \simeq 0.36907$ ，则 $k = \lfloor R n \rfloor$ ，此时对于高汉明重量的 Gilbert-Varshamov bound 恰好是 $n$ ，这里我们取略小于 Gilbert-Varshamov bound 的目标汉明重量，即 $w = \lfloor 0.99 \, d_{\rm GV}^{+}\rfloor = \lfloor 0.99 \, n \rfloor$ 。