The Goppa Code Distinguishing (GD) problem asks to distinguish efficiently a generator matrix of a Goppa code from a randomly drawn one. We revisit a distinguisher for alternant and Goppa codes through a new approach, namely by studying the dimension of square codes. We provide here a rigorous upper bound for the dimension of the square of the dual of an alternant or Goppa code, while the previous approach only provided algebraic explanations based on heuristics. Moreover, for Goppa codes, our proof extends to the non-binary case as well, thus providing an algebraic explanation for the distinguisher which was missing up to now. All the upper bounds are tight and match experimental evidence. Our work also introduces new algebraic results about products of trace codes in general and of dual of alternant and Goppa codes in particular, clarifying their square code structure. This might be of interest for cryptanalysis purposes.
翻译:Goppa 代码区分( GD) 问题要求有效地区分 Goppa 代码的生成器矩阵和随机绘制的生成器矩阵。 我们通过新的方法,即研究平方代码的维度,重新审视外源代码和戈ppa 代码的区分器。 我们在此为迭代代码或Goppa 代码的正方方形的维度提供了严格的上限, 而前一种方法仅提供了基于超自然学的代数解释。 此外, 对 Goppa 代码而言, 我们的证据也延伸到非二元代码, 从而为迄今缺失的区分器提供了代数解释。 所有上界都紧紧, 匹配实验性证据。 我们的工作还引入了一般的痕量代码产品, 特别是变代码和戈帕 代码的双值产品的新代数结果, 澄清它们的正方码结构。 这也许有助于加密目的 。