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$の候補となる解は複数存在することから、左側成分の解を求めることがこの問題の解であるというわけではない。つまり、左側成分を満たすと同時に右側成分も満たすような独立した秘密指数の組を本当の解として計算する必要がある。これは一般的に難しいと思われる。
もし普通の離散対数問題と同じなら指数計算法で解読できる。
一方、多数の秘密指数を解に持つような多元離散対数問題の解読法はよくわからない。（指数の数に比例するというような論文はある）
普通の多元離散対数問題は次のように定義される。
$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は言っていた。
ここで多元離散対数なるものの定義をする。
定義：多元離散対数問題（MDLP）
$(y,g_i)$が公開されているとする。互いに独立した$i$個の半直積の元$g_i$、$i$個の秘密指数$x_i$があった時、
$$y \equiv {(\Pi^n_{i=0} \lor \Sigma^n_{i=0})g_i^{x_i}} \pmod {p}$$
$y$から秘密指数の組$(x_i:0 \leq i \leq n)$を求める問題を、半直積の多元離散対数問題（MDLP,もしくはMulti Exponential）と呼ぶ。（この定義はほかの資料でも確認できる）
しかしこれには問題があり、
$y=g_0^{x_0}g_1^{0}111,...,1=g_0^{x_0}$
が成り立てばよい。つまり偽の平文を作り出すことができる。鍵交換にこの弱点を使われると鍵を共有できなくなる。
公開鍵は$(y,g_i)$である。求めなければならないのは$x_i$である。
半直積の算法の定義から、以下のように半直積の逆元は定義される。
$$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：多元離散対数問題：MDLP
$$y \equiv {\Pi^n_{i=0}g_i^{x_i}} \pmod {p}$$
秘密鍵：$s,t,u,x,y,z \in Z_p,B \in E,s > u, x > z, (s,t,u >0)$
公開鍵：$A,C,D_0,D_1 \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(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)$
注意
ここで言う多元離散対数問題とは、２つ以上の原始元を積によって１つの元を出力するものであるが、例えば$p,q,r$が同じ素体上で定義され、かつ異なる指数$s,t,u > 0$と原始元$A,B,C$を選ぶものとする。
$D_0=(p,f)^s(q,g)^0(r,h)^0=(p^s,q^0r^0\frac{p^{s-1}-1}{p-1}f+r^0\frac{q^{0-1}-1}{q-1}g+\frac{r^{0-1}-1}{r-1}h)$
すると、左側成分の解空間は通常の離散対数より変数の数に比例して大きくなる。
しかし同時に、解となる組み合わせも複数存在することから、左側成分だけから解を特定することにはならない。したがって、次のように１つの離散対数を解いているのと全く異なる。
多元離散対数問題の半直積版を用いた場合、右側要素の計算に、$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$を個別に知る必要がある。これが多元離散対数問題と（単一）離散対数問題との違いである。
この場合、半直積は乗法群になっているが、逆元の存在を仮定しなければ半群になる。
半直積には加法が存在しないので、半分配環とは言えない。
なので、この問題設定には多項式そのものの逆元を前提にしなくても、半直積の逆元があればよい。
楕円曲線バージョンは、$f,g,h$を$P,Q,R \in E$に置き換えるだけである。つまり、
$$D'_0=(p,P)^s(q,Q)^t(r,R)^u=(p^sq^tr^u,q^tr^u\frac{p^{s-1}-1}{p-1}P+r^u\frac{q^{t-1}-1}{q-1}Q+\frac{r^{u-1}-1}{r-1}R)$$
である。これは積に関するMDLPになっていると思われる。むしろ楕円曲線の方がMDLPを実現するのにいいかもしれない。
この複数の離散指数を解に持つ半直積の元は、右側要素も同時に満たさなければならないが、そのような解の組み合わせはただ１つだけであると思われる。しかしこの場合も本当に解が一意であることを保証しなければならない。（確認予定）
半直積についてはここまで
楕円曲線の点と有限体のペアを用いた場合は次のセクションで使うMDLPの加法バージョンを使う必要がある。
2：半直積に加法を導入する（Simultaneous Discrete Logarithm Problem、SDLP）
次に、半直積に加法を導入して、半分配体を構成した場合の離散対数を以下のように記述する。
ここで、半直積同士に加法を定義してみる。$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)と呼ぶ。
つまり、求めるべき秘密指数が1個なのがSDLP、複数なのがこの問題である。（ここでもまだ条件が弱い。複数の指数の組がただ一つだけであることを保証しなければならない。そのためには現実的ではない選択をしなければならない。）
$y$が1つの場合条件を満たす指数の組が複数あるかもしれないのであまり意味がないかもしれない。なぜなら1つの値を満たすような複数の値を借りに設定したとしても、全ての指数を必要とする条件にはならないからだ。
ここで注意するべきことは、半直積に加法を導入することで半分配体になり、要素ごとの足し算ができるようになったことである。（行き当たりばったり）
もしこれがうまく行けば、難しい問題になる可能性あり。
注：
つい最近、楕円曲線と有限体を使った半直積の離散対数問題に準指数的計算量で解読できる量子計算機用の解読法が見つかったらしい。しかしこの場合でも加法的多元離散対数を使えばこの攻撃法も何とかなるのではないかと思う。（まだよくわからないが）
より抜粋。
$(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+(p,P)^s+(q,Q)^t+(r,R)^u+(r,R)^y=(p^x,\frac{p^{x-1}-1}{p-1}P)+(p^s,\frac{p^{s-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)+(r^u,\frac{r^{u-1}-1}{r-1}R)=(p^x+p^{s}+q^t+r^{u}+r^y,(\frac{p^{x-1}-1}{p-1}+\frac{p^{s-1}-1}{p-1})P+\frac{q^{t-1}-1}{q-1}Q+(\frac{q^{y-1}-1}{q-1}+\frac{r^{u-1}-1}{r-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+A^s+B^t+C^{r'}+C^y+C^u$
復号
アリスは$x,y$を知っているので以下を計算できる。
$X=A^{(x)}+C1+C^{(y)}=A^{s}+A^x+A^r+B^t+C^{r'}+C^y+C^u=C2$
これなら全ての指数を知らなければ解読できないので、ある意味強度が普通の離散対数より上がったことになると思われる。これは素数$P$を法とする、指数に全く制約のないランダムナップサック問題のようなものかもしれない。
なので、攻撃者がこの問題を解くためには全ての指数を知る必要がある。
加法と積が定義できれば、ほとんど体と同じということになる。
しかも演算子ほぼそのまま変わらず。
無駄な計算や重複しているかもしれない部分を後日訂正する。
（計算結果は正しかった）
$A,B,C$に異なる原始元を使うことはここで効いてくる。
乗法的多元離散対数問題は、もし同じ原始元を使うとすれば、右側要素である楕円曲線の点群は単なる点のスカラー倍を計算しているのと同じであり、左側の要素は異なる指数の総和になる。
この状況は普通の離散対数のように、左と右の要素による計算問題の中で、弱い方の離散対数問題を解くことに値する。しかし、通常の離散対数問題は量子計算機に解読されるので意味がない。
多元離散対数問題の加法バージョンを使うことにより、これらの問題を回避し、更に難しい問題に変えることができるのではないか。$A,B,C$のそれぞれに異なる原始元を使うことで、この暗号の強度は高まるかどうかは保証できないが。例えば、秘密鍵が互いに独立するように選べば、秘密鍵空間が広がるので解読は難しくなるかもしれない。
まあ面白いのはここまでなんですがｗ
ぱっと見どの問題が一番難しいのかわからないので、実験して自分が思いつく危険性なんかを検証してみたい。
(追加：20230731)
半分配体の性質を利用する（途中）
半分配体というのは、分配法則が右か左かのどちらか一方しか満たさない体である。
今迄考えてきた半分配体は左半分配体だった。
この半分配性を生かした暗号化関数を構成することがこれ課題である。
これは、次のような問題になる。
$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問題のような（未知の値はエラーが入って０になったと考えればいいので）別の問題に帰着できるようにすることです。
次の記事で環であるかどうかを考察し、更に上の問題について考えます。
（それにしてもチャットGPTは正直なのでいろいろ知らないことを教えてくれて、その情報が見つかったりするのだが、アメリカの検閲がすごくて暗号に関するクリティカルなものは全く見当たらない。仮にチャットGPTが本当にその論文で学習したにしても、その論文は存在しないことになっている。知識の出し惜しみｗ）