🤖

共役元探索問題を使った準同型暗号

2023/08/21に公開

メモ

暗号

共役元探索問題を用いた乗法的準同型暗号

定義：共役元探索問題とは、 $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)$ となる。

追記(20230820)：鍵を合成するときの計算がすでに非可換群のなす準同型写像（内部自己同型写像）であることから、この暗号が準同型暗号になる可能性がある。

以下続き。
今、楕円曲線の点を要素に持つような半直積のことを、楕円半直積と呼ぶ。
楕円半直積の離散対数問題は量子計算機にとって難しくないことが知られている。
しかし共役元探索問題が楕円半直積を使ったとき難しいかどうかはよくわからない。
今楕円半直積の共役元探索問題が難しいものと仮定する。
この暗号方式をESDLP(Elliptic Semidirect Discrete Logarithm Problem)と呼ぶことにする。

性質１：ESDLPは乗法準同型暗号である。
上で見たように、暗号文同士の掛け算が定義できる。つまり、
$c_1=tr(m_1,y,z),c_2=tr(m_2,y,z),c_1c_2=tr(m_1m_2,y,z)$
であり、積に関する準同型写像になっている。つまり暗号化関数

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

より、

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

であることが分かる。
次に平文を指数に持つ暗号化を考える。つまり、

f^{m_1}(y)=xy^{m_1}x^{-1},f^{m_2}(z)=xz^{m_2}x^{-1}

であるので、

f^{m_1m_2}(xy)=xy^{m_1}z^{m_2}x^{-1}

これはあまり面白くないが、

z=y

なら次のように書ける。

f^{m_1m_2}(xy)=xy^{m_1}y^{m_2}x^{-1}=xy^{m_1+m_2}x^{-1}

関数に違いがあるので完全準同型かどうかは分からないが、少なくとも1つの演算に限ってみれば準同型暗号であることが分かる。

更にもう一つ同じような準同型暗号を考える。
定義：原始元を暗号化する。共役元探索問題が難しいと仮定する。
公開鍵： $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$ を得る。
攻撃：鍵から秘密指数を計算できれば解読できる。
ここでは原始元に相当する元を暗号化することでこの攻撃を回避しています。
ｍが小さい場合なら復号できそう。かつ積に関して準同型を満たす。
$m_1,m_2$ を平文とする。この時暗号文は次のように書ける。
$m_1=0,m_2=1$ として $m_0m_1$ を暗号化したい。公開鍵に $D_1=A^aXA^{-a},D_2=A^aYA^{-a}$
を用意する。これはそれぞれ $X=0,Y=1$ を表したいからである。今この２つの鍵でメッセージを表現すると、
$E(m_1m_2)=D^{m_1}D^{m_2}=A^aXYA^{-a},$
よって積に関して準同型暗号であることが分かる。

ここでESDLPに加法を導入する。つまり、 $A=(a,P),B=(b,Q)$ とすると、

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

である。
秘密鍵を

z=(c,R)

とすると、

D_1=zAz^{-1},D_2=zBz^{-1}

である。
これだけでは何も面白くないが、

D_1,D_2

の2つを使って平文バイナリベクトルを

m_1,m_2

としてあらわすと、

c_1+c_2=tr(m_1,D_1,D_2)+tr(m_2,D_1,D_2)=c^{-1}(cm_1c^{-1}+cm_2c^{-1})c=(m_1+m_2)

となり、加法準同型が満たされることが必要である。この分配法則は満たさなければならない。
しかし残念ながら、この代数系は半分配体であり、右側分配法則だけを満たすため、この方式は完全準同型暗号にはならない。計算機の結果も同じである。というのも

cm_1c^{-1}+cm_2c^{-1} \neq c(m_1+m_2)c^{-1}

だからである。よって

(m_1+m_2)c=m_1c+m_2c

のみ成り立つ。なにか別の組み合わせならうまく行くかもしれない。つまり非可換群であっても分配法則を満たすような代数系を使えば完全順同系になる可能性がある。
惜しい・・・

このように積に関しては $c_1c_2 \rightarrow m_1m_2$ が、そして加法に関しては $c_1+c_2 \rightarrow m_1+m_2$ が成り立つような？半直積の内部自己同型を使った準同型暗号の構成を試みた。
席に関しては準同系を満たすが、加法には成り立たなかった。これは半直積に加法を導入した代数系が半分配帯であり、両側にある秘密鍵を取り除けないことに原因がある。よって別の代数系を用いて構成しなければならない。

妥協案：復号時に追加的処理を行う。
$((a,A)+(b,B))(c,C)=(a+b,A+B)(c,C)=(c(a+b),c(A+B)+C)= (ac+bc,c(A+B)+C) \neq ((a,A)(c,C)+(b,B)(c,C))=(ac,cA+C)+(bc,cB+C)=(ac+bc,c(A+B)+2C)$
この式のように足してからかけた元（秘密鍵）と、かけてから足した元とは秘密の点Cを１つ余計に足した分だけ多い。
なので、式の右辺から点Cを引くことで等号を成り立たせることができる。この処理には秘密鍵を知っているものだけが行えばいいので、この追加的処理によって秘密鍵が洩れる心配はない。

共役元探索問題を用いた乗法的準同型暗号

Discussion