20230823：その２に攻撃法が見つかったので修正。
楕円半直積の離散対数問題が解読されました。
すでに実装はしてたんですが、ちょっと驚いてます。
対応策として以下の３つを考えました。
その１：共役元探索問題を用いた公開鍵暗号
定義：共役元探索問題とは、$y,A$が公開されているとき$y=xAx^{-1}$から$x$を求める問題である。
鍵：$y=xAx^{-1},z=xBx^{-1},A,B,y,z$を公開鍵とし、$x$を秘密鍵とする。
暗号化：Sをバイナリ列とし、0をy、1をzと置き換えてSを表した元を$tr(S,y,z)$とする。
この時、$U=tr(S,y,z)=xABAB...x^{-1}$であると同時に$V=tr(S,A,B)=ABAB...$なので、暗号文をC,メッセージをMと置くと、$C=(H(U)*M,V)$である。ここでHはハッシュ関数であるとする。
復号：$U=x^{-1}Vx$とすると$M=H(U)*M/H(U)$となる。
攻撃：xが未知である時、$yx=xA,zx=xB$なので、$y=(p,P),z=(q,Q)$とすると、$(p,P)(x,X)=(x,X)(a,A),(q,Q)(x,X)=(x,X)(b,B)$
$(px,xP+X)=(ax,aX+A),(qx,xQ+X)=(xb,bX+B)$
$px-ax=0 \rightarrow x(p-a)=0 ???$
アフィン群の定義から連立一次方程式が導けるので線形代数攻撃ができるかもしれない。
追記(20230820)：鍵を合成するときの計算がすでに非可換群のなす準同型写像（内部自己同型写像）であることから、この暗号が準同型暗号になる可能性がある。
例えば、別の暗号化法が使えることが分かる。今、乱数をバイナリ表現したものをRと置き、平文をバイナリ表現したものをMと置くと、暗号化は$C_1=xRMx^{-1},C_2=xRx^{-1},C=(C_1,C_2)$というように書くことができる。復号は$C'=(m_1=x^{-1}C_1x=RM,m_2=x^{-1}C_2x=R)$
ゆえに$M=m_2^{-1}m_1$である。これは足すというよりは継ぎ足している感じである。
つまり平文と乱数をかけて結果を得るというところである。これの発展形は後日別記事にしようと思います。
群準同型の勉強をしている間に気が付きました。勉強は大事ｗ
その２：元の分割問題を用いた公開鍵暗号
定義：$y,z$が公開、$n,m,x$が秘密とされているとき、$y=x^mzx^n=x_1zx_2$から$x_1,x_2$を求める問題である。
公開鍵：$y=x^{-n+m}zx^{2n},w=x^{-n+l}zx^{2n},X=a^{-1}zx^{n+m}a,Y=a^{-1}zx^{n+l}a$、が公開鍵、$x,m,l,n,a=x^c$が秘密鍵とする。
暗号化：まず、$s,t$をランダムにとり$$W=a^{-1}y^sw^ta=a^{-1}x^{-n+m}zx^{m+n}...zx^{n+l}zx^{n+l}...zx^{2n}a=x^{m-n}a^{-1}X^{s-1}Y^{t+1}azx^{2n}$$（が、xは分からない）とする。次に乱数$r$をとり、$R=(Y^{-1}X)^r=a^{-1}x^{(m-l)r}a$と置く。更に$$W'=RW=a^{-1}x^{(m-l)r}x^{-n+m}X^{s-1}Y^{t+1}azx^{2n}$$として乱数化する。ここで$Z=x^{(m-l)r}X^{s-1}Y^{t+1}$とする。平文を$M$とし、ハッシュ関数を$H$と置くと、暗号化は$C=(H(Z)*M,W')$である。
復号：$Z=x^{n-m}aWa^{-1}x^{-2n}z^{-1}$である。ここから$H(Z)$を計算し、$M=C/H(Z)$となり平文Mが求まる。
攻撃：共役元探索問題が解けると仮定する。$X=zx^{n+m},y=x^{-n+m}zx^{2n}$の場合$(z^{-1}X)^{-1}y=z^{-1}zx^{-n-m}x^{-n+m}zx^{2n}=x^{-2n}zx^{2n}$となり、共役元探索問題が解ければ解読できる。しかし、$a$があるので攻撃は防げると思う。
その２の代替案（半分配体を使う）
上記の半直積に加法を定義する。つまり$(a,P)(b,Q)=(a+b,P+Q)$である。そこで、
$(c,s)^n=(c^n,\frac{c^{n-1}-1}{c-1}s)$
であるから、公開鍵を$D,E$とすると、
$D=(p,P)^s+(q,Q)^t+(r,R)^u=(p^s,\frac{p^{s-1}-1}{p-1}P)+(q^t,\frac{q^{t-1}-1}{q-1}Q)+(r^u,\frac{r^{u-1}-1}{r-1}R)=(p^s+q^t+r^u,\frac{p^{s-1}-1}{p-1}P+\frac{q^{t-1}-1}{q-1}Q+\frac{r^{u-1}-1}{r-1}R)$
$E=(p,P)^x+(p,P)^s+(q,Q)^t+(r,R)^u+(r,R)^y=(p^x,\frac{p^{x-1}-1}{p-1}P)+(p^s,\frac{p^{s-1}-1}{p-1}P)+(q^t,\frac{q^{t-1}-1}{q-1}Q)+(r^y,\frac{r^{y-1}-1}{r-1}R)+(r^u,\frac{r^{u-1}-1}{r-1}R)=(p^x+p^{s}+q^t+r^{u}+r^y,(\frac{p^{x-1}-1}{p-1}+\frac{p^{s-1}-1}{p-1})P+\frac{q^{t-1}-1}{q-1}Q+(\frac{q^{y-1}-1}{q-1}+\frac{r^{u-1}-1}{r-1})R)$
暗号文：
$C1=A^r+D+C^{r'}=A^{r}+A^s+B^t+C^u+C^{r'}$
$C2=A^{r}+E+C^{r'}=A^r+A^x+A^s+B^t+C^{r'}+C^y+C^u$
復号
アリスは$x,y$を知っているので以下を計算できる。
$X=A^{(x)}+C1+C^{(y)}=A^{s}+A^x+A^r+B^t+C^{r'}+C^y+C^u=C2$
その３：原始元を暗号化し離散対数問題を解く関数を復号関数に持つような暗号方式
定義：原始元を暗号化する。共役元探索問題が難しいと仮定する。
公開鍵：$D=A^aXA^{-a},A$、$E=A^bXA^{-b},A,X^c$、秘密鍵$a,b,c,X$
暗号化１：$C=A^rD^{m_1}E^{m_2}A^{-r}=A^{r+a}X^{m}A^{b-a}X^{m}A^{-b-r},R=A^rX^cA^{-r}$
暗号化２：$S=A^rD^mA^{-r}=A^{r+a}X^mA^{-a-r},T=A^rXA^{-r}$、
復号：$U=A^aTA^{-a}=A^{a+r}XA^{-a-r},S=U^m$より、$S,U$から離散指数$m$を求める方法により平文$m$を得る。
攻撃：鍵から秘密指数を計算できれば解読できる。
追記(20230820)：問題は、$S,T$から$T'=A^{a+r}XA^{-r-a}$もしくは秘密指数$a$を見つけることである。論文にある攻撃法は原始元となるべき任意の元$Z=(m,P)$と、その$n$乗された元$A=Z^n=(x^n,[\frac{m^n-1}{m-n}P])$が与えられればShorのアルゴリズムを使って$[m-1]A+P=[m^n]P$から$m^n$を計算することができ、更にもう一度$m^n$に対してShorのアルゴリズムを繰り返すことで最終的に$n$が計算できるという２段階の処理になります。
復号１：まず、共役元探索問題を解くアルゴリズムがあると仮定する。この時、
$R,X^c$,から$A^r$がわかる。すると、$G=A^{-r}CA^{r}=D^mE^m=A^aX^mA^{b-a}X^mA^{-b}$である。
次に、$A^a,A^b$は既知なので、$H=A^{-a}GA^b=X^mA^{b-a}X^{-m}$
となり、$A^{b-a}$は既知なのでここでも共役元探索問題が解け、$A^m$が求まる。
復号２：$S=U^m,U=A^aTA^{-a}=A^{a+r}XA^{-a-r}$
なので、ここでは原始元に相当する元を暗号化することでこの攻撃を回避しています。なんだか合気道みたいですねｗ
ああでも復号関数にShorを使うなんて効率悪すぎますね。そもそもそれって量子計算機が出てきたらの話だし。あ、でもｍが小さい場合なら復号できそう。しかも積に関して準同型を満たす。
ついに離散対数を求める方法を使うときが来たのよ！とばかりに昔の方式をいじってみたりする。
これをやっていてよく理解できたんですが、やはり暗号の多様性が大事なのだという事。
最初に暗号の多様性をいい出したのはパタリンだと思うけど違うのだろうか？脱！離散対数！
この記事の続きでは、楕円曲線だけでなく、置換群とベクトルの半直積やその他決定不可能な問題を利用した暗号系をやる予定である。