符号理論の鍵方程式で遊ぶ(パート2)
シンドロームは2倍化できない
1つの場合では簡単でも、同じ符号に対して2つ以上のエラーベクトルが衝突する場合などエラーをどんどん増やした場合はどうなのか、シンドロームの性質が分かりそう。ここで、式の形が重要になってくる。
例えば1つの符号に過剰なエラーを入れた場合を考える。
今、訂正可能なエラーの数を
まず、エラーを訂正可能なエラー
それぞれに対応するシンドロームを
ここでこの状況を鍵方程式でどうなっているか考える。
このように鍵多項式は同一符号内で独立している。
更に変形すると、
このまま無理やり計算しようと思っても、位置多項式の情報が潰れて上手く行かない。
これらは同一の符号で起きているので、次のようにも書ける。
この場合でも、
するとこれはどこかで見たような・・・。
ここで、定義体は
残念、
ここで、合同式
と2つのパートに分かれている。これらをまとめると、
こんなふうに合同式だけで綺麗にまとまってしまう。
この式を一般化すると、
シンドローム
この時点でシンドロームとしての意味が失われるが、依然として多項式としての性質は残っているので、この合同式が成り立つはずである。
実際、
多項式をいじっているだけなので、ここまは別に何も特別なことがない。
そして出来るからと言って特に面白いこともない。
暗号として使うには、送信者は自由にエラーベクトルを決められるので、
シンドロームが同一の符号多項式で作られているのであれば、符号を分けることで2つのエラーに対するシンドロームを決めることが出来る。
しかしシンドロームを計算したくても、2つの異なるシンドロームを掛けた途端にエラーに関する情報が壊れてしまうので復号できなくなります。そもそもシンドロームは二倍化できません。足してから2乗するのと2乗してから足すのと違いをよく理解していないことが原因。
伝家の宝刀ユークリッドアルゴリズムも、壊れたシンドロームを訂正することはできなかったという次第であった。
同一符号内ではどのようにコリジョンが起きるのか
コリジョンというのは、ハッシュ関数の衝突のことである。
パート1では、異なる符号で同一のシンドロームに対する衝突を起こすように符号を決めることが出来るという話であった。
つまり、
このようなコリジョンのことをクローという。
クローのない関数対には偽造不可能な電子署名など暗号技術において重要な結果が知られているが、ここでGoppa符号にはクローがあるので電子署名には使えないだろう。
ここでは更に同じ符号内で過剰なエラーが発生した時、そのような衝突を起こす2つの異なるエラーベクトルは決定できるのか、という問題をパート2にかけて調べる。
ところで今は、勝手に
この状況を暗号に使うことはできないだろうか?
そう、いま勝手なシンドローム
となるはずである。ここで
となるはずである。
これだけわかれば、
つまり、
ここまで言っておいて、式の上ではなんとでもなりそうなのに、過剰なエラーが入った場合、つまり、
世の中そんなに甘くないのだ。
可能性としてはありそうな気がするんだがどうなんだろう。
これはちょっと計算してみれば解りそうですね。(頭が悪いだけ)
次の式を思い出そう。
ここで過剰なエラーを含んだ同一符号内での衝突を考える。
衝突をするわけなので
つまり、
同一符号内でどのような場合に衝突が起きるかに関しては、まだ続く予定である。
とりあえず、シンドローム2倍化計画は頓挫してしまったので、合同式を使ってコリジョン探しをするつもりである。
ここで、ユークリッドアルゴリズムでは
つまり衝突しないだろう。
ここでハミング重みが
このようなエラーが発生すると、鍵方程式ではどうにもならないのかもしれない。
過剰な場合は、多項式
情報が消えてしまう。つまりこのままでは、鍵方程式から情報を得ようとするのは無理である。
法を
どの本にも生成多項式のべき乗の持つ性質が書かれていない。
バイナリ符号の場合、生成多項式のべき乗で符号を構成すると部分符号になるとか等価な符号になるというのはどういう意味なのー?!
(つづく)
Discussion