😽

符号理論の鍵方程式で遊ぶ(パート2)

2025/01/27に公開

シンドロームは2倍化できない

1つの場合では簡単でも、同じ符号に対して2つ以上のエラーベクトルが衝突する場合などエラーをどんどん増やした場合はどうなのか、シンドロームの性質が分かりそう。ここで、式の形が重要になってくる。

例えば1つの符号に過剰なエラーを入れた場合を考える。
今、訂正可能なエラーの数をtと置き、さらにt'個の過剰なエラーを入れたとする。
まず、エラーを訂正可能なエラーt,t'に分ける。
それぞれに対応するシンドロームをs=tH,s'=t'Hとすると、同一符号内ではこの2つを足したものがシンドロームとなっている。

(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))の倍数であれば合同式を解くことができます。つまり1次不定方程式を解ければいいのですが。(考察中)

するとこれはどこかで見たような・・・。

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は計算できません。
ここで、合同式

S_1l_1 \equiv w_1 \pmod {g}
S_2l_2 \equiv w_2 \pmod {g}

と2つのパートに分かれている。これらをまとめると、

S_1S_2l_1l_2 \equiv w_1w_2 \pmod {g^2}
g^2u_1u_2 \equiv 0

こんなふうに合同式だけで綺麗にまとまってしまう。

S_1S_2l_1l_2+g^2u_1u_2 = w_1w_2

この式を一般化すると、k個の重なりのない領域に発生したエラーに対して次の合同式が成り立つはずである。

S_1S_2...S_kl_1l_2...l_k \equiv w_1w_2...w_k \pmod{g^k}

シンドロームS_1S_2...S_kw_1w_2..w_kを追加して送れば、受信先でg^kを知っている人だけが誤り位置多項式を復元できるはずである。
この時点でシンドロームとしての意味が失われるが、依然として多項式としての性質は残っているので、この合同式が成り立つはずである。

実際、w_1w_2があった場合に誤り位置多項式を計算することは出来るが、値まで復元できるかどうかはまだやっていない。
多項式をいじっているだけなので、ここまは別に何も特別なことがない。
そして出来るからと言って特に面白いこともない。

暗号として使うには、送信者は自由にエラーベクトルを決められるので、w_1w_2を計算できる。
シンドロームが同一の符号多項式で作られているのであれば、符号を分けることで2つのエラーに対するシンドロームを決めることが出来る。

しかしシンドロームを計算したくても、2つの異なるシンドロームを掛けた途端にエラーに関する情報が壊れてしまうので復号できなくなります。そもそもシンドロームは二倍化できません。足してから2乗するのと2乗してから足すのと違いをよく理解していないことが原因。
伝家の宝刀ユークリッドアルゴリズムも、壊れたシンドロームを訂正することはできなかったという次第であった。

同一符号内ではどのようにコリジョンが起きるのか

コリジョンというのは、ハッシュ関数の衝突のことである。
パート1では、異なる符号で同一のシンドロームに対する衝突を起こすように符号を決めることが出来るという話であった。

つまり、f(x)=g(y)となるようなペアg,yを見つけられるのだった。
このようなコリジョンのことをクローという。
クローのない関数対には偽造不可能な電子署名など暗号技術において重要な結果が知られているが、ここでGoppa符号にはクローがあるので電子署名には使えないだろう。

ここでは更に同じ符号内で過剰なエラーが発生した時、そのような衝突を起こす2つの異なるエラーベクトルは決定できるのか、という問題をパート2にかけて調べる。

ところで今は、勝手に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_1=S_2でありl_1,l_2を自由に選んだとき、l_1 \neq l_2であるようなg^2は存在しないことが言えればいい。
ここまで言っておいて、式の上ではなんとでもなりそうなのに、過剰なエラーが入った場合、つまり、l_1l_2の次数が訂正限界を上回るときには何も言えなくなってしまうことに気がついた。
世の中そんなに甘くないのだ。

可能性としてはありそうな気がするんだがどうなんだろう。
これはちょっと計算してみれば解りそうですね。(頭が悪いだけ)

次の式を思い出そう。

S_1S_2l_1l_2 \equiv w_1w_2 \pmod {u_1u_2}

ここで過剰なエラーを含んだ同一符号内での衝突を考える。

衝突をするわけなのでS_1=S_2でなければならない。

S \equiv \frac{w_1}{l_1} \equiv \frac{w_2}{l_2} \pmod g

つまり、l_1 \neq l_2, w_1 \neq w_2のとき、上式を満たすようなシンドロームSは存在しないことが言えればいい。

同一符号内でどのような場合に衝突が起きるかに関しては、まだ続く予定である。
とりあえず、シンドローム2倍化計画は頓挫してしまったので、合同式を使ってコリジョン探しをするつもりである。

ここで、ユークリッドアルゴリズムではS,gが固定のとき、対応するu,l,wはただ1つしか存在しないのであった。そしてその場合(l,w)=1なのでl_1=l_2,w_1=w_2である。
つまり衝突しないだろう。

ここでハミング重みが2tの場合に、2つのエラーベクトルに対するシンドロームS_1,S_2が衝突する条件を考えたい。(未解決)
このようなエラーが発生すると、鍵方程式ではどうにもならないのかもしれない。

過剰な場合は、多項式Slが法となる多項式gの次数を超えて、この式の剰余を取るとエラーに対する
情報が消えてしまう。つまりこのままでは、鍵方程式から情報を得ようとするのは無理である。
法をg^2にした場合どうなるかについてやるつもりであるが、そもそも符号がg,g^2でのときに同じであるという意味がよくわからない。
どの本にも生成多項式のべき乗の持つ性質が書かれていない。
バイナリ符号の場合、生成多項式のべき乗で符号を構成すると部分符号になるとか等価な符号になるというのはどういう意味なのー?!

(つづく)

Discussion