🐙

エラー入り公開鍵を使ったNiederreiter暗号

に公開

バイナリGoppa符号の検査行列をSによるスクランブルとPによる置換を行い、w=wt(e)>2tこの行をビット反転させる。この行列を公開鍵H_eとする。

暗号化は通常のNiederreiter暗号と同じく、s=mH_eとする。
復号は次のようにする。
s_e=eH_eとすれば、Decode.(S^{-1}s+s_e)=mである。
ここでs_eは秘密鍵である。

w個の行をビット反転させて符号の代数的構造を崩すことでリードソロモン符号などを使って暗号化できるのではないか、という効果を期待しているのだが、どうだろうか?
バイナリ行列なので、平文の位置と反転の位置が一致する行の個数が偶数であればs_e=0であり、奇数個の場合はs_{e_i}=e_iHとなると考えられる。
iは平文と反転させた位置が一致した最後の1行である。
反転した行がエラーと重なった場合、その位置は検出されないが、その場合のエラーの個数はw-1になるので、これをw個のエラーになるまで試せば良い。
したがって復号は2回試せば十分である。

本当はHQCのNiederreiterバージョンをやりたかったのだが、それを作るためには過剰なエラーを正確にすべて消す必要があり、その時初めて平文が得られることになる。(他に方法があるかも知れないが)

Discussion