半分配環を使った公開鍵暗号：その２

ChatGPTのヒントから

異なる生成元を使っても、同じ素体上で定義された離散対数問題であることは変わらないので、いずれにしても次のように書くことができるはずである。
$P$を素数とし、$g,x,y \in Z_P$とし$g$は原始元、$x,y$は秘密指数とすると、離散対数は$g_0^xg_1^y=g^{x'+y'}$となるだけではないのか？$x'+y'=a$と置けば、$g^a$となり、元の木阿弥になってしまう。
ということは２つ異なる原始元を使ったとしても、何もメリットがないことになるのだが、違うのだろうか？

そこでChatGPTに質問すると、この問題は多元離散対数問題と呼ぶのだと答えた。

ChatGPTから聞いた情報を元に、半分配体の離散対数問題（Nier-field Discrete Logarithm Problem）を調べてみた。
その結果日本語の情報は１つ。英語で発表された論文が４本程度。
かなりマイナーな問題らしい。

ChatGPTのいう事が正しいかどうかはさておいて、まず$g^a$が計算できることが$x$と$y$を独立に求めることとは全く違うし、また$x,y$の候補となる解は複数存在することから、左側成分の解を求めることがこの問題の解であるというわけではない。つまり、左側成分を満たすと同時に右側成分も満たすような独立した秘密指数の組を本当の解として計算する必要がある。これは一般的に難しいと思われる。
20230805：追記
このような条件を満たすのは、多元離散対数の指数が独立で1つの指数の和に書くことができないような場合である。例えば$(a^xb^yc^z,xP,yQ,zR)$などというように、左側要素は合成できるけど右側要素が1つにかけないような条件になっているとかである。例えば$a^sb^tc^u=g^(s+t+u)=g^x$のとき$yP+0Q+0R$などである。ただこの場合右側をばらしてしまうと、その次点で半直積の元でなくなってしまうので解決法にならない。この工夫の仕方は幾つかあると思うので、それを考えていきたい。幾つかの例は失敗している。つまり左右同時に満たすような複数の絵画存在するのである。存在しない場合を見つけたら別記事にする予定です。第3部を書く前に次の新型を思いついてしまったので次の新型のことを書くつもりでいる。というのもこの業界は春秋戦国時代であって、泡のように暗号方式が出ては消えていく状態だからだ。どのように暗号を構成すれば安全な暗号を作れるのか誰も知らないということだ。今度のは半分配体ではなく、純粋な半直積でそれは加法を定義できない乗法群からなる。なので要素ごとの足し算は定義できないので、半分配体ではない。楕円の半直積は危険であるという研究を見て急遽暗号化の材料を変更しました。

もし普通の離散対数問題と同じなら指数計算法で解読できる。
一方、多数の秘密指数を解に持つような多元離散対数問題の解読法はよくわからない。（指数の数に比例するというような論文はある）

普通の多元離散対数問題は次のように定義される。
$P$を素数とする。
$(P,x_i,y_i),y_i \in Z_P,x_i \in Z_P$である時、$(P,y_i)$から$i$個の$x_i$を求める問題である。

一方、同じ条件で、$g^x+g^y$ならもうこれは難しい問題になるだろうか。
全ての指数を知らないと計算できないからだ。
多元離散対数問題はBLS署名からでたとChatGPTは言っていた。
ここで多元離散対数なるものの定義をする。

定義：対称離散対数問題（多項式と有限体の半直積による）

$(y,z,m,n)$が公開されているとする。

$$y=x^mzx^n$$

$y,z$から秘密$x$を求める問題を、半直積の対称離散対数問題と呼ぶことにする。
$D_0=(p,f)^s(q,g)^t(p,f)^u=(p^sq^tp^u,q^tp^u\frac{p^{s-1}-1}{p-1}f+p^u\frac{q^{t-1}-1}{q-1}g+\frac{p^{u-1}-1}{p-1}f)$
$D_1=(r,h)^x(q,g)^y(r,h)^z=(r^xq^yr^z,q^yr^z\frac{p^{x-1}-1}{p-1}h+r^z\frac{q^{y-1}-1}{q-1}g+\frac{r^{z-1}-1}{r-1}h)$

半直積の算法の定義から、以下のように半直積の逆元は定義される。

$$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)$$

このように、半直積の元の逆元は、法となる既約多項式の存在を仮定しない。

1：有限体と多項式の半直積バージョン（対称離散対数問題）

秘密鍵：$t,y \in Z_p,A,C,s > u, x > z$
公開鍵：$s,u,x,z,D_0,D_1,B \in (Z_p,F[x]),D_0=A^sB^tC^u,D_1=A^xB^yC^z$
$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=(a,f)(b,g)=(ab,bf+g)$
$BA=(b,g)(a,f)=(ab,ag+f)$
となり、非可換である。

ここで$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(p,f)^u=(p^sq^tp^u,q^tp^u\frac{p^{s-1}-1}{p-1}f+p^u\frac{q^{t-1}-1}{q-1}g+\frac{p^{u-1}-1}{p-1}f)$
$D_1=(r,h)^x(q,g)^y(r,h)^z=(r^xq^yr^z,q^yr^z\frac{p^{x-1}-1}{p-1}h+r^z\frac{q^{y-1}-1}{q-1}g+\frac{r^{z-1}-1}{r-1}h)$

問題：上の条件から秘密の半直積の元$A,C$を求めよ。

暗号化

$C1=A^rD_0A^s$
$C3=C^rD_1C^s$

注意
ここで言う対称離散対数問題とは、２つ以上の秘密の元を積によって１つの元を出力するものであるが、例えば$p,q,r$が同じ素体上で定義され、かつ異なる指数と原始元を選ぶものとする。
すると、左側成分の解空間は通常の離散対数より変数の数に比例して大きくなる。
しかし同時に、解となる組み合わせも複数存在することから、左側成分だけから解を特定することにはならない。したがって、次のように１つの離散対数を解いているのと全く異なる。
多元離散対数問題の半直積版を用いた場合、右側要素の計算に、$g_0,g_1$に対する$x_0,x_1$の独立した値を必要とする。例えば、

$$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)$$

の場合、右側要素は、

$$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$$

となるので、$s,t,u$を個別に知る必要がある。これが多元離散対数問題と（単一）離散対数問題との違いである。

この場合、半直積は乗法群になっているが、逆元の存在を仮定しなければ半群になる。
半直積には加法が存在しないので、半分配環とは言えない。
なので、この問題設定には多項式そのものの逆元を前提にしなくても、半直積の逆元があればよい。

この複数の離散指数を解に持つ半直積の元は、右側要素も同時に満たさなければならないが、そのような解の組み合わせはただ１つだけであると思われる。
半直積についてはここまで

暗号化

解読法の発見

２０２３年７月、楕円半直積の離散対数問題に攻撃法が発見された。
https://eprint.iacr.org/2023/1052
これにより楕円半直積の離散対数問題は解読できることが示された。
するとこの暗号はどうなるだろうか？
もはや離散対数問題とは言えないので次のように$D,E$は表現されるべきである。
$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)=XYZ=(xyz,aP+bQ+cR)$
つまり、有限体の積、および点の加法に関する分割問題になると思われる。しかし、依然として$a,b,c$は未知の定数$s,t,u$により記述が可能である。

2：半直積に加法を導入する（半分配体の構成）

次に、半直積に加法を導入して、半分配体を構成した場合の離散対数を以下のように記述する。

ここで、半直積同士に加法を定義してみる。$P,Q \in E$とすると、
$(p,P)+(q,Q)=(p+q,P+Q)$
$(a,P)^n+(b,Q)^m=(a^n+b^m,\frac{a^{n-1}-1}{a-1}P+\frac{b^{m-1}-1}{b-1}Q)$
一般的に、半分配体で加法に関して可換であることは必要ではないが、ここで定義する半分配体の加法は可換性を満たす。
この時、加法における逆元は、$(a,A)^{-1}=(-a,-A)$である。

定義：有限体と楕円曲線を使った半分配体上の多元離散対数問題

1と同じように材料を定義する。

$E$を素体で定義される素数位数$p$の楕円曲線とする。
秘密鍵：$s,t,u,x,y,z \in Z_p,B \in (Z_p,E) ,s > u, x > z$
公開鍵：$A,C,D_0,D_1 \in (Z_p,E),D_0=A^sB^tC^u,D_1=A^xB^yC^z$
$p,q,r \in Z_p$ の異なる原始元。
$P,Q,R \in E$　は同じ楕円曲線上の異なる点とする。
つまり、半直積に使う元、$A,B,C$は、それぞれ有限体の元$p,q,r$と楕円曲線の異なる点$P,Q,R$とを任意に取り、
$A=(p,P),B=(q,Q),C=(r,R)$
であるとする。

$(y,P,g_i)$が公開パラメータとして、素数$P$、互いに素な$i$個の原始元$g_i$、$i$個の秘密指数$x_i$があった時、

$$y=\Sigma^n_{i=0}g_i^{x_i}$$

$(y,P,g_i)$から$(x_0,x_1,...,x_n)$を求める問題を、半分配体上の多元離散対数問題：(Additive Multi Discrete Logarithm Problem over Near-Ring)と呼ぼう。
ここで注意するべきことは、半直積に加法を導入することで半分配体になり、要素ごとの足し算ができるようになったことである。（行き当たりばったり）
もしこれがうまく行けば、難しい問題になる可能性あり。

（修正ここまで：20230717）

https://qiita.com/fumumue/items/5f622ee6ea83cbd4a7f9

より抜粋。
$(c,s)^n=(c^n,\frac{c^{n-1}-1}{c-1}s)$

であるから、公開鍵を$D,E$とすると、
$D=(p,P)^s+(q,Q)^t+(r,R)^u=(p^s,\frac{p^{s-1}-1}{p-1}P)+(q^t,\frac{q^{t-1}-1}{q-1}Q)+(r^u,\frac{r^{u-1}-1}{r-1}R)=(p^s+q^t+r^u,\frac{p^{s-1}-1}{p-1}P+\frac{q^{t-1}-1}{q-1}Q+\frac{r^{u-1}-1}{r-1}R)$
$E=(p,P)^x+(q,Q)^t+(r,R)^y=(p^x,\frac{p^{x-1}-1}{p-1}P)+(q^t,\frac{q^{t-1}-1}{q-1}Q)+(r^y,\frac{r^{y-1}-1}{r-1}R)=(p^x+q^t+r^y,(\frac{p^{x-1}-1}{p-1})P+\frac{q^{t-1}-1}{q-1}Q+(\frac{q^{y-1}-1}{q-1})R)$

暗号文：
$C1=A^r+D+C^{r'}=A^{r}+A^s+B^t+C^u+C^{r'}$
$C2=A^{r}+E+C^{r'}=A^r+A^x+B^t+C^{r'}+C^y$

復号
アリスは$x,y$を知っているので以下を計算できる。
$X=A^{s}-A^x+C2+C^u-C^y=A^s+A^r+B^t+C^{r'}+C^u=C1$

これなら全ての指数を知らなければ解読できないので、ある意味強度が普通の離散対数より上がったことになると思われる。これは素数$P$を法とする、指数に全く制約のないランダムナップサック問題のようなものかもしれない。
なので、攻撃者がこの問題を解くためには全ての指数を知る必要がある。

加法と積が定義できれば、ほとんど体と同じということになる。
しかも演算子ほぼそのまま変わらず。
無駄な計算や重複しているかもしれない部分を後日訂正する。
（計算結果は正しかった）

$A,B,C$に異なる原始元を使うことはここで効いてくる。
乗法的多元離散対数問題は、もし同じ原始元を使うとすれば、右側要素である楕円曲線の点群は単なる点のスカラー倍を計算しているのと同じであり、左側の要素は異なる指数の総和になる。
この状況は普通の離散対数のように、左と右の要素による計算問題の中で、弱い方の離散対数問題を解くことに値する。しかし、通常の離散対数問題は量子計算機に解読されるので意味がない。

多元離散対数問題の加法バージョンを使うことにより、これらの問題を回避し、更に難しい問題に変えることができるのではないか。$A,B,C$のそれぞれに異なる原始元を使うことで、この暗号の強度は高まるかどうかは保証できないが。例えば、秘密鍵が互いに独立するように選べば、秘密鍵空間が広がるので解読は難しくなるかもしれない。
まあ面白いのはここまでなんですがｗ

半分配体の性質を利用する（途中）

半分配体というのは、分配法則が右か左かのどちらか一方しか満たさない体である。
今迄考えてきた半分配体は左半分配体だった。
この半分配性を生かした暗号化関数を構成することがこれ課題である。
これは、次のような問題になる。
$A=(p,P),B=(q,Q),C=(r,R)$
とする。

$$\alpha=B^z(A^x+C^y)$$

$$\beta=(A^x+B^y)B^z$$

$A,C$が公開鍵で、秘密指数$x,y,B^z$は秘密鍵とする。
更に次を定義する。

$$\tau=$$

今のところは鍵交換に使っていますが、ここで今後公開鍵暗号方式を設計するときに必要なことは、線形代数に気をつけることと、LWE問題のような（未知の値はエラーが入って０になったと考えればいいので）別の問題に帰着できるようにすることです。

次の記事で環であるかどうかを考察し、更に上の問題について考えます。