行列を用いた公開鍵暗号（CAB方式の暗号）の脆弱性

著書「16歳のセアラが挑んだ世界最強の暗号」で有名な「セアラの暗号」は，非可換行列と，行列の累乗を用いたものですが，脆弱性がありました。原論文は次のものです。
http://cryptome.org/flannery-cp.htm
セアラの暗号では，2行2列の行列χとχⁿが交換可能であることを用いていますが，ケイリー・ハミルトンの定理により χⁿ＝aχ ＋bＩと表され，これにより離散対数問題が単純化されるからです。
その脆弱性については，セアラ自身が原論文の中で解説していますが，私なりに次の様に解釈しました。
Sarah.pdf

「解読不能は数学的に証明済み」と主張した「CAB方式の暗号」も，公開鍵暗号部分に，非可換行列と，行列の累乗を用いています。その特許は，次のように公報されています。
http://jstore.jst.go.jp/nationalPatentDetail.html?pat_id=31280
この特許公報で，「数学的には解を得る確率は０となる」と主張していますが，この主張の論拠には重大な誤謬があることが数学的に証明できます。
また，CAB方式の暗号の非可換部分が無意味であり，CAB方式の暗号が行列を用いた用いたElgamal暗号(Diffie-Hellman)と同等であることを，ケイリー・ハミルトンの定理を用いて示すことができます。
CAB.pdf

次の暗号は，セアラの暗号を変形したものです。

受信者の初期設定

R＝X^r ，B＝RAR^-1 （rは乱数）
を計算する。ただし，AとXは非可換であるとする。
r，Rを秘匿し，Ａ，B，Ｘを公開する。

送信者の作業

S＝X^s ，Ｃ＝SAS^-1，Ｋ＝SBS^-1 （sは乱数）
を計算する。
ここで，RとSは交換可能であるから
Ｋ＝SBS^-1＝S(RAR^-1)S^-1＝R(SAS^-1)R^-1＝RCR^-1
Ｋを鍵として，共通鍵暗号でメッセージＭを暗号化してＭ’を得る。
s，Sを秘匿し， CとM’を受信者に送信する。

復号処理

RCR^-1=K （この計算は，積を2回しか用いないので極めて高速である）
を計算し，Ｋを鍵としてＭ’を共通鍵暗号で復号してMを得る。

暗号強度

暗号の強度の根拠は，セアラの暗号と同じで，Ａ，B，ＸからRを求める困難性である。

この暗号に離散対数問題を絡ませると，CAB方式の暗号になります。

上記の暗号において，R^-1，S^-1はそれぞれＴ＝X^t，Ｕ＝X^u （ｔ，uは乱数）に置き換えることができます。
さらに，公開鍵としてAと非可換なＹを加え，R^-1，S^-1をそれぞれＴ＝Ｙ^t，Ｕ＝Ｙ^u に置き換えることもできます。
このような拡張により，セアラの暗号の暗号強度が増すことが期待されますが，行列による非可換群ではケイリー・ハミルトンの定理により解読されてしまいます。
また，このように拡張しても，復号処理が極めて高速であるというセアラの暗号の特徴は損なわれません。

さらに，一般化すると，次のようになります。

非可換群Ｇの可換部分群をH₁，H₂とする。

受信者の初期設定

a∊Ｇ，r₁∊Ｈ₁，r₂∊Ｈ₂を選び，
b＝r₁ar₂
を計算する。ただし，aとr₁は非可換，aとr₂は非可換であるとする。
r₁，r₂を秘匿し，G，H₁，H₂，a，bを公開する

送信者の作業

s₁∊Ｈ₁，s₂∊Ｈ₂を選び，
ｃ＝s₁as₂，k＝s₁bs₂
を計算する。
ここで，r₁とs₁は交換可能であり，r₂とs₂は交換可能であるから
k＝s₁bs₂＝k＝s₁(r₁ar₂)s₂＝r₁(s₁as₂)r₂＝r₁cr₂
kを鍵として，共通鍵暗号でメッセージMを暗号化してＭ’を得る。
s₁，s₂を秘匿し，cとM’を受信者に送信する。

復号処理

r₁cr₂=k （この計算は，積を2回しか用いないので極めて高速である）
を計算し，kを鍵としてＭ’を共通鍵暗号で復号してMを得る。

暗号強度

暗号の強度の根拠は，a，bからb＝r₁ar₂を満たすr₁，r₂を求める困難性である。

課題

位数が十分大きい可換部分群 H₁，H₂ が見つかるか。
H₁，H₂が循環群の場合，s₁∊Ｈ₁，s₂∊Ｈ₂を選ぶのに，生成元の累乗を計算しなければならないのか，それとも，ケーリー・ハミルトンの定理のような定理により，累乗を計算しなくても選べるのか。
ケーリー・ハミルトンの定理により行列による暗号が解読されたように，群の性質により簡単に解読されないか。

群を行列で表現すればケーリー・ハミルトンの定理により解読できるため，暗号として成り立つ群は存在しないと思われます。

行列を用 いた公開鍵暗号（CAB方式の暗号）の脆弱性

行列を用いた公開鍵暗号（CAB方式の暗号）の脆弱性