バイナリゴッパコード

数学とコンピュータサイエンスにおいて、バイナリ ゴッパ コードは、もともとValerii Denisovich Goppaによって記述された一般的なゴッパ コードのクラスに属するエラー訂正コードですが、バイナリ構造によって非バイナリ バリアントに比べていくつかの数学的な利点があり、コンピュータや電気通信での一般的な使用にも適しています。バイナリ ゴッパ コードは、McEliece のような暗号システムや同様の設定 での暗号化に適した興味深い特性を持っています。

既約なバイナリ ゴッパ コードは、重根を持たない有限体上の次数の多項式 と、の根ではないからの異なる要素のシーケンスによって定義されます。 ${\displaystyle g(x)}$${\displaystyle t}$ ${\displaystyle GF(2^{m})}$${\displaystyle L_{1},...,L_{n}}$${\displaystyle n}$${\displaystyle GF(2^{m})}$${\displaystyle g}$

コードワードはシンドローム関数のカーネルに属し、次のサブスペースを形成します。 ${\displaystyle \{0,1\}^{n}}$

${\displaystyle \Gamma (g,L)=\left\{c\in \{0,1\}^{n}\,{\Bigg \vert }\,\sum _{i=1}^{n }{\frac {c_{i}}{x-L_{i}}}\equiv 0{\bmod {g}}(x)\right\}}$

タプルで定義されるコードは、少なくとも次元を持ち、距離は少なくとも であるため、少なくとも の誤りを訂正しながら、少なくとものサイズのコードワードを使用して長さのメッセージをエンコードできます。これは、形式で 便利なパリティチェック行列を持ちます。${\displaystyle (g,L)}$${\displaystyle n-mt}$${\displaystyle 2t+1}$${\displaystyle n-mt}$${\displaystyle n}$${\displaystyle \left\lfloor {\frac {(2t+1)-1}{2}}\right\rfloor }$ ${\displaystyle H}$

${\displaystyle H=VD={\begin{pmatrix}1&1&1&\cdots &1\\L_{1}^{1}&L_{2}^{1}&L_{3}^{1}&\cdots &L_{n}^{1}\\L_{1}^{2}&L_{2}^{2}&L_{3}^{2}&\cdots &L_{n}^{2}\\\vdots &\vdots &\ddots &\vdots \\L_{1}^{t-1}&L_{2}^{t-1}&L_{3}^{t-1}&\cdots &L_{n}^{t-1}\end{pmatrix}}{\begin{pmatrix}{\frac {1}{g(L_{1})}}&&&&\\&{\frac {1}{g(L_{2})}}&&&\\&&{\frac {1}{g(L_{3})}}&&\\&&&\ddots &\\&&&&{\frac {1}{g(L_{n})}}\end{pmatrix}}}$

この形式のパリティ検査行列は、ヴァンデルモンド行列 と対角行列で構成されており、交互符号の検査行列と形式を共有しているため、この形式では交互デコーダを使用できることに注意してください。このようなデコーダは通常、限定されたエラー訂正機能のみを提供します（ほとんどの場合）。 ${\displaystyle V}$ ${\displaystyle D}$${\displaystyle t/2}$

実用上、バイナリ ゴッパ コードのパリティ チェック マトリックスは通常、トレース構築によって、よりコンピュータに適したバイナリ形式に変換されます。トレース構築では、連続する行の要素の多項式係数を書き込むことによって、- 行- 列のマトリックスを- 行- 列のバイナリ マトリックスに変換します。 ${\displaystyle t}$${\displaystyle n}$${\displaystyle GF(2^{m})}$${\displaystyle mt}$${\displaystyle n}$${\displaystyle GF(2^{m})}$${\displaystyle m}$

バイナリ Goppa コードのデコードは、従来、優れたエラー訂正機能 (すべての設計エラーを訂正) を備えた Patterson アルゴリズムによって行われ、実装もかなり簡単です。 ${\displaystyle t}$

パターソンアルゴリズムはシンドロームをエラーのベクトルに変換します。バイナリワードのシンドロームは次のような形式を取ることが予想されます。 ${\displaystyle c=(c_{1},\dots ,c_{n})}$

${\displaystyle s(x)\equiv \sum _{i=1}^{n}{\frac {c_{i}}{x-L_{i}}}\mod g(x)}$

の式に基づくパリティ チェック マトリックスの代替形式を使用して、単純なマトリックス乗算でこのようなシンドロームを生成することができます。 ${\displaystyle s(x)}$

次に、アルゴリズムは を計算します。 の場合には失敗しますが、これは入力ワードがコードワードの場合に当てはまるので、エラー訂正は必要ありません。 ${\displaystyle v(x)\equiv {\sqrt {s(x)^{-1}-x}}\mod g(x)}$${\displaystyle s(x)\equiv 0}$

${\displaystyle v(x)}$は、拡張ユークリッド互除法を使用して多項式およびに簡約されるため、 となり、 およびとなります。 ${\displaystyle a(x)}$${\displaystyle b(x)}$${\displaystyle a(x)\equiv b(x)\cdot v(x)\mod g(x)}$${\displaystyle \deg(a)\leq \lfloor t/2\rfloor }$${\displaystyle \deg(b)\leq \lfloor (t-1)/2\rfloor }$

最後に、エラー位置多項式は として計算されます。バイナリの場合、他に可能な値は 1 つしかないため、エラーの位置を特定するだけでエラーを修正できます。非バイナリの場合は、別のエラー修正多項式も計算する必要があります。 ${\displaystyle \sigma (x)=a(x)^{2}+x\cdot b(x)^{2}}$

元のコードワードがデコード可能で、がバイナリエラーベクトルである場合、 ${\displaystyle e=(e_{1},\dots ,e_{n})}$

${\displaystyle \sigma (x)=\prod _{i=1}^{n}e_{i}(x-L_{i})}$

したがって、のすべての根を因数分解または評価すると、エラー ベクトルを回復してエラーを修正するのに十分な情報が得られます。 ${\displaystyle \sigma (x)}$

ゴッパ コードの特殊なケースとして見られる 2 進ゴッパ コードには、 3 進およびその他すべてのケースではエラーのみが訂正されるのに対し、 2 進ゴッパ コードではエラーがすべて訂正されるという興味深い特性があります。漸近的に、このエラー訂正能力は有名なギルバート-ヴァルシャモフの限界を満たします。 ${\displaystyle \deg(g)}$${\displaystyle \deg(g)/2}$

バイナリ ゴッパ コードは、コード レートやパリティ チェック マトリックスの形式 (通常、フル ランクのランダム バイナリ マトリックスと区別がつきにくい) に比べてエラー訂正能力が高いため、いくつかのポスト量子 暗号システム、特にMcEliece 暗号システムやNiederreiter 暗号システムで使用されています。

• Elwyn R. Berlekamp、「Goppa コード」、IEEE Transactions on information theory、Vol. IT-19、No. 5、1973 年 9 月、https://web.archive.org/web/20170829142555/http://infosec.seu.edu.cn/space/kangwei/senior_thesis/Goppa.pdf
• Daniela Engelbert、Raphael Overbeck、Arthur Schmidt。「McEliece 型暗号システムとそのセキュリティの概要」Journal of Mathematical Cryptology 1、151–199。MR 2345114。以前のバージョン: http://eprint.iacr.org/2006/162/
• Daniel J. Bernstein. 「バイナリ Goppa コードのリスト デコード」 http://cr.yp.to/codes/goppalist-20110303.pdf

• BCH コード
• コードレート
• リード・ソロモン誤り訂正