注意

残念ながらブレイド群にも攻撃法が見つかったようで、共役元探索問題を実現できるような材料が見つかってない状態だそうです。プロでも見つけられない。

まずアリスは$a,y,x \in S_n$、とし、$x,y$は公開します。
ボブは秘密鍵$a' \in S_n$を選ぶものとします。
$a \in S_n$これはアリスの秘密鍵です。
そして、$A=axa^{-1},B=aya^{-1}$をアリスの公開鍵として公開します。
更にボブも$b \in S_n$としてボブの秘密鍵として保持します。
ボブの公開鍵は、$C=bxb'^{-1},D=byb ^{-1}$です。

ここで例として${(0,1)}^n$のパターンを想像してみてください。
パターンは何でも良いですが、パターンは秘密にしないとだめです。
ここではアリスの秘密パターンは"0101"であるとしましょう。
一方、ボブのパターンは"1111"であるとしましょう。
アリスは今０にボブの公開している鍵$bXb^{-1}$を、１に$bYb^{-1}$を対応付けることを考えます。
すると、パターン0101に相当する鍵は、$A2=bXYXYb^{-1}$になりますよね？
今は相手の公開鍵から取りましたが、今度は自分の鍵からも取りましょう。
すなわち、$A1=aXYXYa^{-1}$です。ボブも同じようにやります。
ボブのパターンは"1111"だったので、次のようになります
$B2=bXXXXb^{-1}，B1=aXXXXa^{-1}$
と、このようにしてできたパターンを、アリスとボブは公開します。
そしていよいよ鍵共有です、
アリスは自分の公開鍵にラベルを付けてA1,A2,B1,B2とします。
そしてこの１，２の意味はそれぞれ1の場合は自分の公開鍵から、2の場合は相手の（ボブにとってはアリスの）公開鍵から作って同一パターンの公開鍵であることを意味します。
そこでアリスはボブが公開した１のついた公開パターンを合体させます。なぜなら、同じパターンをそれぞれ違う鍵から作っているからです。
こうして混合させたものは、結局同じ鍵を生成できることになります。
ボブも同様に１と２のラベルがついた鍵をかけ合わせ、アリスと同じ鍵を得ます。
パターン１の方も公開してあるので、相手と同じパターンを作れます。
つまりアリスの秘密鍵を使っているパターン１の場合、A1B1と連結できます。
A1とB1の両脇にはアリスボブの秘密鍵がそれぞれ次のように入っています。
A1=a0101a^{-1}
A2=c0101c^{-1}
B1=a1111a ^{-1}
B2=c1111c^{-1}

４つの要素がある場合、交換子群の形にすれば共有できるらしいですがまだ理解できてません。
$A1B1A2B2=(B2A2B1A1)^{-1}?$

これで2者間の鍵交換は終了です。
または、もっと確実な方法はX,Yの２つだけの場合です。
この場合はきれいに決まります。
A1B1=a01011111a
A2B2=c01011111c
となり、最後に持ち帰った鍵の両側から自分の秘密鍵を取り除いてあげれば、立派に鍵共有できますね。
デモの個場合は共役源探索問題をベースに作られたものですが、置換群ではできないのでブレイド軍でしましょう。
いずれも秘密鍵を持っている鍵公開者にしかできなことなので、盗聴していても最終的にどのような鍵を共有したのかわかりません。（と思うｗ）

よく確認してみてください。
送信者と受信者の鍵が非対称であること以外は一致しているはずです。

あえて言うなら、この鍵交換はビットパターンを共有しているのだということです。

しかし本当にやりたいことは、置換群を使ってのことなので、置換群と多項式、多項式とベクトルなどいろんな群が使える半直積なんかを調べて、可能性を探っていきたいです。

置換群を有効活用しているのは、むしろPKPとかなのでさっさとそっちに行ったほうが良いかもしれないｗ

具体例

ブレイドでも行列でもない非可換な、半直積を鍵交換に使ってみましょう。
まず楕円曲線は問題から外します。
なぜなら楕円曲線はもともと鍵交換をするために使われている問題なので、車輪の再発明になります。
そこでここでは、半直積にしかできない合体技をやってみます。
つまり、多項式とスカラーを合体させた半直積で構成します。

まずシステムパラメータです。
半直積の元A,Bを２つ用意します。
ボブの秘密鍵は$X,X^{-1}$です。
アリスの秘密鍵は$Y,Y^{-1}$です。
ここでX,Aは秘密の半直積の元です。
ここで暗号に使うのは、今までも出てきた共役元探索問題です。
$X,A,B \in (K[x],Z_p)$
$X=(f,a),A=(g,b),Y=(h,c),B=(i,d)$
とします。
もう一度おさらいします。
共役元探索問題とは、非可換群の元A,Xがあり$Z=XAX^{-1}$があったとき、ZとAからXを計算する問題です。
$X=(f,a)$とすると$X^{-1}=(-a^{-1}f,a^{-1})$
$Z_{a1}=XAX^{-1}=(f,a)(g,b)(-a^{-1}f,a^{-1})=(ag+f,ab)(-a^{-1}f,a^{-1})=(-bf+f+ag,b)$
$Z_{a2}=XBX^{-1}=(f,a)(i,d)(-a^{-1}f,a^{-1})=(ai+f,ad)(-a^{-1}f,a^{-1})=(-df+ai+f,d)$
とするような演算です。ボブも同様に$Z_{b1}=YAY^{-1},Z_{b2}=YBY^{-1}$を作る。

※次のような多項式の代入版も可能なようです。(20230509:追記)
$(f,a)(f,a)^{-1}=(f,a)(-a^{-1}f,a^{-1})=(f(x)-f(x),aa^{-1})=(0,1)$
$(a,f)(a,f)^{-1}=(a,f)(-af^{-1}(a),f^{-1})=(a-a(f(a)f^{-1}(a)),ff^{-1})=(0,1)$
$(a,f)(b,g)(a,f)^{-1}=(f(b)+a,fg)(-af^{-1},f^{-1})=(fg(-af^{-1})+f(b)+a,g)=(-ag(a)+f(b)+a,g)$

本題に入ります。

ボブの公開鍵は$B_1=XAX^{-1},B_2=XBX^{-1}$
ボブの秘密鍵；X,ビットパターンS

同様に、アリスの公開鍵は$A_1=YAY^-1,A_2=YBY^-1$
秘密鍵はYとアリスのビット列Tとする。

鍵交換：ボブは自分のビットパターンS=1010に従って、公開鍵を次のように構成して公開する。
$XB_1X^{-1}=0,XB_2X^{-1}=1$
ビットパターンはS=1010なので公開鍵は
$B_{a}=XB_2B_1B_2B_1X^{-1}=X1010X^{-1}$
$B_{b}=YA_2A_1A_2A_1Y^{-1}=Y1010Y^{-1}$
同様にアリスのビットパターンをT=0101とすると、公開鍵は
$A_{a}=YA_1A_2A_1A_2Y^{-1}=Y0101Y^{-1}$
$A_{b}=XB_1B_2B_1B_2X^{-1}=X0101X^{-1}$
で、今やろうとしているのはAAG風の交換子を使った鍵交換です。
ボブが鍵交換をしたいとき、アリスの公開している$A_1$と$A_2$を自分のビットパターンに合わせて選びます。

そしてボブの公開鍵に左右から$A_{a},A_{b}$をかけて共有鍵を作ります。
$B_{key}=A_{a}^{-1}B_{b}^{-1}A_{b}B_{a}$
とします。

アリスは逆にB'を作ったら、自分の公開鍵Aに対してボブの公開鍵Bを
$A_{key}=B_{a}^{-1}A_{b}^{-1}B_{b}A_{a}$

すると、
$A_{key}=(Y^{-1}1010Y) * (Y^{-1}0101Y) * (X0101X^{-1}) * (X1010X^{-1})= \
Y^{-1}10100101Y*X01011010X^{-1}=B_{key}$

となり、鍵共有ができたことになります。
この時ボブはアリスの秘密鍵Y,T、アリスはボブの秘密鍵X,Sを知りません。

これで離散対数では使えなかった、半直積の鍵交換が使えるようになればいいと思いますがまだ確認してません。これは設計のロードマップです。AAGというプロトコルのマネをしてみましたが、私のほうがラベルを選んでつなげるだけなのと、相手の鍵で自分と同じパターンを暗号化するところがわかりやすくなっていると思います。

おまけ

数ベクトル$A,B$と多項式ベクトル$f,g$の半直積を考える。（もう寝るｗ）
$(A,f)(B,g)=(f(B)+A,fg),a=(A,f),x=(B,g)$
$(C,f')(D,g'),(C,f')^{-1}=(-f'^{-1}(C),f'^{-1}),b=(C,f'),y=(D,g')$
$A1=axa^{-1},A2=aya^{-1}$（公開鍵$A1,A2$、秘密鍵$a$）
$B1=bxb^{-1},B2=byb^{-1}$（公開鍵$B1,B2$、秘密鍵$b$）
共通パラメータ：$x,y$

この因数分解は難しいのだろうか？
例えば、この半直積の材料で共役源探索問題を難しくできるだろうか？
確か置換群は任意の元で１つの置換を表現できるらしいし、もしそうなら別の方法でirreducibleな置換群を見つけてこないといけない。しかもそれが難しいかどうかもわかっていない。
勉強不足！

$X=(\pi,A),Y=(\phi,B)$
とした時、Xの逆元は$X^{-1}=(\pi,A,)(\pi^{-1},-\pi(A)^{-1})=(\pi\pi^{-1},\pi(A)^{-1}-\pi(A)^{-1})=(e,0)$である。

半直積使って難しい問題を作るのが夢なんですがどうでしょうねえｗ
とりあえず既約多項式の方はもう少し考えてみようと思う。

以下の方法ではブレイド群以外でも鍵交換をすることができます。

ブレイド群を用いた鍵交換

注意

具体例

おまけ