古典的Goppa符号をユークリッド法で復号します。
そして、Looooooongシンドロームも復号してみたいです。
まえがき
私は暗号をやる上で、近年、多項式を扱うことが増えた。
多項式は整数より複雑な構造の代数系であり、それだけ多様な性質を持つ。
超楕円曲線のヤコビアン、格子暗号、多変数多項式暗号、そして符号ベースの暗号などにも多項式は大活躍である。
私はコロナまっただ中の2019年ころから、約2年掛けて多項式ライブラリを自作してきた。
それまでは自分で勝手に暗号を作って遊んでいた。
とても人様に見せられるものではないけれど、積み重ねがあったおかげで符号、そして格子暗号も短期間で実装できるようになった。格子暗号に関してはわずか1日で基本的な昨日を実装できた。（ただし、規格には従っていない）
ただ自分には数学の才能がないので、証明や数式を理解するのが苦手である。
私の解説や実験は間違っている可能性が高いので、記事には間違いがあると思う。
その時はコメントをいただきたい。
そこで、この記事では多項式のユークリッドアルゴリズムをつかって、誤り訂正符号の一つであるGoppa符号の復号法を解説したい。ここでいうGoppa符号とは古典的な方で、代数幾何符号のことではない。代数幾何符号をここでは幾何学的Goppa符号と呼ぶことにして、Goppa符号とは別のものとして扱う。
符号の材料である有限体については必要最小限の記述をする予定であるが、なるべくシンプルにしたいので、ここで扱う有限体は比較的小さな素数を用いた素体を扱うことにする。
体とは、集合に四則演算が定義されており、元に対する各演算の結果がもとの集合に含まれるという性質を満たす集合のことである。
有限体はこのくらいにして、早速ユークリッドアルゴリズムについて書こう。
この説明のハイライトは、ユークリッド法を使ってGoppa符号を複合することであるが、この復号では過剰なエラーを入れた時に複合する方法を知らないので、その場合は次の話で倍サイズのシンドロームに新調できることを示す。なぜユークリッド方ではできないのかといえば、検査行列の構造が複雑だからである。
また、余興ではあるが、鍵法的式を合同式で表して２つのシンドローム多項式を純粋に多項式で扱った場合、復号に必要な頭値位置多項式を復元で聞き内科を研究してみる。（これは失敗する可能性が高い）
整数のユークリッドアルゴリズム
手始めに高校でやる整数のユークリッドアルゴリズムを説明します。
最大公約数と一意分解整域
合同式
多項式のユークリッドアルゴリズム
多項式としての誤り訂正符号
鍵方程式登場
ユークリッドアルゴリズムと鍵方程式
多項式の係数行列と線形代数
ユークリッド復号法
過剰なエラーが入った場合どのように復号するか
１つの場合では簡単でも、同じ符号に対して２つ以上のエラーベクトルが衝突する場合などエラーをどんどん増やした場合はどうなのか、シンドロームの性質が分かりそう。ここで、式の形が重要になってくる。
鍵方程式と合同式
例えば１つの符号に過剰なエラーを入れた場合を考える。
今、訂正可能なエラーの数を$t$と置き、さらに$t'$個の過剰なエラーを入れたとする。
まず、エラーを訂正可能なエラー$t,t'$に分ける。
それぞれに対応するシンドロームを$s=tH,s'=t'H$とすると、同一符号内ではこの２つを足したものがシンドロームとなっている。
$$(t+t')H=S_1+S_2=S$$
ここでこの状況を鍵方程式でどうなっているか考える。
$$S_1(x)l_1(x)+u_1(x)g(x)=w_1(x)$$
$$S_2(x)l_2(x)+u_2(x)g(x)=w_2(x)$$
このように鍵多項式は同一符号内で独立している。
更に変形すると、
$$S_1(x)l_1(x) \equiv w_1(x)\pmod{g(x)}$$
$$S_2(x)l_2(x) \equiv w_2(x)\pmod{g(x)}$$
このまま無理やり計算しようと思っても、位置多項式の情報が潰れて上手く行かない。
$$S_1(x)l_1(x)+S_2(x)l_2(x)+(u_1(x)+u_2(x))g(x)=w_1(x)+w_2(x)$$
これらは同一の符号で起きているので、次のようにも書ける。
$$S_1(x)l_1(x)+S_2(x)l_2(x) \equiv w_1(x)+w_2(x)\pmod{g(x)}$$うーん。難しいのう。
この場合でも、$w_1(x)+w_2(x)$が$(S_1(x),S_2(x),g(x))$の倍数であれば合同式を解くことができます。つまり１次不定方程式を解けば良いのです。（考察中）
そしてユークリッドの互除法を使っても$l_1,l_2$は求められそうです。
ここで言えるのは、まず１つの符号の中に過剰なエラーが入ったときは、訂正可能なエラーに分割し、それに対応するシンドローム多項式をそれぞれ掛けて２倍サイズのシンドロームを計算すれば良いことが分かる。（シンドロームを掛けるなんてことが許されるのかどうかがわからないが。）
するとこれはどこかで見たような・・・。
$$S=S_1+S_2=(e_1+e_2)H$$であり、$S_1l_1+S_2l_2$
$$S^2=(S_1+S_2)(S_1+S_2)=S_1^2+2S_1S_2+S_2^2$$
ここで、定義体は$GF(2^m)$なので、
$$S^2=S_1^2+S_2^2$$
残念、$S_1S_2$は計算できません。$K=32$の時、鍵方程式を使うと、
$$Sl_1l_2 \equiv w_1w_2 = w \pmod {g^2(x)}$$
$$l_1l_2 \equiv \frac{w}{S_1S_2} \pmod {g^2(x)}$$
ここで、もとの方程式をみてみると、
$$S_1S_2l_1l_2+ug^2=w$$
である。
従って、$S_1S_2$と$g^2$を入力としてユークリッド法を使えば$w$を計算できる。（何かが間違っているせいか計算できません。）
ここで、合同式
$S_1l_1 \equiv w_1 \pmod {g}$
$S_2l_2 \equiv w_2 \pmod {g}$
と２つのパートに分かれている。これらをまとめると、
$$S_1S_2l_1l_2 \equiv w_1w_2 \pmod {g^2}$$
$$g^2l_1l_2 \equiv 0$$
$$(S_1S_2+g^2)l_1l_2 \equiv w_1w_2$$
こんなふうに合同式だけで綺麗にまとまってしまう。
高校の参考書で思いついたのだった。（やり直せ）
と、上手く行けば良いのですが、計算結果は全然合いません。
間違っているんだろうけど・・・。
ユークリッド法だと計算できません。
当然のことながら$w_1w_2$を別途送信すれば計算できます。
ということは式の上ではあっているけど、符号的には勘違いということになります。
シンドロームだけでは復号できないという時点でこの論理は破綻してますね。
つまり、$S_1S_2$が効率的に計算できれば、過剰なエラーの場合でも復号できそうである。
ところがこれは難しいので、受信者が出来ることはあまりない。
20250129（改）
何という馬鹿なことを考えているのだと思ったので計算してみました。
その結果、例外的にエラーの値を１だけにすれば可能らしいことが解りました。
１以外だとエラー同士で混ざってしまい、シンドローム同士を掛けた段階で訂正不可能になります。
つまり１以外のエラー値が入ったシンドローム同士を掛けると、もはやシンドロームでさえなくなってしまうのです。
例え多項式として正しくても、符号的に見れば間違っていたのです。
その代わり、エラーの値がバイナリなら符号の成分を壊さずに済むので訂正できそうです。
そう、２倍サイズのシンドロームはあります！
しかしこの場合でもまだ問題があります。
異なるエラーベクトルを含んだシンドローム同士を掛けたら、訂正可能なエラーの数が増えるのでしょうか？（いや、かければ掛けるだけ符号多項式の次元を上げることになるのかもしれない。）
ここでは、純粋に多項式として公約多項式を追加して送信するか、あるいは小さな符号にバイナリエラーを入れて受信先で２倍サイズのシンドロームにするかという方法がありそうです。（２倍以上のサイズのシンドロームができればいい）
式の上では間違っていないのですから、多項式だったら合同式同士を掛けるというのはあります。
今までシンドロームを完全に多項式として扱っていたのですが、多項式である以前にこれは符号なのです。
バイナリエラーならシンドロームを破壊しないで情報量を２倍にできそうです。（２倍まで？）
今の所リードソロモン符号では２倍サイズのシンドロームからエラーを訂正できるようです。
じゃあリードソロモンでLooooooong Syndromeを復号すればいいということになるのでしょうか？
上手く行ってるリードソロモンで先に結論を出すことにします。（後日）
Goppaの場合で上手く行かないのは、符号の構造が複雑なせいかもしれません。
しかしこれはこれで面白いのでどうなるのかやっています。
もし拡大体でだめならバイナリ符号バージョンでできないか試して見る予定です。
そこで送信者に計算してもらうことにする。
シンドロームが同一の符号多項式で作られているのであれば、符号を分けることで２つのエラーに対するシンドロームを決めることが出来る。
あとはこの２つのシンドロームの積を計算して送信し、受信者は$g^2$で復号すれば良い。（ホントかよ！ｗ）
実験したけどうまくいかないのは、合同式の性質を理解していないからだと思う。（高校レベル以下）
同じ法で両辺を掛けることは出来るようだ。
送信語を暗号文とする方法では、受信語を分割してそれぞれに対してシンドロームを計算し、それぞれ復号することで処理できそうだ。しかし、Niederreiterのように、シンドロームとして暗号文が送られてくる場合は、送信側でシンドロームを伸長しなければ計算することはできないだろう。
以下では、この伸長されたシンドロームのことをLooooooong Syndromeと呼び、$LS(x)$と書くことにする。
ところで今は、勝手に$S,l$を決められるのであった。
この状況を暗号に使うことはできないだろうか？
そう、いま勝手なシンドローム$S_1,S_2$に対して、同じ符号$g$でのエラー位置$l_1,l_2$を指定して、鍵方程式をちょっといじると、
$$u_1=\frac{S_1l_1}{g},u_2=\frac{S_2l_2}{g}$$
となるはずである。ここで$S_1,S_2,l_1,l_2$が自由に選べるのだから、
$$u_1u_2=\frac{S_1S_2l_1l_2}{g^2}$$
となるはずである。
これだけわかれば、$S_1=S_2$になるためには$g^2 \neq g_1g_2$でなければならないということが言えそうな気がするけどわからない。
ここで次の式を思い出そう。
$$S_1S_2l_1l_2 \equiv w_1w_2 \pmod {u_1u_2}$$
ということは、つまり同一符号内で過剰なエラーが発生した時、$S_1+S_2$ではなく、エラーを２つに分けてそれぞれに対するシンドロームを$S_1,S_2$とすると、この２つのシンドロームの積と符号多項式の平方を使って$t+1$個以上のエラーが訂正できるはずである。問題はどのようにこの積を計算するかだ。
Looooooong Syndrome復号はなぜ実現不可能か？
一言で言えば、掛けた段階で各シンドローム多項式に含まれるエラーの値が鑑賞してお互いを識別不可能に破壊してしまうため、それらは多項式である事はさておきシンドロームとしては無意味になってしまうからである。
しかしここではまだ救いがある。バイナリエラーであれば干渉を最小限に抑えることが出来るのだ。
更にこの２倍化されたシンドロームを複合できるのはバーレカンプマッシーが最もシンプルであるので、ここで計算を中心にやってみることにする。
具体例は現在準備中なので待ってほしい。
第二部に続く。
参考文献：Error-Correcting Codes and FInite Fields by Olyver Pretzel