その２：元の分割問題を用いた公開鍵暗号

１はアイデアだし、行列の場合何だか解読できそうなので引っ込めました。

基礎となる問題：u=x^mvx^n=x_1vx_2,vを公開鍵とした時、u,vからx_1,x_2を求める問題である。

秘密鍵：
e,f,n,m,l,a \in Z,x \in Gが秘密鍵とする。Gは非可換群とする。
公開鍵：

y=x^{-n+m}z^ex^{2n},　w=x^{-n+l}z^fx^{2n},　X=x^{-a}z^ex^{n+m}x^a,　Y=x^{-a}z^fx^{n+l}x^a

、
が公開鍵であるとする。

暗号化：まず、s,tをランダムにとり

W=y^sw^t=x^{-n+m}zx^{m+n}...zx^{n+l}zx^{n+l}...zx^{2n}=x^{m-n}x^aX^{s-1}Y^{t+1}x^{-a}zx^{2n}

（が、xは分からない）とする。
暗号化は鍵y^sw^tを使うものとする。
次に乱数rをとり、

R=(yw^{-1})^r=x^{(m-l)r}

と置く。更に

W'=RW=x^{(m-l)r}x^{-n+m}x^aX^{s-1}Y^{t+1}x^{-a}zx^{2n}

として乱数化する。
ここで

Z=x^{(m-l)r}X^{s-1}Y^{t+1}=RX^{s-1}Y^{t+1}

とする。つまり、

W'=x^{-n+m}x^aZx^{-a}zx^{2n}

である。
平文をMとし、ハッシュ関数をHと置くと、暗号化は

C=(H(Ry^sw^t) \oplus M,Z)=(C_0,C_1)

である。
復号：

W'=x^{n-m}x^aC_1x^{-2n}x^{-a}z^{-1}

である。ここからH(W')を計算し、M=C_0 \oplus H(W')となり平文Mが求まる。
攻撃：共役元探索問題が解けると仮定する。X=x^{-a}zx^{n+m}x^a,y=x^{-a}x^{-n+m}zx^{2n}x^aの場合

(z^{-1}X)^{-1}y=z^{-1}zx^{-n-m}x^{-n+m}zx^{2n}=x^{-2n}zx^{2n}

となり、共役元探索問題が解ければx^{2n}がわかる。しかし、xが未知のためnの計算ができない。
ごちゃごちゃ書いてしまいましたが、これが一番危ういです。

追試

このままではStickelの鍵交換と呼ばれる方式と同じ弱点があるので、この2つの行列のべき乗にハッシュ関数をかけた値を平文に対してXORして暗号文とする。
つまり、y^sw^tをそのまま送ってはならないということである。

(z^{-1}X)^{-1}y=z^{-1}zx^{-n-m}x^{-n+m}zx^{2n}=x^{-2n}zx^{2n}

に対してケーリーハミルトン攻撃をかける。
A=x^{-2n}zx^{2n}
x^{2n}A=zx^{2n}
(ex+fI)A=z(ex+fI)

よって、４本の式に対して６個の未知変数が存在するので、式の数が足りない。

ケーリーハミルトンの定理より公開鍵への攻撃

公開鍵：

y=x^{-2n+m}zx^{3n},　w=x^{-n+l}zx^{2n},　X=x^{-2a}zx^{n+m}x^{3a},　Y=x^{-a}zx^{n+l}x^a

、
が公開鍵であるとする。

ケーリーハミルトンの定理より、
y=(ax+bI)z(cx+dI)
w=(ex+fI)z(gx+hI)
(ix+kI)X=z(kx+lI)(mx+nI)
(ox+pI)Y=z(qx+rI)(sx+tI)
よって、未知変数は１６本の式に対して、
a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,x_0,x_1,x_2,x_3
の２４個である。更に、
wy^{-1}=x^{-n+l}zx^{2n}x^{-2n}z^{-1}x^{n-m}=x^{l-m}
となり、
Y^{-1}a^{-1}aX=x^{-n-l}z^{-1}zx^{n+m}
であるから、

Y^{-1}X=x^{m-l}

最終的にz,aが消える。さらに、
wy^{-1}=x^{l-m}
Y^{-1}X=x^{m-l}
から、wy^{-1}=XY^{-1}となり、全部消えてしまい、肝心の秘密鍵である指数などの値が計算できない。
つまるところ、これは攻撃すると消える暗号？なのかもしれないがちょっと考えます。

暗号文をケーリーハミルトンで解読する

W'をケーリーハミルトンで変形すると、
W'=RX^{s-1}Y^{t+1}=x^{(m-l)r}X^{s-1}Y^{t+1}=(ax+bI)(cX+dI)(eY+fI)
となる。この時未知定数は、
x_0,x_1,x_2,x_3,a,b,c,d,e,f,a_0,a_1,a_2,a_3
の１０個であり、方程式の数は４つなので解読できそうにない。

結論

ケーリーハミルトン攻撃に対抗できる行列を使った公開鍵暗号を作ったのだろうか？
この暗号は、公開鍵にケーリーハミルトン攻撃をかけると必要な秘密鍵が全部消えてしまう。
そんなにうまい話はそうないので、後日数値例で確認する。
他にもっと有効な解読法がないか考える。

xも何もかも秘密にすれば解読できないかもしれないが、それでは計算困難な問題だとが言えず、単に鍵が決定不可能になるだけである。（つまり秘密主義）
これを計算理論に基づいた暗号にするためには何が必要なのか？