McEliece使用非二进制Goppa码是否安全？
具有长度为n位的码字的二进制Goppa码可以在GF(2^m)上用多项式修正t错误，可以对k = n - mt比特长数据进行编码。也就是说，需要添加mt检查位来修复t位。这意味着最多有1/m的码字可以被错误填充。
另一方面，如果您在GF(p)的某个领域工作，其中p是一些素数，那么要修复t错误的符号，您只需要添加更多的2t符号(因为泛型情况的多项式需要有两倍度)。所以k = n - 2t。在最极端的情况下，一半的码字可能是错误的。
如果我正确理解了“信息集解码”，则依赖于找到不包含错误的传输数据的k符号长子集。因此，这意味着能够在消息中引入更多错误是一种优势。一般的Goppa码似乎更能做到这一点。
我们使用二进制Goppa码而不是一般的Goppa码有什么特别的原因吗？二进制代码能更好地抵御其他类型的攻击吗？
编辑:我还对代码的多项式在GF(2^m)上的情况感兴趣，但是代码字的元素不是在GF(2)上，而是在GF(2^m)上。使用像GF(2^{16})这样的字段是很有诱惑力的，因此矩阵和多项式元素用“短词”表示，并且省略了到位部分的转换，这样我们就可以在单个字段中完成所有的工作，生成矩阵的元素也是短词。并将输入作为2字节批处理:可以更容易、更快地实现向量化。
EDIT2：
在信息集解码中，我们正在寻找密文中没有错误的子集。在[n, k, t]代码中。我们可以选择k元素{n \choose k}方式，并且可能正确的猜测数是{n-t \choose k}。因此，偶然发现一个无错误序列的机会是{n-t \choose k}/{n \choose k}。
现在，让我们在GF(1021)上使用通用的Goppa代码。让n = 725，t = 145和k = 725 - 2*145 = 435
所以计算{725-145 \choose 435}/{725 \choose 435} \approx 6.953 \cdot 10^{-71}。这是关于2^{-233}的。所以有233位的保安。
GF(1021)中的元素可以用10位表示，密钥大小为3153750位或约400 of。
使用二进制Goppa码，需要更多的检查符号。考虑在扩展字段GF(2^{13})上使用参数n = 5600、t = 172、so k = 3364的代码
。类似的安全级别。但是矩阵现在大于2MB。
这就是我的问题。
回答 1
Cryptography用户
发布于 2019-07-01 19:38:19
问题是，您所指的只是简单的信息集解码。实际上，对于普通的ISD来说，在\mathbb F_q上攻击Goppa代码的复杂性将如人们所期望的那样在q上扩展。
然而，Stern的ISD算法并不是只根据代码大小进行缩放。
按照几何分布，我们可以将ISD算法的预期成本表示为
对于Stern算法，给定参数p与0 \le p \le w (其中w为误差向量的权重)和l与0 \le l \le n - k，
- 成功迭代的概率并不直接取决于q，可以表示为n、k、w、l和p的函数。
- 一次迭代的成本是(n - k)^2 (n + k) + ((\kappa - p + 1) + 2 N {(q - 1)}^p)l + \frac{q}{q - 1} (w - 2p + 1) 2p (1 + \frac{q - 2}{q - 1}) \frac{N^2 {(q - 1)}^{2p}}{q^l}\text, ，其中\kappa = k / {2}和N = \binom{k / {2}}{p}。
如您所见，算法使用q进行缩放的方式在很大程度上取决于参数p和l。因此，p通常被选择为相当小的，以便将通过太多子集( {(q - 1)}^p和{(q - 1)}^{2p}项)的影响降到最低。
请看克里斯汀·彼得斯的论文，它有整整一章专门讨论这个问题。它还讨论了额外的改进，并提出了p和l的确切值。
当然，\mathbb F_q上也有Goppa码，这样的密码系统是安全的。你也可以在论文中找到一些建议和分析。
https://crypto.stackexchange.com/questions/71505
复制相似问题
腾讯云开发者
