如何使用斯特恩的算法攻击McEliece？

Question

我在读关于McEliece密码系统的攻击的文章。我需要做很多事情，因为到目前为止，我在互联网上发现的大多数描述似乎都是关于细节的手忙脚乱的。所以我写下了我理解的或者我认为我理解的，最后我有一些问题。

在McEliece密码体制中，公钥由一个k×n密钥矩阵K和t引入密文的错误数组成。为了加密，我们采用k元素长消息\mathbf{m}，n元素长错误向量\mathbf{z}和t非零元素，最后得到密文\mathbf{y} = \mathbf{m}K + \mathbf{z}。

攻击者可以使用信息集解码(ISD)对明文进行解码。在k随机线性无关列中，从K中选择一个可逆的k×k平方矩阵A，并选择与列相同位置的k元素形成向量\mathbf{a}。为了获得纯文本，我们计算\mathbf{q} = \mathbf{a}A^{-1}，如果一个元素中的所有元素都是无错误的，这应该会给出纯文本。通过计算\mathbf{y} - \mathbf{q}K = \mathbf{m}K + \mathbf{z} - \mathbf{q}K = (\mathbf{m}-\mathbf{q})K + \mathbf{z}验证结果。如果是\mathbf{m} = \mathbf{q}，则结果是\mathbf{z}，它有t非零元素，我们就完成了.如果是\mathbf{m} \neq \mathbf{q}，那么我们的猜测是错误的。两个码字之间的Hamming距离是最小的2t+1，所以(\mathbf{m}-\mathbf{q})K是至少有2t+1非零元素的向量。\mathbf{z}有t非零元素，所以即使\mathbf{z}恰好从(\mathbf{m}-\mathbf{q})K取消了t元素，结果仍然是t+1非零元素。因此，在结果中有超过t的非零元素意味着失败。

McEliece密码体制选择参数时，不可能找到无错误子序列。

然后我读到还有其他的攻击。将问题转化为最短的码字查找问题的人。并通过将线性代码更改为这样的方式来实现，这样就可以像这样映射消息：\mathbf{x} \mapsto \mathbf{x}K - \mathbf{y}。因此，这转换了K定义的代码中的码字，这保留了最小的Hamming距离要求，所以它仍然是一个纠错代码。在这段代码中，没有零元素，最短的代码字是-\mathbf{z}和t非零元素(当\mathbf{x} = \mathbf{m})。由于最小距离仍然是2t+1，所有其他码字至少有t+1非零元素。因此，如果我们能找到这个最短的码字，那么我们可以删除错误的密文，使ISD成功的第一次尝试。

现在有一件事我被困住了:翻译得到的代码不是线性代码，因为翻译不是线性转换。它中码字的线性组合不一定是另一个码字，也不包含一个全零码字。对吗？

但是，我看到的大多数描述都是将\mathbf{y}作为新行添加到K中，然后计算修改后的代码的奇偶校验矩阵，并将其输入到最小长度码字搜索算法中，例如Stern的算法。当代码不是线性的时候，这是如何工作的，为什么工作呢？

Answer 1

如果我错过了什么就原谅我。

K是一个生成器矩阵吗？我相信是的，这意味着原始代码是线性的。

通过减去y来翻译原始代码是一个陪集，有时被称为仿射子空间。它几乎具有子空间的所有优点。

特别是，翻译代码的元素和是原始代码中的码字(特征二均值和与差相同)。