暗号のプラットフォームというのは要するに代数系の選択と性質に関する研究だとみつけたり。
代数系をやればいいのだ。（暗号理論のための圏論？）
基本に戻ってこの半直積をスカラー（あるいは数ベクトル）の要素を持つ半直積にすれば、半直積の元はデータとして大きさ（ノルム？）を持つことができるので暗号化に使える。今まではパターンであった。スカラー＝データとしても非可換性、加法と乗法の定義は変わりなくできる。半直積の場合、これはアフィン群である。演算を大きな素数の積を法とする演算にすれば多少マシかも？
この方法の売りは自己準同型だから、それを活かしたい。
そもそも完全準同型暗号を作るためには、2つの演算を持つ代数系、つまり環と暗号との関係を調べなければならないはず。。。
このテーマはまだ準同型定理を始めたばかりの自分には無理だ！
その１：共役元探索問題を用いた乗法的準同型暗号
定義：共役元探索問題とは、２つの元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=(C_1=tr(R*M,y,z),C_2=tr(R,y,z))である。ここでRはランダムな半直積の元であるとする。
復号：U=x^{-1}C_1x,R=x^{-1}C_2xとするとM=U/Rとなる。
その２：原始元を暗号化する共役＋離散対数暗号
更にもう一つ同じような準同型暗号を考える。
定義：原始元を暗号化する。共役元探索問題が難しいと仮定する。
公開鍵：D=A^aXA^{-a},A,X、
秘密鍵：a
暗号化：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を得る。
半直積の原画2個だけというのもすべての群の元を生成できないのでもっと増やす必要がある。
その３：加法準同型暗号の構成実験（準同型の確認）
・強度は関係ないです。
例えば、xmx^{-1}のmを文書にすることで準同型秘密鍵暗号ができるかも？
アフィン暗号に対する選択平分攻撃を行う。暗号文をCとする。
C_1=(c,R)(r_1,M_1)(c^{-1},-c^{-1}R)=(cr_1,r_1R+M_1)(c^{-1},-c^{-1}R)=
(r_1,c^{-1}(r_1R+M_1)-c^{-1}R)
C_2=(c,R)(r_2,M_2)(c^{-1},-c^{-1}R)=(cr_2,r_2R+M_2)(c^{-1},-c^{-1}R)=
(r_2,c^{-1}(r_2R+M_2)-c^{-1}R)
C_1-C_2=(r_1-r_2,c^{-1}((r_1-r_2)R+M_1-M_2))
秘密鍵のc,Rはgcdを使えば求められるかもしれないがよくわからない。
これはAが公開されている公開鍵方式に当てはまるので、ベクトルを使った共役元探索問題はまるで使えない。（大きな素数の積を法とする演算なら強くなるかも？Rが楕円曲線の点であればこれも一味違う。代数系と計算問題との関係を調べたサーベイが必要）
ベクトルの半直積に加法を定義する。つまり(a,m_1)(b,m_2)=(ab,bm_1+m_2),(a,m_1)+(b,m_2)=(a+b,m_1+m_2)である。
そこで、(c,m)^n=(c^n,\frac{c^{n-1}-1}{c-1}m)。
手始めにスカラーの半直積に積と加法を定義する。
ここで、a,b \in randomであり、P,Q \in Z_pであるとする。
今、妥協案を受け入れることにして、この疑似加法的準同型暗号を使ってデータを暗号化と復号する方法を考える。
A=(r_1,P),B=(r_2,Q),x=(c,R),x^{-1}=(c^{-1},-c^{-1}R),r_1,r_2 \in random, P,Q \in M
ここでMはメッセージ空間である。
積に対する結合法則より、
・(a,A)(b,B)(c,C)=(ab,bA+B)(c,C)=(abc,c(bA+B)+C)=(abc,bcA+cB+C)
・(c,R)(r_1,P)(c^{-1},-c^{-1}R)=(cr_1,r_1R+P)(c^{-1},-c^{-1}R)=(r_1,c^{-1}(r_1R+P)-c^{-1}R)
・暗号化してから足す
F_1=xAx^{-1}+xBx^{-1}=(r_1,c^{-1}(r_1R+P)-c^{-1}R)+(r_2,c^{-1}(r_2R+Q)-c^{-1}R)
=(r_1+r_2, c^{-1}((r_1+r_2)R+P+Q)-2c^{-1}R)
・足してから暗号化する
F_2=x(A+B)x^{-1}=x(r_1+r_2,P+Q)x^{-1}=(c,R)(r_1+r_2,P+Q)(c^{-1},-c^{-1}R)=
(c(r_1+r_2),(r_1+r_2)R+P+Q)(c^{-1},-c^{-1}R)=
(r_1+r_2,c^{-1}((r_1+r_2)R+P+Q)-c^{-1}R)
よって、F_2=F_1+(0,c^{-1}R)が成り立つ。
・暗号化してから足した元を復元する
G_1=x^{-1}F_1x=x^{-1}(xAx^{-1}+xBx^{-1})x=
x^{-1}(r_1,c^{-1}(r_1R+P)-c^{-1}R)x+x^{-1}(r_2,c^{-1}(r_2R+Q)-c^{-1}R)x=
(c^{-1},-c^{-1}R)(r_1+r_2, c^{-1}((r_1+r_2)R+P+Q)-2c^{-1}R)(c,R)=
(c^{-1}(r_1+r_2),-c^{-1}(r_1+r_2)R+c^{-1}((r_1+r_2)R+P+Q)-2c^{-1}R)(c,R)
=(r_1+r_2,P+Q-R)
・足してから暗号化した元を復元する
G_2=x^{-1}F_2x=(-c^{-1},-c^{-1}R)(r_1+r_2,c^{-1}((r_1+r_2)R+P+Q)-c^{-1}R)(c,R)=
(-c^{-1}(r_1+r_2),-c^{-1}(r_1+r_2)R+c^{-1}((r_1+r_2)R+P+Q)-c^{-1}R)(c,R)=
(r_1+r_2,-(r_1+r_2)R+((r_1+r_2)R+P+Q)-R+R)
=(r_1+r_2,P+Q)(秘密鍵の要素は全部消える)
よって、G_2=G_1+(0,R)が成り立つ。（F_2が正しい暗号文,G_2正しい元データ）
平文が先に足されてから暗号化されたのかどうかの区別をする必要がある。
（・暗号化してから足す）
F_1=xAx^{-1}+xBx^{-1}=(r_1,c^{-1}(r_1R+P)-c^{-1}R)+(r_2,c^{-1}(r_2R+Q)-c^{-1}R)
=(r_1+r_2, c^{-1}((r_1+r_2)R+P+Q)-2c^{-1}R)
のP,Q,Rが全部スカラーになるので平文をデータとして暗号化できる。
これは因数分解でもないし、何になるんだろう？
もう少し勉強します。
Discussion