共通鍵型準同型暗号メモ

準同型暗号の目的

準同型暗号の目的が、暗号化したまま検索できるようにすることだとしたら、それは公開鍵暗号だけでなく秘密鍵暗号にも当てはまるメリットではないだろうか？
半直積を使うという事は、可換群から非可換群を作るという目的があった。
ここでは更に非可換群を用いて暗号化したまま検索できるような、準同型秘密鍵暗号を作ろうという話をする。

半直積の基本演算を定義する

1.$(c,s)(d,t)=(cd,sd+t)$：積
2.$(c,s)^{-1}=(c^{-1},-sc^{-1})$：逆元
3.$(c,s)^{-1}(d,t)(c,s)=(d,s(e-d)+tc)$：共役元
4.$(c,s)^n=(c^n,c^{n-1}s+c^{n-2}s+...+cs+s)$：べき乗公式

ここで$n$項等比数列の総和が$S_n=\frac{(c^n-1)}{c-1}$から、

1'.$(c,s)^n=(c^n,\frac{c^{n-1}-1}{c-1}s)$
2'.$(c,s)^{nm}=(c^n,\frac{c^{n-1}-1}{c-1}s)^{m}=(c^{n},s')^m=(c^{nm},\frac{c^{m-1}-1}{c-1}s')$
3'.$(c,s)^{m+n}=(c^{m+n},c^m\frac{c^{n-1}-1}{c-1}s+\frac{c^{m-1}-1}{c-1}s)$

3'なんか割と面白い形してませんか？

加法準同型暗号の構成実験（公開鍵暗号の様な何か）

原始元を暗号化する。共役元探索問題が難しいと仮定した場合の暗号系・・・@
公開鍵：$D=A^aXA^{-a},A,X,X=(r_1,M),A=(r_2,R)$、ここでXは秘密鍵ベクトル、Aを平文ベクトルとする。
秘密鍵：$a,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$を得る。
攻撃：鍵から秘密指数を計算できれば解読できる。

ここでは原始元に相当する元を暗号化することでこの攻撃を回避しています。
即ち、$S=A^{r+a}X^mA^{-a-r}$なので、公開鍵から暗号文を直接計算することができない。またランダム化された鍵$T=A^rXA^{-r}$からこの暗号系の原始元の役割を果たす$A^{r+a}XA^{-a-r}$を計算しなければならないが、これは公開鍵$D$が、乱数$r$によってランダム化されたものであるため秘密鍵$a$がわからなければ$T$から原始元を復元できない。この時、指数に数値などのデータを保持することができる。
ｍが小さい場合なら復号表を使うことで復号できそう。

いま話題のCKKSという謎の公開鍵暗号（私が知らないだけです）があるらしく、そこでは多項式の係数をベクトルと考え、その安全性を解読が難しい数学的な問題に還元させるような暗号化方式もあり、これは調べなければならない。ベクトルを使うところと線形写像の核を使うというところで工夫がされているようですが、これはまた別の暗号化方式であるPermutated Kernel Problemという昔から知られている問題に似ているので今後の改良案に取り入れていきたい。例えばベクトル空間を構成してマックエリス暗号のような誤り訂正を使うのではなく、写像の核を容易に推定できないようにするためのトラップドアとして使うという方法を取ることができるかもしれない。いずれにしてもこういう出てきたばかりの暗号の使用は注意深くなければならない。このベクトル空間の構成にGoppaでもワイルドでも色々な角度から検証してみるつもりです。（Vandermondeだと1種類しかない）

共通鍵型準同型暗号

@ の構成は半直積に対し、固定秘密鍵$K$と可変秘密鍵$a$を適用して準同型暗号を考えようとしたものでした。なぜ秘密パラメータが2つ必要があるのかといえば、共役元探索問題と離散対数問題を合体させたいからです。効果があるかどうかはこれから検証します。これを両脇から公開鍵のべき乗をかけることで　@ の構成を踏襲します。

$y=(r_1,M_1),z=(r_2,M_2),x=(c,K),x^{-1}=(c^{-1},-c^{-1}K)$
ここで、$M_1,M_2$は平文ベクトル、$K$は鍵ベクトル、$c,r_1,r_2$は乱数ベクトルとする。計算は任意の素数を法とする四則演算であるとする。
秘密鍵：$a,x$
暗号化：$C=x^ayx^{-a}$：$r_1$を使い捨ての初期値とした場合は、置換群との組み合わせることで疑似乱数は得られるが、3つ組にしなければならないので新たにラウンド鍵を生成する仕組みを考えなければならない。もしくは、$C^i=x^{i+a}yx^{-a-i}$とすることで再帰的な暗号化が可能かもしれない。

共役類を考える場合、（解読されるかもしれないが）暗号文同士の掛け算が定義できる。つまり、暗号化関数

$$f(y)=xyx^{-1},f(z)=xzx^{-1}$$

より、

$$f(y)f(z)=f(yz)=xyzx^{-1}$$

であることが分かる。次に平文を指数に持つ暗号化を考える。ここで、
$f^{m_1}(y_1)=xy_1^{m_1}x^{-1},f^{m_2}(y_2)=xy_2^{m_2}x^{-1}$であるので、$f^{m_1m_2}(xy)=xy_1^{m_1}y_2^{m_2}x^{-1}$これはあまり面白くないが、$y_2=y_1$なら次のように書ける。
$f^{m_1m_2}(xy)=xy_1^{m_1}y_1^{m_2}x^{-1}=xy_1^{m_1+m_2}x^{-1}$
関数に違いがあるので完全準同型かどうかは分からないが、少なくとも1つの演算に限ってみれば準同型暗号であることが分かる。
加法に関しても同じような性質を持つ。

今、復号時に秘密鍵を足すという変更を受けれれば、この加法的準同型暗号を使って秘密鍵暗号として使う事ができるかもしれない。（公開鍵暗号化はもう少し考えなければならない）
ここで、暗号文に対する加法を導入する。
暗号文に対する加法とは、$A=(x,P),B=(y,Q)$とすると、

$$A+B=(x+y,P+Q)$$

となることである。

積に対する結合法則より、
$(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)$
$r_1=0$のとき、
$(c,R)(r_1,P)(c^{-1},-c^{-1}R)=(0,c^{-1}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)$(秘密鍵の要素は全部消える)

ここで$r_1+r_2$は乱数であり定数なので、別途保管しておけば暗号文が増大することを防ぐことができる。

xを暗号化の秘密鍵とすると、P,Qがn次元のベクトルとして表された平文であるから、これを上記の通りに暗号化することで秘密鍵暗号の暗号文同士を足したり掛けたりできるようになる。
ベクトルを要素として持つ半直積は楕円半直積や置換群の時には出来なかったデータの暗号化という用途に使える暗号化である。（が、強度は怪しい）
さらに両脇からxのべき乗をかけることで、公開鍵暗号としても使えるようになるかもしれない。
楕円半直積の単独の離散対数問題には量子計算機で解読できる効率的な方法が存在するらしいが、秘密鍵で両側から平文を挟んだり、両側から乱数べきを持つ元をかけて原始元を暗号化したりすることで、計算すべき指数が複数になる場合には指数を表す単独の式としては存在しないので、離散対数問題とは言えない気がする。（例えば$c^mc^n=c^{m+n}$が分かっていたとして、$c^m\frac{c^{n-1}-1}{c-1}+\frac{c^{m-1}-1}{c-1}$を計算することができるだろうか？）
平文を上記の方式で暗号化する時に、乱数ベクトルを一緒に掛けることでECBモードのブロック暗号を乱数化すると同時に暗号文同士の加算と掛け算を同時に実現できると思うがまだやっていない。
ブロック暗号の場合、限られた長さの鍵からいかに推測されにくい鍵すストリームを生成するかが問題なので、公開鍵暗号とは違った安全性の評価が必要になり、このような安易な暗号では簡単に破られてしまうことが推測できる。
Bounded Strage Modelを使ってなんとかできないものか考えている。

$f_u^{m_um_u}(e)$