結果だけ読みたい人は最終回に飛んでください。
https://qiita.com/fumumue/items/57c1c0fa6707f09216bf
今からやることは完全な暗号を作ることではなく、私の頭の中にある暗号学的バブルを解体してゆく作業である。
Key Words: ECDLP, Elliptic Curve Cryptosysytem, semi direct product, Group Algebra, Triple decomposition problem, noncommutative group, semigroup decomposition problem
２種類の$n*n$次の正方行列を考える。
20200205追記：
「
https://arxiv.org/pdf/1210.8114.pdf
こんなこともあるので安心できない。
以下は私のに近いアプローチ。
Exploring platform (semi)groups for non-commutative keyexchange protocols
Ha Lam
Graduate Center, City University of New York
くそー先駆者がいたか！ｗ
http://shpilrain.ccny.cuny.edu/semidirect.pdf
半直積の離散対数が新しくないのであれば、半直積の３分割問題なら新型かもしれない。
」
20220207:追記
「
攻撃法：https://eprint.iacr.org/2021/644.pdf
でも、楕円バージョンなら安全かもしれない。
」
１つは行列$A,B$は有限体の元が入る行列。
そしてもう一つの行列$X$は楕円曲線上の点を要素に持つ行列。
さらに行列Zを以下のように構成し、Xとともに公開する。
$Z=AXB$、$X$
このようにした場合、$(Z、X)$から$A,B$を計算するのは簡単だろうか？
これを３要素分解問題(Triple Decomposition Problem)という。
具体例を示そう。$G$を楕円曲線の任意の点として１つ固定する。
この時２×２の行列を、
P=
\begin{pmatrix}
1 & 2 \\
3 & 4
\end{pmatrix}
Q=
\begin{pmatrix}
G & G \\
G & G
\end{pmatrix}
R=
\begin{pmatrix}
5 & 6 \\
7 & 8
\end{pmatrix}
とすると、3つの行列の積$S=PQR$は
S=
\begin{pmatrix}
3G & 9G \\
7G & 10G
\end{pmatrix}
mod 11
となる。
これがスカラー行列と楕円の行列演算だ。
20220213追記：
「
多くの非可換群や半直積を使った暗号が、線形代数を使った攻撃に弱いのは行列が線形独立だかららしい。
楕円の点を使った行列がこの攻撃にかからないのは、楕円の点がそれ自身を足したり引いたりするだけですべての点が求まるからで、つまり線形従属だから攻撃できないのだ。
問題は両側にあるスカラー行列を計算できるかどうかだ。
」
暗号で使うためには、行列QとSから両側のスカラー行列$P,R$を計算するのが難しいかどうかが決め手になる。
これを普通の連立方程式を解くように、両側の行列の値を未知の係数に持つ連立方程式として扱おうとすると、変数に相当する楕円曲線の点をどう処理するかが問題になる。
サンプル https://gist.github.com/anang0g0/bb38ced239b6edfa014b99a17348e9c4
20220202：追記
「
20220203；離散対数を使わないバージョン変更につき削除。
」
もしこれが簡単な場合は次を考える。
楕円曲線の点群と、有限体との半直積を考える。
https://ja.wikipedia.org/wiki/%E5%8D%8A%E7%9B%B4%E7%A9%8D
この場合の半直積とは楕円曲線の点群と、有限体上の乗法群の２つの群の要素$(P,Q) \in E_p$（楕円）、$(c,d) \in GF(p)$（有限体）があったとき、この２種類の異なる要素のペアに対する演算 $*$を $(P,c)*(Q,d)=(dP+Q,cd)$と定義したものである。
また半直積の逆元は$(-Pd^{-1}-Q,c^{-1}d^{-1})$である。
更にこの半直積は$(P,c)(Q,d)(R,e)=((dP+Q,cd)(R,e)=(e(dP+Q),cde)$となる。
ちなみに$(Q,d)*(P,c)=(cQ+P,cd)$なので、半直積は非可換となる。
行列では２種類の演算が必要だが、積を$*$としたとき、２つの元$(P,c)+(Q,d)$の間の$+$に代わるものは2つとも加法を持つので$(P+Q,c+d)$でよいだろう。
なんでこんなことをするのかというと、楕円曲線の点は掛け算ができないから、半直積$$を導入することで、楕円曲線の点を要素の一部に持つ２つの行列$AX*B$の計算をできるようにするためである。
加法に対する離散対数も構成できるだろうか？
今整数nを決めた時、Pを法とする楕円曲線上の点Qのn倍点
$n(Q,d)=(nQ,nd)$
をただ1つ決めることになるが、その場合ndのnは法となる素数と公開されている値とdにより一意に決まる。これはあまり面白くないのでボツ。
このとき楕円曲線の点xと有限体の元yの対を元に持つような２つのn次元の正方行列$U,V$を用いた$W=UVW$の分解元探索問題は難しくなるだろうか？
これは暗号において楕円曲線を離散対数問題以外で使う試みである。
このような仮定の下で非可換群である行列を使う暗号は構成可能か？と思い、調べています。
最初は同種写像をやろうかと思っていたのですが、こちらのほうが簡単そうだという感じで遊びになります。
追記：20220119 半直積を使った場合の離散対数問題について
追記：20220202
「
ケーリーハミルトン云々の場合は全く見当違いなので削除。
」
半直積はもともと新しい群を作るために考えられたらしいのだが、ここで新しいものが何も発見できなければ何もなかったのと同じになる。
20220202：追記
「
半直積バージョンの場合も離散対数として扱う場合ほとんど意味がないことがわかった。
なんと夢の中に出てきてわかったのだ。
というのも、右成分は明らかに普通の離散対数問題であり、左成分も楕円曲線の離散対数問題と全く同じである。
つまり離散対数問題として扱う場合全く新しいものがない。
ECDLPと右側要素の離散対数問題のどちらか弱いほうで強度が決まるので、右側要素をそれなりに大きくしなければならない。
右側要素を大きくしても、楕円曲線の演算サイズは影響を受けない。
また新しい問題として扱うためには、離散対数以外の問題に還元されなければならない。（保留）
」
行列の離散対数の場合、以下のリンクで解読法がわかる。
続く
https://qiita.com/fumumue/items/4313ffa768b67315c587
参考文献：
https://arxiv.org/pdf/1504.05040.pdf
https://eprint.iacr.org/2012/694.pdf