やりたかった事（符号とか知ってる人向け）

途中ですが公開しておきます。

Goppa符号は1970年代に符号長を伸ばしたときの性能が良い代数的符号として考案された。

まず自分の知りたかったことは、任意の文字列をシンドロームにできないか？ということと、そのシンドロームを他の符号と共有できるか？という疑問だった。
これらが関係していつの間にかIDベース暗号の符号バージョンなんかを妄想していたのだ。
しかし、今回はIDベースになるかどうかはわからないが、任意の文字列から、それをシンドロームに持つようなエラーベクトルと符号多項式の対を簡単に計算する方法がわかったので記事にした。

ここで、Goppa符号をそのまま認証符号やハッシュ関数として使用するのはやめたほうが良いと分かる。
なぜなら割り算アルゴリズムは、任意のシンドロームに対する複数の符号とエラーの対を計算できるからである。

そこでシンドロームに対する、（異なる符号との）衝突（コリジョン）を見つける方法について書きます。

シンドロームから割り算で生成多項式を逆算する

$g(x),S(x),l(x),w(x)$をそれぞれ、Goppa多項式、シンドローム多項式、エラーロケーター、最大公約多項式であるとする。
いま任意のバイト列を係数とするシンドローム多項式$S(x)$から、符号とエラーベクトルを出力することを考える。
この４つの関数の関係式は、
$$S(x)l(x)+u(x)g(x)=w(x)$$
と書ける。この式は符号理論で鍵方程式とよばれています。これは、
$$S(x) \equiv \frac{w(x)}{l(x)} \pmod{g(x)} $$
のように書くこともでき、符号の復号でよく見かけます。
$l(x)$はエラーの位置を指定するための１次式の積であり、$t$をエラーの個数とすると$deg(w)<t$という制限があります。
ここで$l(x)$をランダムに選ぶのに確率的アルゴリズムを使う。
まず、上の式を変形して次のようにする。
$$S(x)l(x)+w(x)=u(x)g(x)・・・（＊）$$
この式の$u(x)$が肝です。
名もないこの関数で全体を割れば、一発で符号多項式が計算できます。

つまり、$$g(x) = \frac{S(x)l(x)}{u(x)},w(x) \equiv S(x)l(x) \pmod {u(x)}$$となる。

実際１次多項式を因子に持たない（持つと符号が短くなる）全ての多項式$g(x)$はGoppa符号に使えるので、この式も一発で計算できるはずです。

当たり前のようだが、任意のシンドロームに対するエラーベクトルと符号の対を求める方法がこれで実現できるはず。やってみると実に当たり前で、１つのシンドロームに対応する符号の数は沢山ある。計算結果もあうし、妙に納得できる。

鍵空間が$deg(u)=T-1$で決まるので、今回の割り算法でお好みの位置にエラーを持つような符号多項式が１２８次以上あっても恐るるに足りないものとなりました。（今までは因数分解をしていた）

これが攻撃法に使えるかも知れないというのも指摘しておきましょう。
なぜなら符号多項式を全数探索するよりも、$u(x)$の総探索のほうが範囲が狭いからです。
いろいろな見方があると思いますが、例えばエラー位置関数$l(x)$とシンドローム$S(x)$を固定した場合、$u(x)$の数だけ取りうるエラーの値があるということです。
最初はこれで暗号が作れないかを考えましたが、エラーとシンドロームの両方を同時に公開してはいけないことがはっきりしました。

こうして任意のシンドロームに対応するエラーと符号の対を見つける方法ができたのだった。

エラーベクトルから１つのシンドロームへの写像の数は、定義体を$GF(2^m)$とし、エラーのハミング重みを$T$とすると、$2^{m(T-1)}$もある。
この全てが、$f(x)=g(y)=S$となる。
これはハッシュ関数で言うところの衝突である。
エラーの位置だけで値は問題とならない場合は、パターソン復号を使って更に２倍のエラーを訂正できる。この場合もシンドロームの衝突は計算できるのだろうか？

そして、このような異なる射による像が一致するような衝突のことを、暗号ではクローと呼ぶ。
クローフリーであることは偽造不可能な電子署名を構成する場合に必要とされる性質だが、Goppa符号にはこのような性質にかけていることが分かる。つまりGoppa符号で電子署名を作ると、クローがあるので安全な電子署名はそのままでは作れなくなる可能性がある。歯科モクローは１つのシンドロームに対して２５６ビットサイズの多項式が当てはまる。

シンドロームを共有する

この状況を鍵配布や秘密分散に使えないだろうか。

普通は意味のないビット列であるシンドロームに、任意の文字列を使うことができるというのは意外なことに気がついた。つまり同一のシンドロームから異なるエラーベクトルが得られることを利用すれば、$u(x)$を秘密鍵にして何か出来るのではないかと勝手に期待している。（シンドロームを入力とする多重線形写像？）
即ち、（トラップドアとして）$u(x)$なしに$S(x)l(x)$から符号$g(x)$を計算することができないようにしたいのだった。しかし、エラーを公開するということは$l(x)$が分かるということで、エラーは公開したらだめなのかも。符号系の暗号は符号多項式$g(x)$がわからなくても、検査行列というシンドロームを生成するための手段があることが一つの鍵になっているみたいです。

また符号系の公開鍵暗号を攻撃する時、符号の生成多項式を総探索するという方法もありますが、$u(x)$を総探索したほうが効率が良いことが解ります。

シンドロームを固定した場合、衝突を起こす写像は、実に$2^{m(T-1)}$もある。
衝突が問題になるときは、同一符号内での衝突を考えている場合であり、今回の発見は異なる符号にあるため問題にならない。
このように、異なる符号をまたいだシンドロームの衝突は簡単に見つけられる。
とはいえ、当初の目的はIDベース署名などを作ることであり、任意の文字列をシンドロームにできないか、を考えていたのだった。

実験しよう

ここで定理のようなものが出来上がる。
１つのシンドロームは$2^{m(t-1)}$個の異なる符号とエラーの対に対応する。

これだけではあまり面白くないので、検査行列をハッシュ関数$f$としたときに、衝突がないことも言えるかも知れない。つまり、$g(x)$と$S(x)$を固定した時に、$l(x)$を１次の式に分解できる$u(x),w(x)$が存在しないことが言えればいい。これが言えると、第２原像困難性が言える。つまり入力$x$に対して、$f(x)=f(y)$（$x$は既知）であるような別の入力$y$が存在しないことが言えればいい。またハッシュ関数であるならば、$g(x)$は常に１つ固定しなければいけない。これが固定された場合でも、長いメッセージを処理する場合に衝突がないようにハッシュ関数を設計するのは難しい。同様にして長さを固定した場合に、$f(x)=f(y)$である２つの入力$x,y$を（もしあれば）探すのは鍵方程式があればそんなに難しくない気がする。ハミング重みとか考えると難しいけど、多項式だと考えれば解りそうな気がする。

符号の場合、つまり鍵多項式の$l(x)$の次数が$g(x)$の半分以下なら一意性が保証されるのであった。では$l(x)$がそれを超えるとどうなるのだろうか？

IDベース暗号が不可能でも、鍵委託や秘密分散に使えるのではないかと色々考えている。

Omake

この話を２変数、つまり平面代数曲線で考えるとどうなるかはチャレンジ問題である