Goppa码的维数

Question

对于McEliece/Niederreiter密码体制，有效的看似安全的码选择是一种不可约的二进制Goppa码，由不可约g(x)\in GF(2^m)[x] of t和支持向量L=(\alpha_0,\ldots,\alpha_{n-1})定义。

代码本身就是奇偶校验矩阵GF(2)-valued向量，注意H是满秩的。为了在GF(2)上生成奇偶校验矩阵D8，可以在GF(2)中用列向量替换H的条目(使用扩展GF(2^m)/GF(2)的一些基础)。

我查阅的几乎所有源代码都将结果代码列出为[n,k]=[n, n-mt]，但是一般的构造(例如交替代码)给出了k=n-mt作为结果子空间代码的维度k的下界。

我的问题是：

1. 产生的秩k=n-mt多长时间一次？在AG的设置中，我猜这是一个Riemann维数，所以也许代数几何可以回答。
2. 如果我们在奇偶校验H'中有冗余行重要吗？这会影响密码系统的实现吗？

我想这在https://eprint.iacr.org/2017/595.pdf的密钥生成器中得到了解决(第5.2节)，如果只返回故障并在没有实现rref的情况下重新启动密钥生成过程；它们根据GL_{mt}(GF(2))在Mat_{mt\times mt}(GF(2))中的密度给出29%的成功概率，即渐近密度为\prod_{i=1}^{\infty}\left(1-\frac{1}{2^i}\right)=0.288\ldots. 。

再考虑一下1)，我想更多的问题是线性映射的核是什么时候在子域上定义的(例如，x-\sqrt{2}y的核在\mathbb{Q}(\sqrt{2})上有维1，而当限制在\mathbb{Q}上时，维数是零)。

Answer 1

1. 从启发的角度来看(对于密码学方面的参数)，这是不太可能的。具有随机项的二元n\times(n-r)矩阵的秩亏概率小于2^{-n+r}矩阵。可能有一个更精确的几何答案。
2. 代码可能是通过使用行转换将H'以系统形式(I|A)放置，然后以二进制Goppa代码作为(I|A^t)来计算的。如果H'是秩不足的，那么实现将需要有一种方法来检测完整的系统形式尚未实现，并丢弃H'的其余行。如果H'的等级是r，那么我们的二进制Goppa代码生成器矩阵将是n\times(n-r)，它可能比分配的内存要大(并且增加了已经很痛苦的带宽问题)。生成矩阵中的一些行现在必须丢弃。为了保持信息集解码的难度，我们希望避免冗余列，因此在删除行、排列列和重新系统化之前，我们可能要随机地对生成器矩阵进行系统化。还有一个有趣的问题，那就是，删除的行可以被呈现给我们的解码器，并成功地避免混淆到不在我们的生成器矩阵范围内的东西，但是我们的解码器可能会使用我们的再结晶矩阵来将其映射到生成器矩阵的范围。实现不太可能为此做好准备，并且可能表现出不可预测的行为。选择一个新的g(X)重新开始可能会更好。