やりたかった事（符号とか知ってる人向け）
途中ですが公開しておきます。
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)$が肝です。
名もないこの関数で全体を割れば、一発で符号多項式が計算できます。
つまり、$$w(x) \equiv S(x)l(x) \pmod {u(x)}, g(x) = \frac{S(x)l(x)+w(x)}{u(x)},$$となる。
ちょっとおかしな感じがするかもしれませんが、$S(x)l(x)+w(x)$は式の形からすると常に$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,g$による像$S$が一致するような衝突$x,y$のことであり、
$$f(x)=g(y)=S$$と書くことが出来る。
これはハッシュ関数で言うところの衝突である。
そして、シンドロームと符号多項式の関係はどうなっているのかが気になります。
クローフリーであることは偽造不可能な電子署名を構成する場合に必要とされる性質だが、Goppa符号にはこのような性質にかけていることが分かる。つまりGoppa符号で電子署名を作ると、クローがあるので安全な電子署名はそのままでは作れなくなる可能性がある。
符号からIDベース暗号はできない？
このように、異なる符号をまたいだシンドロームの衝突は簡単に見つけられる。
この状況を鍵配布や秘密分散に使えないだろうか。
シンドローム復号問題とは、誤り訂正符号に基づく計算困難な問題である。
ランダム化したGoppa符号を$H$とすると、エラーベクトル$x$として$s=xH$をシンドロームという。
シンドローム復号問題とは、公開鍵$H,s$から対応する秘密鍵であるエラーベクトル$x$を求める問題である。
普通は意味のないビット列であるシンドロームに、任意の文字列を使うことができるというのは意外なことであった。つまり同一のシンドロームから異なるエラーベクトルが得られることを利用すれば、$u(x)$を秘密鍵にして何か出来るのではないかと勝手に期待している。
とはいえ、当初の目的はIDベース署名などを作ることであり、任意の文字列をシンドロームにできないか、を考えていたのだった。
つまりこの場合でいうと、メールアドレスをシンドロームに持つようなエラーベクトル$e$とGoppa多項式$g$を鍵センターが発行するという具合に。
ただし、同じメールアドレスをシンドロームとして持つ別の符号とエラーの組もあるため、1つのシンドロームに関して鍵を発行するのは1回だけにするなどセンターが管理しなければならない。
逆に、この状況は鍵が失効した場合には再発行が出来るということである。
また符号系の公開鍵暗号を攻撃する時、符号の生成多項式を総探索するという方法もありますが、$u(x)$を総探索したほうが効率が良いことが解ります。
シンドロームを固定した場合、衝突を起こす写像は、実に$2^{m(T-1)}$組もある。
実験しよう
ここで定理のようなものが出来上がる。
１つのシンドロームは$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
この話を２変数、つまり平面代数曲線で考えるとどうなるかはチャレンジ問題である
追記：２変数以上の多項式の値とn次元平面上の点を使い、２変数以上の単項式で評価してゴッパ符号の他変数バージョンが作れるのかもしれないがやってない。やりたくてもそのような符号の復号が知られていないのでどうにもならない。あるいはユークリッド方の他変数バージョンが出来るのだろうか。
それともGoppaも同じことを考えてうまく行かなかったので代数幾何符号になったのかもしれない。
つまり、符号多項式を２変数以上に一般化したもので符号が作れるのかが知りたい。
２変数の場合を考えると、$\frac{x^iy^j}{C(x,y)} > 0$となり、幾何学的に考えると代数曲線上の多項式写像を考えることになると思われる。（リードマラーがそうなのだろうか、詳しく知らない）
ユークリッド復号をするためには、この符号らしきものの鍵方程式を考える必要がある。