楕円半直積の離散対数問題が解読されました。
元ネタをリンクしたかったのですができないようです。
A quantum algorithm for semidirect discrete logarithm problem on elliptic curves
対応策として以下の３つを考えました。
その１：共役元探索問題を用いた公開鍵暗号
定義：共役元探索問題とは、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 ???
アフィン群の定義から連立一次方程式が導けるので線形代数攻撃ができるかもしれない。
その２：元の分割問題を用いた公開鍵暗号
定義：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が求まる。
攻撃：
RW=x^{(m-l)r}y^sw^tから
s,tを計算できれば解読できる。
その３：離散対数問題を解く関数を復号関数に持つような暗号方式
定義：原始元を暗号化する。共役元探索問題が難しいと仮定する。
公開鍵：D=A^aXA^{-a},A,X
暗号化：S=A^rD^mA^{-r},T=A^rXA^{-r}
復号：U=A^aTA^{-a}=A^{a+r}XA^{-a-r},S=U^mより、S,Uから離散指数mを求める方法により平文mを得る。
攻撃：鍵から秘密指数を計算できれば解読できる。
ついに離散指数を求める方法を使うときが来たのよ！とばかりに昔の方式をいじってみたりする。これをやっていてよく理解できたんですが、やはり暗号の多様性が大事なのだという事。脱！離散対数！
特に「その２」が完璧すぎてうっとりする。誰か解読してｗ
Discussion