Introduction to Information Set Decoding

2024-01-05

字数统计: 4.9k字 | 阅读时长≈ 21分

Information Set Decoding （ISD）类算法是编码密码学中最重要的基本算法之一，是目前 Syndrome Decoding 问题的最优时间-空间复杂度权衡解法。本文梳理 ISD 算法基本原理，介绍基于 ISD 算法的各种优化。

Information Set Decoding

ISD 算法最早由 Prange 在 1962 年提出，后续基于 Prange 的框架，ISD 算法进行了各种优化，但是核心框架基本没有改变，时间空间上的复杂度优化并不大。并且基于量子的 ISD 算法只能应用于 Prange 的原始 ISD 算法，因此 Prange 的朴素 ISD 算法至今仍有重大意义。

Remarks

一些注记定义：

对于矩阵 $G \in \mathbb{F}^{k \times n}$ ， $I$ 为下标集合 $\{1,2,\cdots,n\}$ 的子集， $G_{I}$ 表示取矩阵 $G$ 对应下标的列构成的新矩阵。集合 $I^C$ 表示 $I$ 的补集。
若无特殊说明，我们均考虑在二元域 $\mathbb{F}_2$ 上的线性编码。
符号 $\mathbf{wt (\cdot)}$ 表示向量的汉明重量。
简记 Syndrome Decoding Problem 为 $\mathcal{SDP(n,k,t)}$ ，表示在 $[n,k]$ 的线性编码上求解汉明重量不大于 $t$ 的 SDP 问题，即给定校验矩阵 ${\rm \bf H} \in \mathbb{F}_2^{(n-k) \times n}$ ，以及一个目标向量 ${\rm \bf s} \in \mathbb{F}_2^{n-k}$ ，找到一个向量 ${\rm \bf e} \in \mathbb{F}_2^n$ 使得其汉明重量 $\le t$ ，并且满足 ${\rm \bf He^{\top}} = {\rm \bf s^{\top}}$ .
简记 $\left(\begin{array}{c} n \\ m \end{array}\right)$ 为组合数，也即二项式系数（Binomial Coefficient）。

信息集 Information Set

记 $[n,k]$ 的二元线性编码 $\mathcal{C}$ 的生成矩阵为 $\mathbf{G} \in \mathbb{F}_2^{k \times n}$ ，其 $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$ 维的密文信息即可解码：选取子集 $I \subset \{1,2,\cdots,n\}$ ，大小为 $|I| = k$ ，使得 $G_{I}$ 为可逆矩阵，则可解码得到原消息。因此，满足上述性质的大小为 $k$ 的集合 $I$ 被称为信息集，因为它包含编码的所有信息。

信息集的概念一般在含错误向量的场景下使用，考虑两种场景下的信息集：

生成矩阵场景：含错码字 $\mathbf {c = mG + e, wt(e) = t}$ ，选取大小为 $k$ 的下标子集 $I \subset \{1,2,\cdots,n\}$ 为信息集，如果有效错误集（对应维度的 $e_i$ 为 1）均不落入信息集 $I$ 中，则我们可以根据 $\mathbf{c_I \cdot G}_I^{-1}$ 直接解码得到消息 $m$ 。
校验矩阵场景：给定一个 $\mathcal{SDP(n,k,t)}$ ，校验矩阵 ${\rm \bf H} \in \mathbb{F}_2^{(n-k) \times n}$ ，目标向量 ${\rm \bf s} \in \mathbb{F}_2^{n-k}$ ，此时我们想要找到 ${\rm \bf e} \in \mathbb{F}_2^n$ 使得， $\mathbf{wt(e)} \le t$ ，并且满足 ${\rm \bf He^{\top}} = {\rm \bf s^{\top}}$ 。选取大小为 $n-k$ 的下标子集 $I \subset \{1,2,\cdots,n\}$ 为信息集，如果有效错误集（对应维度的 $e_i$ 为 1）全部落入信息集 $I$ 中，则可以根据 $\mathbf{s \cdot H}_I^{-1}$ 直接解码得到向量 $\mathbf{e}$ 的有效部分，然后根据信息集位置重构恢复 $\mathbf{e}$ 。

多数情况下，我们都只考虑在校验矩阵场景下的信息集解码算法。在一般论文中，都会直接把 $\mathcal{SDP}$ 的信息集定义为上述信息集的补集 $J = I^C$ ，这两者实际是等价的。后续校验矩阵场景下的 ISD 算法中，统一称大小为 $k$ 的下标子集 $I \subset \{1,2,\cdots,n\}$ 为信息集，只要其满足矩阵 $H_{I^C}$ 是可逆的。

值得注意的是，对于校验矩阵 ${\rm \bf H} \in \mathbb{F}_2^{(n-k)\times n}$ ，存在一个置换矩阵（Permutation Matrix） $\mathbf{P} \in \mathbb{F}_2^{n \times n}$ ，和一个可逆矩阵 $\mathbf{U} \in \mathbb{F}_2^{(n-k) \times (n-k)}$ 使得：

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

实际上每个信息集 $I$ 对应的 $\mathbf{H}_{I^C}^{-1}$ ，也就是使得校验矩阵系统化的矩阵 $U = \mathbf{H}_{I^C}^{-1}$ 。另外为了简洁起见，绝大多数情况下我们把置换矩阵的作用忽略。

Plain ISD

最早由 Prange 提出的 ISD 算法，又被称为朴素 ISD 算法，是最简单的的 ISD 算法。

Plain ISD 算法

输入：校验矩阵 ${\rm \bf H} \in \mathbb{F}_2^{(n-k) \times n}$ ，目标向量 ${\rm \bf s} \in \mathbb{F}_2^{n-k}$ ，目标汉明重量 $t$

输出： ${\rm \bf e} \in \mathbb{F}_2^n$ 满足 $\mathbf{wt(e)} \le t$ ，并且 ${\rm \bf He^{\top}} = {\rm \bf s^{\top}}$ 。

随机选取一个大小为 $k$ 的信息集合 $I \subset \{1,2,\cdots,n\}$ ，其补集记为 $J = I^C$
计算系统化矩阵 $U$ 使得，
$(\mathbf{U H})_I=\mathbf{A} \text { and }(\mathbf{U H})_J=\mathrm{Id}_{n-k},$
其中 $\rm A \in \mathbb{F}_2^{(n-k)\times k}$
计算 $\mathbf{s^\prime = s U^T}$
如果 $\mathbf{wt(s^\prime)} = t$ ，则直接返回 $\rm \bf e$ ，使得 $\rm \bf e_{I} = 0_k, e_J = s^\prime$ 。
否则直接返回第一步，选取一个新的信息集。

上面算法非常容易理解，如果像我们假设的一样，有效错误集（对应维度的 $e_i$ 为 1）全部落入信息集的补集 $J$ 中，则：

$\mathbf{e} \mathbf{H}^{\top} \mathbf{U}^{\top}=\left(\begin{array}{ll} \mathbf{0}_k & \mathbf{e}_J \end{array}\right)\left(\begin{array}{c} \mathbf{A}^{\top} \\ \operatorname{Id}_{n-k} \end{array}\right)=\mathbf{sU}^{\top}$

简单而言，大小为 $n-k$ 的补集 $J$ 选取出的校验矩阵对应的列的逆，恰好能够将错误向量所在的部分全部还原，并且前面 $k$ 个维度完全不会影响最后的结果，能够直接从 $\rm \bf s^\prime = \mathbf{sU}^{\top} = e_J$ 检查汉明重量信息。由算法流程可见，所有错误全部落入信息集的补集 $J$ 中是概率性的，ISD 算法的迭代次数（时间复杂度）取决于这个概率。

时间复杂度分析

考虑 ISD 算法的单轮复杂度，主要包括单次矩阵求逆得到 $U$ ，以及矩阵乘法 $\rm \bf U \cdot (H,s)$ ，因此单轮时间复杂度为（论文 ^ISD中称系统化的时间复杂度于矩阵乘法相当，该估算最终只影响一个常数，本文考虑精确的时间复杂度分析）

$R = ((n-k)^{3}+(n-k)^2(n+1))$

任意选取一个信息集使得 $t$ 个错误全部落入信息集的补集 $J$ 中的概率为：

$p = \frac{\left(\begin{array}{c} n-k \\ w \end{array}\right)}{\left(\begin{array}{c} n \\ w \end{array}\right)}$

因此期望的时间复杂度预计为：

$T(n,k,w)_{\rm \bf pisd} = \frac{1}{p} R = {\left(\begin{array}{c} n \\ w \end{array}\right)}{\left(\begin{array}{c} n -k \\ w \end{array}\right)}^{-1} (n-k)^2(2n+1-k)$

考虑单纯的穷举算法的时间复杂度：

$T(n,k,w)_{\rm \bf bf} = \left(\begin{array}{c} n \\ w \end{array}\right)$

对于大部分困难参数而言，朴素的 ISD 算法都有比较好的时间性能上的提升。考虑 decoding challenge 上低汉明重量码字解码问题给出的具体参数 $n = 1280, k = 640, t = 144$ ，时间复杂度如下（简单估计，不考虑优化，会有小的多项式系数误差）：

$T(n,k,w)_{\rm \bf pisd} = O(2^{187}) \\ T(n,k,w)_{\rm \bf bf} = O(2^{645}) \\$

目前 SDP 最优的求解算法之一是 $\rm \bf BJMM$ ，其渐进时间复杂度为 $T(n,n/2,d_{GV})_{\rm \bf BJMM} = O(2^{0.0999852\, n})$ （不考虑空间的限制），目前绝大多数基于编码的 PQC 密码体制，其安全强度对标这个渐进时间复杂度。

Improved ISD

ISD 算法提出之后，提出了许多优化算法。核心的优化思路是分析有效错误集（对应维度的 $e_i$ 为 1）在信息集中的分布。通过增加单轮求解的时间复杂度，来减少 ISD 主循环中需要迭代的次数。给定一个 $\mathcal{SDP(n,k,t)}$ ，主要有两个方向的优化：

方向一（Lee-Brickell）：假设大小为 $k$ 信息集中有 $v$ 个错误，信息集的补集中存在 $t -v$ 个错误。
方向二（Dumer）：假设在 $k+l$ 个比特位置（包含一个信息集）上有 $v$ 个错误，在另外 $n-k-l$ 个比特位置上有 $t-v$ 个错误。

Lee-Brickell 方向的优化，论文^{Code-Survey22}给出了一个各类 ISD 算法中错误向量中大小为 $t$ 的有效错误集在信息集中分布假设

图一：Lee-Brickell 方向优化

Dumer 方向的优化，论文^{Code-Survey22}给出了一个各类 ISD 算法中错误向量中大小为 $t$ 的有效错误集在 $k+l$ 个位置（包含一个信息集）中分布假设：

图二：Dumer 方向优化

Lee-Brickell Direction

由于本文篇幅有限，仅选取部分算法进行介绍性阐述。

Lee-Brickell ISD 算法

输入：校验矩阵 ${\rm \bf H} \in \mathbb{F}_2^{(n-k) \times n}$ ，目标向量 ${\rm \bf s} \in \mathbb{F}_2^{n-k}$ ，目标汉明重量 $t$ ，参数 $v < \mathcal{MIN}\{t,k\}$

输出： ${\rm \bf e} \in \mathbb{F}_2^n$ 满足 $\mathbf{wt(e)} \le w$ ，并且 ${\rm \bf He^{\top}} = {\rm \bf s^{\top}}$ 。

随机选取一个大小为 $k$ 的信息集合 $I \subset \{1,2,\cdots,n\}$ ，其补集记为 $J = I^C$
计算系统化矩阵 $U$ 使得：
$(\mathbf{U H})_I=\mathbf{A} \text { and }(\mathbf{U H})_J=\mathrm{Id}_{n-k},$
计算 $\mathbf{s^\prime = sU^T}$
对所有 $\mathbf{e_I} \in \mathbb{F}^k_q, \quad \mathbf{wt(e_I)} = v$ ，如果存在 $\mathbf{e}_I$ ，满足 $\mathbf{s^\prime - e_I A^T} = t -v$ ，则算法终止，返回 $\mathbf{e}$ , 使得 $\mathbf{e_I = e_I},\quad \mathbf{e_J = s^\prime - e_I A^T}$ 。
返回第一步，重新选取一个新的信息集。

Lee-Brickell 算法假设有 $v$ 个有效错误落入子集 $I$ 中，另外 $t-v$ 个有效错误错入信息集的补集 $J$ 中，因此：

$\mathbf{e} \mathbf{H}^{\top} \mathbf{U}^{\top}=\left(\begin{array}{ll} \mathbf{e}_I & \mathbf{e}_J \end{array}\right)\left(\begin{array}{c} \mathbf{A}^{\top} \\ \operatorname{Id}_{n-k} \end{array}\right)=\mathbf{s} \mathbf{U}^{\top}$

如果我们穷举所有汉明重量为 $v$ 的向量 $\mathbf{e_I} \in \mathbb{F}^k_q$ ，则 $\mathbf{e_J = sU^T - e_I A^T}$ 的汉明重量恰好为 $t-v$ 。通过额外在单轮中增加一次迭代，增加选择单次信息集时的求解复杂度，减少循环次数。选取恰当的 $v$ 参数值，Lee-Brickell ISD 比朴素的 ISD （ $v=0$ ）算法性能更佳。

Lee-Brickell ISD 单轮迭代的时间复杂度大概为（忽略一些常数）：

$R = (n-k)^{3}+(n-k)^2(n+1) + \left(\begin{array}{l} k \\ v \end{array}\right)(v+1)k$

如果使用 early abort 的思想，时间复杂度可以进一步优化。感兴趣的读者可以去阅读 ISD 相关的 survey。

有效错误集恰好有 $v$ 个落入 $I$ 的概率为：

$p = \left(\begin{array}{l} k \\ v \end{array}\right)\left(\begin{array}{l} n-k \\ t-v \end{array}\right)\left(\begin{array}{l} n \\ t \end{array}\right)^{-1} .$

于是 Lee-Brickell ISD 算法的时间复杂度为：

$T(n,k,w)_{\rm \bf Lee-Brickell} = \frac{1}{p} R \\ = \left(\begin{array}{l} k \\ v \end{array}\right)^{-1} \left(\begin{array}{l} n-k \\ t-v \end{array}\right)^{-1} \left(\begin{array}{l} n \\ t \end{array}\right) ( (n-k)^{3}+(n-k)^2(n+1) + \left(\begin{array}{l} k \\ v \end{array}\right)(v+1)k )$

Dumer Direction

Dumer 方向的 ISD 算法，本文以 BJMM 算法为例，它是目前为止在 binary code 上求解 SDP 渐进最优的算法。BJMM 算法的论文^BJMM12 名为：Decoding Random Binary Linear Codes in 2n/20 : How 1 + 1 = 0 Improves Information Set Decoding，很有意思的一个思路就是利用 binary code 的等式： $0 = 1 + 1$ 去优化 ISD 算法。

在前面提到过的所有 ISD 算法中，它们对错误向量 $\rm\bf e$ 的划分都是基于等式 $0 = 0 + 0, 1= 1 + 0 = 0 + 1$ ，而从来不会用到二元域上的特殊等式 $0 = 1 + 1$ ，也就是说信息集合划分的两个子错误集 $\rm\bf e_I, e_J$ 不会在相同位置同时出现 $1$ （缺省位置默认补 0）。于是 BJMM 的核心思路是把错误向量 $\rm\bf e \in \mathbb{F}_2^n, wt(e) = v$ 划分为： $\rm\bf e = e_1 + e_2$ ，其中 $\rm\bf e_1, e_2 \in \mathbb{F}_2^n$ ，并且汉明重量为 $\rm\bf wt(e_1) = wt(e_2) = \frac{v}{2} + \varepsilon$ ，也就是说我们假设 $\rm\bf e_1, e_2$ 在 $\varepsilon$ 个位置上发生重叠（对应维度均为 1）。

Dumer （包括BJMM）算法的第一步仍然是高斯消元，不同于 Lee-Brickell 方向， Dumer 方向 ISD 的信息集大小为 $k + l$ ，部分高斯消元（Partial Gaussian Elimination）作用在大小为 $n - k -l$ 的方阵。即给定 ${\rm \bf H} \in \mathbb{F}_2^{(n-k) \times n}$ （经过某个置换后）：

$\mathbf{U H}=\left(\begin{array}{cc} \operatorname{Id}_{n-k-\ell} & \mathbf{A} \\ \mathbf{0} & \mathbf{B} \end{array}\right),$

其中 $\mathbf{A} \in \mathbb{F}_2^{(n-k-\ell) \times(k+\ell)}$ ， $\mathbf{B} \in \mathbb{F}_2^{\ell \times(k+\ell)}$ 。

我们将错误向量按照信息集进行划分 $\mathbf{e}=\left(\mathbf{e}_1, \mathbf{e}_2\right)$ ，其中 $\mathbf{e}_1 \in \mathbb{F}_2^{n-k-\ell}$ ，汉明重量 $t-v$ ， $\mathbf{e}_2 \in \mathbb{F}_2^{k+\ell}$ ，汉明重量 $v$ ，将 syndrome 做同样划分， $\mathbf{s} \mathbf{U}^{\top}=\left(\mathbf{s}_1, \mathbf{s}_2\right)$ ，其中 $\mathbf{s}_1 \in \mathbb{F}_2^{n-k-\ell}$ ， $\mathbf{s}_2 \in \mathbb{F}_2^{\ell}$ 。因此我们想要求解的 SDP 为：

$\mathbf{U H e}^{\top}=\left(\begin{array}{cc} \operatorname{Id}_{n-k-\ell} & \mathbf{A} \\ \mathbf{0} & \mathbf{B} \end{array}\right)\left(\begin{array}{c} \mathbf{e}_1^{\top} \\ \mathbf{e}_2^{\top} \end{array}\right)=\left(\begin{array}{c} \mathbf{s}_1^{\top} \\ \mathbf{s}_2^{\top} \end{array}\right) .$

即：

$\begin{aligned} \mathbf{e}_1^{\top}+\mathbf{A e}_2^{\top} & =\mathbf{s}_1^{\top}\\ \mathbf{B e}_2^{\top} & =\mathbf{s}_2^{\top} \end{aligned}$

Dumer 方向 ISD 算法的思路是求解第二个等式：寻找汉明权重等于 $v$ 的错误向量 $\mathbf{e}_2 \in \mathbb{F}_2^{k+\ell}$ 使得 $\mathbf{e}_2 \mathbf{B}^{\top}=\mathbf{s}_2$ 。然后计算 $\mathbf{e}_1=\mathbf{s}_1-\mathbf{e}_2 \mathbf{A}^{\top}$ ，检查其汉明重量是否满足 $\rm\bf{wt(e_1)} = t - v$ 。

注意到，求解第二个等式，本质上就是求解一个更小规模的 SDP 问题，校验矩阵为 $\mathbf{B} \in \mathbb{F}_2^{\ell \times(k+\ell)}$ ，并且此时我们需要求解出一系列的解。Dumer 方向的 ISD 算法对这个小规模 SDP 的求解采用了 Wagner 的算法框架： Merge，即广义生日悖论问题（general birthday problem）的时间-空间权衡算法。

Dumer 方向 ISD 的求解框架大致分为两步：

部分高斯消元（PGE）得到两个方程，包含一个更小规模的 $\mathcal{SDP}$ 问题。
利用 Wagner 算法求解更小规模的 $\mathcal{SDP}$ ，验证汉明重量。

BJMM 算法中 $1 + 1 = 0$ 的优化

BJMM 中 merge 的思路其实很简单。每次我们寻找目标向量解时，两个列表的目标候选向量都会选定重叠（overlap）段的长度为 $\varepsilon$ ，如之前给出的 Dumer 方向图中的蓝色部分所示：

图二：Dumer 方向优化

准确地来说，BJMM 算法会选定两个最优的参数 $\varepsilon_1, \varepsilon_2$ 和 $u_1,u_2$ ，令：

$\begin{aligned} & v_1=v / 2+\varepsilon_1, \\ & v_2=v_1 / 2+\varepsilon_2 . \end{aligned}$

定义 Merge 算法如下（ $x_{\mid u}$ 表示 $x$ 向量的前 $u$ 维）：

图三：Merge

首先我们生成两个汉明重量为 $v_2$ 的随机向量列表：

$\mathcal{B}_i=\left\{\mathbf{x} \in \mathbb{F}_2^{k+\ell}\left(P_i\right) \mid \mathrm{wt}_H(\mathbf{x})=v_2 / 2\right\} , i \in 1,2$

预定义需要寻找的中间目标向量形式为：

$T^{(1)} = \left\{ \begin{array}{lr} \mathbf{t}_1^{(1)} \in \mathbb{F}_2^{u_1} \\ \mathbf{t}_2^{(1)}=\left(\mathbf{s}_2\right)_{\mid u_1}+t_1^{(1)} \end{array} \right.$ $T^{(2)} = \left\{ \begin{array}{lr} \mathbf{t}_1^{(2)} \in \mathbb{F}_2^{u_2} \\ \mathbf{t}_2^{(2)}=\left(\mathbf{t}_1^{(1)}\right)_{\mid u_2}+\mathbf{t}_1^{(2)} \\ \mathbf{t}_3^{(2)} \in \mathbb{F}_2^{u_2} \\ \mathbf{t}_4^{(2)}=\left(\mathbf{t}_2^{(1)}\right)_{\mid u_2}+\mathbf{t}_3^{(2)} \end{array} \right.$

容易看出，任意的 $\mathbf{t}_1^{(2)}$ 和 $\mathbf{t}_2^{(2)}$ 进行 merge ，必然能够得到 $(\mathbf{t}_1^{(1)})_{\mid u_2}$ ，依次类推。于是， BJMM 中三个阶段的 Merge 流程如下：

对于基础向量列表 $\mathcal{B}_1, \mathcal{B}_2$ ，选定目标向量为 $\mathbf{t}_i^{(2)}$ ，其中 $i \in\{1, \ldots, 4\}$ ，目标维度数为 $u_2$ , 目标汉明重量为 $v_2=v_1 / 2+\varepsilon_2$ ，进行四次 Merge 操作：
$\mathcal{L}_i^{(2)}=\mathcal{B}_1 \bowtie \mathcal{B}_2, i = 1,2,3,4$
此时 $\mathcal{L}_i^{(2)}$ 列表的目标向量前 $u_2$ 维度均落入 $T^{(2)}$ 。
对第一步生成的列表进行进一步 Merge ：
$\mathcal{L}_i^{(1)}=\mathcal{L}_{2 i-1}^{(2)} \bowtie \mathcal{L}_{2 i}^{(2)}$
目标向量为 $\mathbf{t}_i^{(1)}$ ，其中 $i \in\{1,2\}$ ，目标维度数为 $u_1$ ，目标汉明重量为 $v_1=v / 2+\varepsilon_1$ 。
对第二步生成的列表进行最终 Merge ：
$\mathcal{L}=\mathcal{L}_1^{(1)} \bowtie \mathcal{L}_2^{(1)}$
目标向量为 $\rm\bf s_2$ ，目标维度数为 $\ell$ ，目标汉明重量为 $v$ 。

经过上面三步，我们就能得到小规模 SDP 的一系列解，即对于任意 $x \in \mathcal{L}$ ，满足 $\mathbf{B x}^{\top}=\mathbf{s}_2^{\top}$ 。

这个算法流程其实就是广义生日悖论问题的 Wagner 算法框架，BJMM 的额外加入的目标汉明权重限制选取为：

$\begin{aligned} & v_1=v / 2+\varepsilon_1, \\ & v_2=v_1 / 2+\varepsilon_2 . \end{aligned}$

是整个算法的精髓所在，因为通过选取最优化的 $\varepsilon$ ，这样权重限制的向量是很容易找到的。在一般有限域 $\mathbb{F}_q$ 上，这样选取不会对算法有所优化，因为只在 binary code 上存在 $1 + 1 = 0$ 。

图四：BJMM 算法全流程

ISD Estimator

值得一提的是，目前在编码密码学 $\mathcal{SDP}$ 这一块，最新的工作成果是去年欧密会上的一篇论文：New Time-Memory Trade-Offs for Subset Sum — Improving ISD in Theory and Practice ，其相关实现和 estimator 都已经开源至：decoding 和 Improving-ISD-in-Theory-and-Practice ，这篇工作的本质还是对 BJMM 算法进行了优化。

本节简单介绍 ISD (SDP) estimator 的开源项目，Syndrome Decoding_Estimator ，论文为 Syndrome Decoding Estimator ，它对目前主流的 ISD 算法求解 $\mathcal{SDP}$ 的时间复杂度和空间复杂度进行了评估，并且能够自动给出最优参数。在去年，该项目并入了 CryptographicEstimators: a Software Library for Cryptographic Hardness Estimation 中的 $\mathcal{SDP}$ 模块，开源项目在 CryptographicEstimators 上，可以直接在 sage 上进行安装，并且提供了一个 online 的 web 交互页面：SDEstimator。

Decoding Challenge 上 $\mathcal{LW}$ （低汉明重量码字问题）的参数取 $n = 1280, k =640, w = 144$ ，它声称的安全强度是 128 比特（BJMM 的渐进最优复杂度）， $\mathcal{LW}$ 和 $\mathcal{SD}$ 的求解是类似的， $\mathcal{LW}$ 能转换成一般形式的 $\mathcal{SD}$ 使用 ISD 算法求解，评估结果如下：

满足其声称的安全强度。

参考文献

^ISD20. Information Set Decoding in the Lee Metric and the Local to Global Principle for Densities，https://user.math.uzh.ch/weger/thesis.pdf ↩

^{Code-Survey22}. A Survey on Code-Based Cryptography，https://arxiv.org/abs/2201.07119 ↩

^BJMM12. Decoding Random Binary Linear Codes in 2n/20 : How 1 + 1 = 0 Improves Information Set Decoding，https://eprint.iacr.org/2012/026.pdf ↩