ハイミー

一般化置換行列を使った半直積

https://ja.wikipedia.org/wiki/一般化置換行列

これは何

いろいろな公開鍵暗号がある中で、なるべくシンプルな理論に基づく公開鍵暗号を作りたい。例えば線形写像のカーネルを用いたものとして、シャミアのPKP（Permuted Kernel Problem）を使った電子署名や、置換による有限生成ベクトルの部分和問題などを視野に入れている。

https://eprint.iacr.org/2018/714

これはまず、一般化置換群が通常の置換とベクトルの半直積として表せることから、その元は第二要素が複数ベクトルとなる入れ子構造を持っている。
今まで色々半直積の例を作ってきたが、何故かこのシンプルな代数系だけやらなかったので今回やることになる。
なお、この研究はまだ途中である。
何もないところから任意のシステムと言語を使って外部依存なしに１０分くらいで作れる安全な暗号を作ることを目指します。
ベクトルと置換しか用いずに難しい計算問題を構成します。

置換とベクトルからなる暗号系

例１

$\pi,\phi,\xi$を一般化置換行列とし、$r,v,w \in Z_p^n$（対角行列）とする。

$x=(\pi,v)$を秘密鍵、$u=(\xi,r),y=(\phi,w),z=x^{-1}yx,t=x^{-1}ux$を公開鍵とする。

ここで半直積の演算を次のように決める。
$(\pi,v)(\phi,w)=(\pi\phi,w_{\pi}+v)$
$x^{-1}=(\pi,v)^{-1}=(\pi^{-1},-v_{\pi^{-1}})$

すると公開鍵$z$は以下のように書ける。
$z=x^{-1}yx=(\pi^{-1},-v_{\pi^{-1}})(\phi,w)(\pi,v)=(\pi^{-1}\phi,w_{\pi^{-1}}-v_{\pi^{-1}})(\pi,v)$
$=(\pi^{-1}\phi\pi,v_{\pi^{-1}\phi}+w_{\pi^{-1}}-v_{\pi^{-1}})=(\phi,v_{\pi^{-1}\phi}+w_{\pi^{-1}}-v_{\pi^{-1}})$
$w=v_{\pi^{-1}\phi}+w_{\pi^{-1}}-v_{\pi^{-1}}$と置くと、

$$z^k=(\phi^k,w_{\phi^k}+w_{\phi^{k-1}}+...+w_{\phi}+w)$$

$y$あるいは$z$から$x$を計算する問題を、共役元探索問題と呼ぶ。
これは難しい問題になると思われる。
整数と楕円曲線の点を使った半直積の離散対数問題は解かれることが知られている。
置換群とベクトルの半直積から構成された離散対数も解かれる事が容易にわかるが、共役源探索問題は、公開鍵から秘密鍵の情報が完全に失われるので難しいと思われる。
ここで２つの異なるベクトルと置換の半直積を使って、暗号化を行う。

$t=x^{-1}ux,z=x^{-1}yx$を半直積の２つの元とする。
バイナリ列$s$の$0$に相当する元に$z$を、$1$に対応する元を$t$と置き、積として表すと$0101=ztzt=x^{-1}uyuyx$となる。
暗号化は、

$$c=(m+H(yuyu),ztzt)$$

となる。
受診者は$x$を知っているので、$c$の第２成分に両側から$x,x^{-1}$を掛け、$yuyu$を復元してハッシュ関数$m=H(yuyu)-c$を計算して平文$m$を得る。

例２

例えば、次のようにしてベクトルと置換を用いた部分和問題を構成する。これは半直積ではなく、置換とベクトルの２つの代数を使った代数系になる。これは、$a,b \in Z_p^n,x,y \in S_n$のベクトルを係数に持つ置換群の群環$Z_p^n[S_n]$である。この代数系の演算を次にように定義する。
和：

$$a_{\pi}+b_{\pi}=(a+b)_{\pi}$$

積：

$$a_{\pi}b_{\pi}=ab{\pi^2}$$

$$a,b,c \in Z_p^n, \pi,\phi \in S_n$$

であるとする。例えば、他変数多項式の変数に当たる部分が置換でその係数がベクトルであり、ベクトルには置換が作用している。
この結果全てのベクトルの和が定義できる。また、掛け算は異なる変数ごとに足し合わせることができる。
$f(x)=x^2+x+e=\pi^2+\pi+e$と、多項式と同一視できる。
多項式の係数はベクトルである。$\pi$は一般化置換行列なので、係数ベクトルは対角行列として表すことができるが、一般化置換行列同士の足し算はできない。
今、ベクトル$a,b,c$が公開されている時、

$$a=b_{\pi}+c_{\phi}$$

となるような、置換$\pi,\phi$を求める問題である。例えば、同一ベクトル$a$に対して、群環の元を$a_{\pi^{-1}}$とした時、$0=a_{\pi}+a$であるような置換$\pi$を求める計算問題が難しい問題ならば暗号に使えることになる。
ベクトルが２つの場合は総当りが簡単なので、$n=256,k=32$くらいのパラメータをおすすめしたい。
つまり、

$$k=32,a=b_{0,\pi_0}+b_{1,\pi_1}+...+b_{i,\pi_i}+...+b_{k-2,\pi_{k-2}}+b_{k-1,\pi_{k-1}}$$

詳細は秘密である。（各自考えよ）
ちなみに、置換軍を用いた所属問題は簡単な問題らしいので、この場合も有限生成ベクトルの所属問題は簡単であると予想する。

公開鍵に対する攻撃

$$t=x^{-1}ux,z=x^{-1}yx$$

この両辺に未知の元を$x'$としてかけると、

$$x't=ux', x'z=yx'$$

となる。$x'$の第一成分は一般化置換行列であり、連立方程式で計算できるかも知れない。
そこで$x$の第一成分がが分かったとした場合、第２成分が計算できるか試す。
$z=(\phi,v_{\pi^{-1}\phi}+w_{\pi^{-1}}-v_{\pi^{-1}})$
であり、$v$は秘密ベクトル、$w$は公開ベクトルである。
また$\pi,\phi$は分かっているものとする。
すると、$z$の第２成分は、
$z=(\phi,v_{\pi^{-1}\phi}+w_{\pi^{-1}}-v_{\pi^{-1}})$
より、$a=v_{\pi^{-1}\phi}+w_{\pi^{-1}}-v_{\pi^{-1}}$としたとき、
$b=a-w_{\pi^{-1}}=v_{\pi^{-1}\phi}-v_{\pi^{-1}}$
$b_{\pi}=v_{\phi}-v$
これは$b,\pi,\phi$から$v$を求める問題になり、これが解かれれば秘密鍵は全部復元できたことになる。
従って未知ベクトル$v$を$\phi$を使って総当たり攻撃をかける問題に還元できると思われる。
暗号の強度はベクトル空間の大きさに比例する。
つまり実質的な秘密鍵は、ベクトル$v$のみとなる。
従って、秘密の元の第２成分であるベクトルがわからないので、第１成分がわかっても平文は得られないと思われる。
従って複数の（３２くらい）ベクトルを秘密鍵に使いのが良いはずである。
暗号文として通信路に流す情報は第二要素だけである。

総当たり攻撃の回避策

これは暗号文$c$に置いて、第二成分だけしか送信しないという方法で回避できると思われる。
つまり、離散対数を経由する方法が取られる。
暗号化関数に、未知の指数$e_0,e_1$と置き、

$s=v_{\pi^{-1}\phi}+y_{\pi^{-1}}-v_{\pi^{-1}}$
$t=v_{\pi^{-1}\xi}+u_{\pi^{-1}}-v_{\pi^{-1}}$

とすると、

$$c=t^{e_0}=x^{-1}s^{e_0}x=(\pi^{-1},-v\pi^{-1})(\phi^{e_0},s_{\phi^{e_0}}+s_{\phi^{e_0-1}}+...+s_{\phi}+s)(\pi,v)$$

$$c''=z^{e_1}=x^{-1}y^{e_1}x$$

のように暗号化する。そして$c',c''$をそれぞれ$0$及び$1$に対応させ、暗号文を$d=0101=c'c''c'c''$とし、$d$の第２成分だけを送信する。
あとは$x,x^{-1}$を$d$の両側から掛けてやり$\pi,\phi$は分かっているものとして計算できる。
すると未知の指数が邪魔をして、離散対数問題ではなくなる。
つまり、$d$の第１成分は、

$$(\pi^{-1}\phi^{e_0}\xi^{e_1}\phi^{e_0}\xi^{e_1}...\pi,$$

となるので離散対数問題を回避することができる。
ちなみに置換群の離散対数問題は容易に解読できる。

総当り解読に対する防御

今までの例はベクトルが2つの場合だった。
総当りの場合ベクトルの数が2であれば、ベクトルの次元$n$のときは、２つのベクトルの要素に対して、高々$n \times n$回試せば解読可能である。
そこで同じ長さのベクトルを32個にすることでさらなる強度に引き上げることが可能である。
つまり、

$$w_i \in Z_p^n, \pi_i \in S_n i=k, v_i=(\pi_i,w_i),$$

　

$$u_{(i,j)}=v_{0,\pi_0}v_{1,\pi_1}...v_{k-1,\pi_{k-1}}$$

$$=(\pi_0\pi_1\pi_2...\pi_{k-1},v_{(k-1,w_ow_1...w_{k-1})}+v_{(k-2,w_0w_1...w_{k-2})}+...+v_{(1,w_0)}+v_{0,e})$$

このように置換の数を増やせばこの暗号系の解読をより困難にすることができる。（加法だとどうなるか）
しかしこの場合も、使われているベクトルが全て同じである場合に弱くなるならば、$k=32$個の異なる置換を使うようにしなければならない。（単一ベクトルバージョンと複数ベクトルバージョンの違いについては考察中）
つまり半直積の第2要素に対して、複数のベクトルを使うような場合である。

一方、共役元探索問題は行列を使うと線形代数攻撃によくなるという弱点がある。
線形代数攻撃に強くするため、多変数多項式などを使う必要があるがまだそれは試していない。

この代数系を多変数多項式の係数に使うとどうなるか？

この暗号系の安全性評価

調査中

最後のニュース

まだなにか欠陥があるかも知れないですが、ベクトルと置換だけで安全な暗号ができるとしたら、とても実装が簡単な暗号系になるかも知れません。

https://github.com/anang0g0/PKP-Based_blind_signature