非可換群として半分配環を使う鍵交換

（とは言え行列以外の非可換軍って少ないのよね・・・。）
つまりこういうことです。
問題：Near-Ring Decomposition Problem (NDP)

ここでは行列を除いた一般の非可換群に対する鍵交換プロトコルを紹介します。
この問題は、私が離散対数でもなく共役元探索問題でもない、非可換群を用いた鍵交換で初めて経験した方法です。
世の中非可換群を使ったプロトコルなんて山のようにあるけど、本当は可換になる部分群を使ってたりしてがっかりすることが多いのですが、そんな偽物ではなく本当に非可換な元同士を組み合わせて鍵交換をしようというのが動機です。
行列を使った暗号は色々攻撃法があって危険かもしれませんが、そのときは半直積にしてお好きな群を非可換にしてみるのも手だと思います。
ちなみに置換群は行列なので解読できる可能性が高いです。
今度記事を書くときには、多項式とスカラー、そしてその多項式への代入値との半直積を作って、その可能性を調べたいと思います。
今まで置換群で共役元探索問題をやろうとして線形代数攻撃に悩まされてきたのですが、今度こそその攻撃を交わすことができればいいと思います。
ちなみに行列の３分割問題への攻撃法は先程思いつきましたので、整数行列は絶対に使わないでください。
多変数多項式を要素に持つベクトルと、整数ベクトルの半直積などをやってみたいです。
例えば、１変数多項式をｎ=1本持つベクトルと、ｎ=1個の整数を持つベクトルとの半直積を考える。nは簡単に一般化できます。
ベクトルを$v,x$、多項式を$f,g$とすると$(v,f)(x,g)=(f(x)+v,f+g)$（ここで$Z/mZ$は整数環,$I(x)$は多項式の法となる既約多項式）のような演算を定義します。

Decomposition Problem

Problem 2.(Decomposition Problem)とは、
ある$v = x_1ax_2$と$a$ が与えられた時、$ , x_1 ∈ H, a ∈ A, x_2 ∈ H'.$
（要するに$x_1,x_2$が冪等元でないこと）
を満たすような$x_1,x_2$を求める問題です。

ここでは3分割のうち真ん中の1つが公開されている条件の問題です。
見た感じ行列を使った暗号によく使われるようです。
ちょっと線形代数攻撃を試してみましょう。
今$a$が公開されていて$x_1,x_2$が秘密であり、
$v=x_1ax_2$
であったとしましょう。そのとき、未知の元$x_2$の逆元を右からかけると、
$vx_2^{-1}=x_1a$
この条件をみたすような$x_1,x_2^{-1}$を計算する問題がこの暗号の強度になります。
更にここで$a$が公開されており、
$w=x_1bx_2$
とｂが公開されているとしましょう。すると未知変数は同じで、方程式の数だけ2倍になるので、この8個の式から未知の行列$x_1,x_2$の未知の変数はすべて解読できることになります。
少なくとも非可換群でも整数を元とする行列を作ってはならないというのはこれが理由です。
もちろん連立方程式が組めないような特殊な行列（楕円曲線の点を要素に持つなど）なら安全でしょう。

共役元探索問題とどう違うのか？

共役源の場合は、$Z=XAX^{-1}$の真ん中の元Aが公開されているところは同じですが、両脇にある元Xが互いにXの逆元であることが特徴です。
そのため片側からXの逆元を乗算することで未知変数を減らすことができます。
しかし3分割問題では、3つとも違う元なので未知変数を減らすことができません。
ここで言われている方法では、秘密の元は違いますが真ん中にある弦が同じでしかも真ん中に公開されている元が2種類存在するので、せっかく増やした変数が多項式まで増えてしまいTDP問題の効果がなくなってしまう、つまり共役元探索問題と同じ状況になてしまうのです。
もし、行列以外の共役源を使えば、以前の記事にある共役元探索問題を使った鍵交換がうまくいくかもしれません。その時は今取り組んでいるこの方式から式の数を減らして、それでも成り立つような暗号系を再設計しなければならず、そのときこそオリジナルな方法になるであろうと思われます。

多項式とスカラーによる例

次に、1変数多項式と、1個のスカラーとの半直積を考える。

もう一度おさらいします。
Decomposition Problemとは、非可換群の元A,X,Yがあり$Z=XAY$があったとき、Z,AからX、Yを計算する問題です。
今使っているのは多項式と有限体の元の対であるような元の半直積です。
$a,b,c \in Z_p,f,g,h \in K[x]/(I)$（ここで$I$は$K[x]$の法となる既約多項式）
$X=(f,a),Y=(g,b),Z=(h,c)$とすると、
$W=XYZ=(ag+f,ab)(h,c)=(abh+ag+f,abc)$
とするような演算です。この時、WとYからX,Zを計算できるかという問題です。
線形代数のときにはうまくいきましたが、この半直積ではどうでしょうか？
現在この半直積を使った攻撃法を研究中で、結果が分かり次第他のコンテンツで公表したいと思います。

半直積の気持ち

半直積の基本演算を定義すると、
$(c,s)(d,t)=(cd,sd+t)$：積
$(c,s)^{-1}=(c^{-1},-sc^{-1})$：逆元
$(c,s)^{-1}(d,t)(c,s)=(d,s(e-d)+tc)$：共役元
となる。
$(f,a)^{-1}(g,b)(f,a)=(g,a(1-g)+bf)$
※こういう事もできそうです。
$(a,f)(b,g)(a,f)^{-1}=(f(b)+a,fg)(-af^{-1}(a),f^{-1})=(f(b)+a-ag(a),g)$：代入値でも矛盾なく定義できそうな悪寒。

$(f,a)(f,a)^{-1}=(f(x),x)(-x^{-1}f(x),x^{-1})=(f(a)-f(a),aa^{-1})=(0,1)$
$(a,f)(a,f)^{-1}=(x,f(x))(-xf^{-1}(x),f^{-1}(x))=(a-a(f(a)f^{-1}(a)),ff^{-1})=(0,1)$：逆元も定義できる。
ただ単に多項式にスカラーをかけるだけなんてつまらないと思ったのでやってみました。
今度はこれを使ってブレイド群の代わりに多項式と代入地のペアで暗号を作ってみます。（20230509：追記）

半直積の例

任意の群の半直積を構成し、その非可換性を確かめます。
$2,4,5,6 \in Z$
であるとします。この時、
$(2,4)(5,6)=(10, 4 \times 5+6 )=(10,26)$
$(5,6)(2,4)=(10, 6 \times 2+4 )=(10,16)$
となり、非可換であることが確認できました。
ちなみに要素の右半分は計算結果が直接的すぎて、解読の危険背を増すことが多いので左側の要素だけを暗号化に使うという方式もあります。今回の提案でもその方法が適応できないか考えてみます。

秘密鍵の選択

アリスは次のように非可換群の元を取ります。
例えば素体からできた半直積の元の集合$Z_p^2$にします。
アリスは6個の異なる元を取ります。
$a,b,c,d,x,y \in (Z_p,K[x])$
ボブも同様に４個の元を取ります。
アリスはそのうち$x,y \in (Z_p,K[x])$だけを公開し、アリスとボブとの間で共有します。
公開する鍵はボブが決めても問題ありません。
つまりボブの秘密鍵は、
$e,f,g,h' \in (Z_p,K[x])$
の４つだけです。

鍵設定

アリスは次のようにして公開鍵を作ります。まず、
$d^{-1}a=h'^{-1}e=\phi$
であるように決めます。
これは後で述べるビットパターンの分離記号としての役割を果たす元です。

$A1=(a_1=axb^{-1},a_2=bxc^{-1},a_3=cxd^{-1})$
$A2=(b_1=ayb^{-1},b_2=byc^{-1},b_3=cyd^{-1})$
$B1=(c_1=exf^{-1},c_2=fxg^{-1},c_3=gxh'^{-1})$
$B2=(d_1=eyf^{-1},c_2=fyg^{-1},c_3=gyh'^{-1})$

$A1,A2$はアリスの公開鍵、$B1,B2$がボブの公開鍵、$a,b,c,d$がアリスの秘密鍵、$e,f,g,h'$がボブの秘密鍵です。
$x,y$は共通パラメーターです。

ビットパターンと鍵共有

（ややこしいのでじっくり読みましょうｗ）

ここで1つ制約条件をつけます。
それはアリスとボブの秘密のバイナリ列の長さが偶数であるという仮定です。
その仮定のもとにこの鍵交換は成り立ちます。
ビットパターンを
$h=(0,0),i=(0,1),j=(1,0),k=(1,1)$とします。
長さ2のバイナリ列にはこの4パターンしかないので、これだけ定義できれば十分です。

この時、各2ビット列が、アリストボブの間でどのように組み合わせられるのか見ていきます。
まず、パターンhのとき、アリスの鍵の組み合わせは、
$h=a_1a_2a_3=ax^3d^{-1}$と決めます。
同様にパターンiの場合は、
$i=a_1b_2a_3=axyxd^{-1}$
$j=b_1a_2b_3=ayxyd^{-1}$
$k=b_1b_2b_3=ay^3d^{-1}$

追記：20230605

まだあります。
$a_1a_2b_3=ax^2yd^{-1}$
$b_1b_2a_3=ay^2xd^{-1}$
$a_1b_2b_3=axy^2d^{-1}$
$b_1a_2a_3=ayx^2d^{-1}$

上記にあるように、$a,b,c,d,x,y$はすべて半直積の元なので、$x,y$の順序の違いは計算に反映されます。なので実際には8パターンのGF(8)に対応するような計算結果が得られることになります。で、これでどうなるかはまだ考えてませんｗ

となるように決めます。
同様にボブも、
$h1=c_1c_2c_3=ex^3h'^{-1}$と決めます。
同様にパターンiの場合は、
$i1=c_1d_2c_3=exyxh'^{-1}$
$j1=c_2d_2c_3=eyxyh'^{-1}$
$k1=d_1d_2d_3=ey^3h'^{-1}$

これは行ってしまえば、０と１を2つの元の対応関係で表現しているということです。
3つの異なる元を組み合わせると同時に、ビット列を共有したいという要求を実現できます。
このようにパターンごとに値を決めてしまえば、4つの変換テーブルを持つだけで、ビットストリングを共有できたことになりなります。
ここで$d^{-1}a=h^{-1}e=\phi$と決めた事を思い出してください。
あとはパターン通りに鍵の組み合わせを並べるだけです。

アリスのビットパターンが1010のときは、
$K_{a_1}=jj=b_1a_2b_3b_1a_2b_3=ayxy\phi yxyd^{-1}$
$K_{a_2}=j1j1=d_1c_2d_3d_1c_2d_3=eyxy\phi yxyh'^{-1}$
1111の場合は、
$K_{b_1}=kk=b_1b_2b_3b_1b_2b_3=ay^3\phi y^3d^{-1}$
$K_{b_2}=k1k1=ey^3\phi y^3h'^{-1}$

$K_{alice}=K_{a_1}K_{b_1}=ayxy\phi yxy^4\phi y^3d^{-1}$
$K_{bob}=K_{a_2}K_{b_2}=eyxy\phi yxy^4\phi y^3h'^{-1}$

であり、鍵に割り当てられた番号同士をつなぎ合わせて、$K_{alice},K_{bob}$からそれぞれアリスとボブの秘密鍵を取り除けば鍵共有は出来上がりです。
これは非可換でなければならないという要請に答えるための鍵共有ができる元の分割問題(decomposition problem)を利用したものとなると思います。（不安）

ここで問題が。
$\phi$が公開されることで、特定の位置に$\phi$があることがわかるというのはどの程度問題になるだろうか？
かと言って1にしてしまうと3つのパーツを全部揃えれば線形代数攻撃に弱くなるし、何かいい方法があるかもう少し考えます。
あともう一つ。共有鍵で得られた鍵は左半分を使うようにします。
公開鍵は下記計算に右う要素も使うため、右要素は公開したくありませんが、公開しなくてもいい方法を模索しています。特に素体上の元が素数と法として3つに因数分解されるかもしれないのでその場合も素体は使えないことになります。

成功したら大発見です。

半分配環のDecomposition Problemに基づく鍵交換