📌

誤り訂正符号の鍵方程式で遊ぶ(パート1)

2025/01/23に公開

符号ベースの暗号技術(符号とか知ってる人向け)

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

この記事では、エラー位置とシンドロームを公開鍵とし、割り算アルゴリズムに使った多項式を秘密鍵にして符号を決定します。エラー位置を公開鍵にすることよって、符号を使った暗号系の鍵サイズを大幅に減らすことができる新型になるかも知れません。(その代わり通信に必要なデータのサイズがすごく増えます)

もしシンドロームとエラーから符号を求めるのが難しければ、これも公開鍵暗号の1つとして成り立つというわけです。

Goppa符号は1970年代に符号長を伸ばしたときの性能が良い代数的符号として考えられた。
符号の元を2進表記にしたものをバイナリ符号というのだが、このバイナリにバラしたものにスクランブル行列と置換行列をかけたものは、符号の構造が隠されて鍵に対する攻撃から守ることができる。

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

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

シンドロームから割り算だけで符号を逆算する

g(x),S(x),l(x),w(x)をそれぞれ、Goppa多項式、シンドローム多項式、エラーロケーター、最大公約多項式であるとする。
いま任意のバイト列をシンドローム多項式S(x)の係数として持つような符号とエラーベクトルを出力することを考える。
この4つの関数の関係式は、

S(x)l(x)+u(x)g(x)=w(x)

と書ける。この式は符号理論で鍵方程式と読ばれています。これは、
S(x)==\frac{w(x)}{l(x)} \pmod{g(x)}

のように書くこともでき、符号の復号でよく見かけます。
l(x)はエラーの位置を指定するための1次式の積であり、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)=S(x)l(x) \pmod {u(x)}
実際1次多項式を因子に持たない(持つと符号が短くなる)多項式の全てはGoppa符号に使えるので、この式も一発で計算できるはずです。

当たり前のようだが、任意のシンドロームに対するエラーベクトルと符号の対を求める方法がこれで実現できるはず。やってみると実に当たり前で、符号の数は沢山ある。
シンドロームとエラー位置だけでは符号多項式が多すぎて1つにさえまとまらない。
あるいは、符号多項式の中でも既約なものだけを許すとか。(これが符号にどのような影響を及ぼすかは理解していない。)
鍵方程式をいじるだけで一生が終わってしまいそう。

鍵空間がdeg(u)=T-1で決まるので、定義体をGF(2^8)とすると、deg(u) \geq 32でなければならないことが分かる。これは普通のマックエリス暗号のパラメータさえあれば十分なので、今回の割り算法で符号多項式が128次以上あっても恐るに足りないものとなりました。(今までは因数分解をしていた)

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

エラーベクトルから1つのシンドロームへの写像の数は、定義体をGF(2^m)とし、エラーのハミング重みをTとすると、2^{m(T-1)}もある。
この中から、f(x)=g(y)=Sとなるような、ハッシュ関数で言うところの衝突が見つけられるのである。
このような衝突(コリジョン)は暗号の世界ではクローと呼ばれている。
ここでは異なる符号をまたいだシンドロームのクローは簡単に見つけられる事が分かった。
もしクローを見つけるのが実際に困難であれば、偽造不可能な電子署名が作れるはずであるが、Goppa符号の場合、このように簡単にクローが見つかってしまうのでクローフリー関数対としては使えないことが分かる。

こんなの何に使えるのかと聞かれると困る。そこで、

この性質を利用して、鍵委託や秘密分散に使えないだろうかと思っている。

普通は意味のないビット列のかわりに、意味のある言葉を使うことができるというのは意外なことに気がついた。つまり同一のシンドロームから異なるエラーベクトルが得られることを利用すれば、u(x)を秘密鍵にして何か出来るのではないかと勝手に期待している。(シンドロームを入力とする多重線形写像?)

参考文献:
[1] A new identification scheme based on syndrome decoding.
https://link.springer.com/content/pdf/10.1007/3-540-48329-2_2.pdf
[2] A Zero-Knowlede Identification Scheme Based on the q-ary Syndrome Decodiong Problem.
https://link.springer.com/content/pdf/10.1007/978-3-642-19574-7_12.pdf

Discussion