📘

半分配環を使った幾つかの公開鍵暗号：その１

2023/07/29に公開

ポエム

概要

この記事は3部に分かれている。第1は半分配環の説明と多元離散対数問題を定義し、簡単な例を構成する。第2部では楕円曲線と有限体を組み合わせた半分配体の例を上げ、具体的に多元離散対数と、それを用いた鍵交換の例を挙げる。第3部では多項式と整数からなる代数系に整数環上の減法を適用した分割問題を定義し、それに基づく鍵共有方式を考案した。

０．目標

まず加法及び乗法に関する算法を定義する。ここで、ある算法を持つ代数系を作り、この代数系が半分配環、或いは半分配体になることを確認し、この代数系での多元離散対数問題を定義したい。
しかしこれは暗号系の基盤となる群に、加法が存在する場合のみという制約があり一般には成り立たない。
幸いにも多項式と有限体、または有限体と楕円曲線は加法に関して群になるので、いかに述べるような算法から半分配体を構成できるはずである。
楕円曲線と有限体、または多項式と有限体を使って半直積から半分配体を作り、更にその多元離散対数問題を構成したい。

1.代数系

$a,b,c$ を素体の元、 $A,B,C$ を楕円曲線上の点とする。
この集合に次のような算法を定義する。
$A=(a,A),B=(b,B)$
$AB=(ab,bA+B)$
$A^{-1}=(a^{-1},-a^{-1}A)$
$AA^{-1}=(a,A)(a^{-1},-a^{-1}A)$
もしくは、
$AB=(a,A)(b,B)=(a+b,bA+B)$
$A^{-1}=(-a,aA)$
$AA^{-1}=(a,A)(-a,aA)=(0,0)$
とする。
これを楕円曲線の代わりに、式のスカラー倍、もしくは式の値に対しても同様なことができる。

この算法は形式的に積の形をとっているので、加法が定義されていない。
そこで加法を次にように定義する。
$(a,A)+(b,B)=(a+b,A+B)$
普通に直和です。
以下ではこのような代数系が環であるかどうか確かめる。

環の条件

１）加法に関して結合律を満たす。
結合律）
$((a,A)+(b,B))+(c,C)=(a+b,A+B)+(c,C)=(a+b+c,A+B+C)$
$(a,A)+((b,B)+(c,C))=(a,A)+(b+c,B+C)=(a+b+c,A+B+C)$
よって成り立つ。
零元の存在）
$(a,A)+(0,O)=(0,O)+(a,A)=(a,A)$
よって存在する。
逆元の存在）
$(a,A)^{-1}=(-a,-A)+(a,A)=(a,A)+(-a,-A)=(0,O)$
となり、存在する。
可換律）
$(a,A)+(b,B)=(b,B)+(a,A)=(a+b,A+B)$
よって成り立つ。（可換性は必ずしも必要としない）
全て成り立つので、この演算は加法群である。

以下、環の条件を確かめる。
２）積に関する結合則を満足する
$(a,A)(b,B)(c,C)=(ab,bA+B)(c,C)=(abc,c(bA+B)+C)=(abc,bcA+cB+C)$
$(a,A)(bc,cB+C)=(abc,bcA+cB+C)$
よって満足する。
次に、
$(a,A)(b,B)(c,C)=(a+b,bA+B)(c,C)=(a+b+c,c(bA+B)+C)=(a+b+c,bcA+cB+C)$
$(a,A)(b+c,cB+C)=(a+b+c,(b+c)A+cB+C)=(a+b+c,bA+cA+cB+C)$
これは結合法則を満たさないので、半分配環の条件を満たさない。
このような代数系のことを擬群と呼ぶが暗号には使えそうにないので保留する。

３）乗法に関して逆元が存在する
逆元が存在して、それは $(a,A)^{-1}=(a^{-1},-a^{-1}A)$ なので、 $(a,A)(a^{-1},-a^{-1}A)=(1,O)$
単位元は $(1,O)$ である。
４）分配律を満足する
$(a,A)((b,B)+(c,C))=(a,A)(b+c,B+C)=(a(b+c),(b+c)A+B+C)=(ab+ac,(b+c)A+B+C)=((a,A)(b,B)+(a,A)(c,C))=(ab,bA+B)+(ac,cA+C)=(ab+ac,(b+c)A+B+C)$
足してから積を計算するのと、積を計算してから足した結果が一致するので、左分配法則が成り立つ。
$((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)$
なので右分配法則が成り立たない数学からの物体X。積が特殊だからかも。
つまり環ではない！

積に対しては結合則を満たしているので半群ではある。
さらに０でない元に逆元が存在するのでモノイドになる。
ここで上のような分配法則が片側からしか成り立たない代数系を半分配環と言うらしい！
正確には、半分配体というのは逆元の存在を前提としているので、逆元が存在しない場合は少し緩い条件を持つ半分配環になる。

2.半分配体の実験的構成

上で見たように、楕円曲線や有限体上の多項式には逆元が存在する。
0以外の全ての要素に逆元が存在するとき、この代数系を半分配体と呼ぶ。

有限体と多項式の半分配環にスカラー倍を導入する

$p,q,r \in Z_p$ の異なる原始元。
$f,g,h \in F[x]$ 　は有限体上の多項式（楕円曲線の場合は足し算の場合のみ）
半直積の元を、
$A=(p,f),B=(q,g),C=(r,h)$
とする。

この代数系の基本演算を定義すると、
$(c,s)(d,t)=(cd,sd+t)$ ：積
$(c,s)^{-1}=(c^{-1},-sc^{-1})$ ：逆元
$(c,s)^{-1}(d,t)(c,s)=(d,s(e-d)+tc)$ ：共役元
$(c,s)^n=(c^n,c^{n-1}s+c^{n-2}s+...+cs+s)$ ：べき乗公式
となる。

更に、代数系の元同士の積を次のようにすると、
$AB=(p,f)(q,g)=(pq,bf+g)$
$BA=(q,g)(p,f)=(pq,ag+f)$
この場合は非可換となる。
これは演算に積と加法を混ぜた場合である。
さらに、半直積の演算に乗法のみを使うと、
$AB=(p,f)(q,g)=(pq,qfg)$
$BA=(q,g)(p,f)=(pq,qgf)$
となり、可換になる。

また、代数系の元同士に代入した式の値を見ると、
$AB=(f,p)(g,q)=(fg,g(p)+q)$
$BA=(g,q)(f,p)=(gf,f(q)+p)$
この場合は非可換となる。
最後に、式の値に乗法のみを使うと、
$AB=(f,p)(g,q)=(fg,g(p)q)$
$BA=(g,q)(f,p)=(gf,f(q)p)$
この場合も非可換となる。
これは演算に積と加法を混ぜた場合である。

定義：多元離散対数問題

手短に説明します。
多項式と有限体に上で半直積と呼んでいた算法を使って多元離散対数問題を構成する。
今、以下の条件

y_i=\Pi^n_{i=0}g_i^{x_i}

を満たすような

(y_i,g_i)

が公開されているとする。互いに独立した

i

個の半直積の元

g_i

と、

i

個の秘密指数

x_i

があった時、

y_i

から秘密指数の組

(x_i:0 \leq i \leq n)

を求める問題を、半直積の多元離散対数問題と呼ぶことにする。
ここで算法は乗法群である。
これは真数のベクトルに対して秘密の指数ベクトルを計算するような問題です。
さらにこの問題は離散対数問題を拡張したものである。
最初にこの問題が出てきたのは楕円曲線暗号のペアリング関数を使ったBLS署名だという事をChatGPTが言っていた。
そして普通の有限体で、更に半直積を使った例は有名ではないという事も聞いた。
お好みの群を混ぜるだけで非可換群を作ることができる。

有限体と多項式から構成された半直積の元の右要素には法となる既約多項式は必要としない。
20230727:ここで扱う多項式は多変数多項式を扱う。またこの代数系の多項式はべき乗の影響を受けずに離散対数問題を構成できる。
というのもこの算法における逆元は以下のように定義されているからである。

A=(a,f),a \in Z_p,f \in F[x] \rightarrow A^{-1}=(a^{-1},-a^{-1}f)

AA^{-1}=(a,f)(a^{-1},-a^{-1}f)=(1,0)

非可換群において、原始元が１つの場合は普通の離散対数問題であるが、非可換群の特殊性が現れるのは２つ以上の原始元を使った離散対数問題である。これを多元離散対数問題という。
例えば、有限体上に定義された行列環の元を $A,B$ とし、この $A,B$ を用いた２元離散対数問題を例に挙げると、

A^nB^m \neq B^mA^n

という俄には信じがたいことが起きるが、これは非可換群ならではのことで非可換群の多元離散対数問題には左右の区別が必要になるようだ。
行列を用いた離散対数問題はStickelの鍵交換として知られている。（しかし破られる）
非可換群を暗号に用いるための暗号化関数は存在するが、暗号に使えるような具体的な群が見つかっていないというのが問題である。

以下では、加法と乗法の混合を使った場合の離散対数問題ついて述べる。

$x,y,z$ を楕円曲線の点と有限体の半直積の元とする。
$y=z^{-1}xz$ であるようなzを求める問題である。
パターンが対称的であることから２つの共役を使うと以下のようなことができる。
$u=z^{-1}vz$
と定義すれば、
$uyuy=z^{-1}vxvxz$
となることが分かる。
さらに、共役源の構造は対称的なので、離散対数も作ることができる。それは、
$y^n=z^{-1}x^nz$
となることである。
これら２つを組み合わせれば次のようなパターンも表現できる。
$uy^nu^my=z^{-1}vx^nv^mxz$
このようなパターンはDecomposition Problemではできない。（鍵の構造が非対称なので）
なのでこの問題は２つの問題の合成を作ることができる。

行列以外の適切な非可換群を使えば新しい暗号ができるかもしれない。<-ここ！

置換群は行列表現が可能なので、絶対に使ってはいけない。
使うとするなら行列以外の材料で、例えば半直積を構成し、それを使うことを強くおすすめする。
離散対数問題はすでに死んでいるが、このような複数の生成元による複合的な離散対数がどのように解かれるかは興味深い。
というのも非可換群を使った離散対数には、左離散対数と右離散対数など、どちら側に元をかけていくかによる違いがあるからである。

だが、これを説明できる適当な言葉が思いつかない。

ここで $n$ 項等比数列の総和が $S_n=\frac{(c^n-1)}{c-1}$ から、
$(c,s)^n=(c^n,\frac{c^{n-1}-1}{c-1}s)$
$(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')$
$(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)$

$D_0=(p,f)^s(q,g)^t(r,h)^u=(p^sq^tr^u,q^tr^u\frac{p^{s-1}-1}{p-1}f+r^u\frac{q^{t-1}-1}{q-1}g+\frac{r^{u-1}-1}{r-1}h)$
$D_1=(p,f)^x(q,g)^y(r,h)^z=(p^xq^yr^z,q^yr^z\frac{p^{x-1}-1}{p-1}f+r^z\frac{q^{y-1}-1}{q-1}g+\frac{r^{z-1}-1}{r-1}h)$

この場合に明らかなのは、多項式はべき乗されないということである。

楕円曲線の場合はこちら

多項式と有限体の半直積で多元離散対数問題を構成する

多項式 $f,g,h \in F[x],p,q,r \in Z_p$
とすると、
$D'=(p,f)^s+(q,g)^t+(r,h)^u=(p^s+q^t+r^u,\frac{p^{s-1}-1}{p-1}f+\frac{q^{t-1}-1}{q-1}g+\frac{r^{u-1}-1}{r-1}h)$

多項式と有限体に上で半直積と呼んでいた算法を使って多元離散対数問題を構成する。

y_i=\Sigma ^n_{i=0}g_i^{x_i}

結論

半直積の多元離散対数問題と、半直積に加法を導入した半分配体での多元離散対数問題を定義した。
乗法に関して逆元が存在するので半分配体というらしい。

参考図書：半分配環論入門　近代科学社

続く