Open2

暗号を作るために非可換群を工夫する

暗号マイスター暗号マイスター

この記事はなるべく正確に書くつもりですが、正しくないかもしれないので間違っていたらご指摘いただけたら直します。
支離滅裂かもしれませんが、これでもわかりやすく整理して書いているつもりです。
まあスクラップは自分用なのでてきとー。

半直積とは?

下記解説を参照。

https://mathematics-pdf.com/pdf/semiproduct.pdf

半分配環とは

楕円曲線とスカラーからできた半直積(これを楕円-スカラー半直積とここでは呼ぶことにする)にもう一つ可能な演算を定義します。
つまりこの半直積の元同士に足し算を定義して、その代数系が環になるかどうかを検査します。

X=(P,a),Y=(Q,b)
とします。この時この2元の掛け算は、
XY=(bP+Q,ab)
こうなります。P,Qは楕円曲線の点、a,b \in Z_pでいいです。
更に
X+Y=(P+Q,a+b)
と、加法を定義することができました。

これは片側からしか分配則が成り立たない。
そのような代数系は半分配環とか半分配体などと言われる代数系になります。
結合則も満たすし、加法および積に関する逆元もあるし、それを考えるとただの非可換環でもなさそう。

という訳で調べてみると、加法と積の両方が群の場合を体という代数系になる。
0以外の元に対して逆元の存在を考えるとわり算もできることになる。
なので楕円-スカラー半直積の2つの演算に群の性質をもたせると、これは体になるということらしい。
積に関しては片側からの分配則しか成り立たいので、これは半分配体になります。
加法が導入できたのは楕円-スカラー半直積の場合だけなので、他にも試してみたいのですが、とりあえずここでは1つだけにします。

小さな半直積の離散対数問題は、半直積の第2要素であるスカラー部分の計算は普通の有限体上の離散対数問題になるので古典計算機でも量子計算機にも両方弱い。
なのでここは離散対数によらない秘密の守り方をしなければならない。

AAG鍵共有に対する実験的構成

RHAMANの場合離散対数問題を使っているが、ここでは同じ材料でAAG方式を構成してみる。

https://arxiv.org/abs/1802.07300

まずアリスとボブは、ある非可換群の中から任意の元A,B,C,Dを選んで、それに基づいて公開鍵を作成することに同意する。
例えば、アリスが元をA,Bを選び、ボブの元はC,Dであるとする。
この時アリスとボブは互いにどのパラメーターを選んだのかを相手に通知する必要がない。
アリスは鍵を交換するためにランダムな長さkの2進列を生成し、0をAに、1をBに対応させて自分の秘密鍵をs=ABABとし、A,B,C,Dを全て自分の鍵を使って、

P_a=(sAs^{-1},sBs^{-1},sCs^{-1},sDs^{-1})

としてこれをアリスの公開鍵にする。ボブも秘密の2進列をt=DCDCとし、公開鍵を
P_b=(tAt^{-1},tBt^{-1},tCt^{-1},tDt^{-1})

として公開鍵にする。
ここで互いに相手の公開鍵を使って自分の秘密鍵を構成すれば、自然と相手の秘密鍵も手に入るという事になる。
トリッキーですね。
この方式は最初ポリサイクリック群(何だかよくわからない)で構成されたんですが、攻撃方法が見つかってなかなか新素材を見つけるのは難しいということが解ってきた。
これからプラットホームは、それぞれバイナリ行列(ブール行列)と置換群、あるいは楕円曲線の点とスカラー、そして置換ベクトル(行列にすると演算が足りない)、楕円-スカラーの半直積からなる行列と置換群の4種類を試してみる。
いくらでも定義できそうだが、安全であるためには何が必要なのだろう。
この問題は行列が使えない。
なぜなら線形代数を使うことで秘密鍵Xが分かるからだ。

共役元探索(決定)問題についてざっくりと

今、W=XYX^{-1}W,YからXを計算したい。この問題を共役元決定問題という。
ここでWを満たす2個か3個の元に分割できればそれでいいとする場合がある。
その場合、与えられた2つの生成元A,Bを使ってW=aA+bBと計算できるa,bが計算できれば良い。
例えば、ベクトルA,B,Wが与えられて、置換群a,bを決定する問題になる。
そしてある性質を満たすこと以上は、単に予測するよりいい方法がないらしい。(公開鍵以外は何もわからないので)
今、X,Yが行列の場合、共役元探索問題は簡単である。
WX=XY
と変形するのは簡単である。
ここでW,X,Yが非特異2次正方行列であるとすると、Xの4つの未知変数に対して4本の方程式があるので、これらの連立方程式を解くことでXが決定できる。

暗号マイスター暗号マイスター

MOBS

ここで漸く真打ち登場。
MOBSとはNEAL RAHMAN とSHPILRHAINらが構成した鍵交換の方法がある。
詳しくは以下のリンクで読める。

https://eprint.iacr.org/2021/560.pdf

MOBSで使われている半直積を材料に、離散対数以外の問題で暗号を構築したい。
半直積の元を、R=(M,\phi)とする。
ここで、Mは2進列を要素に持つ行列、そして\phiは置換群である。
オリジナルは行列の要素であるバイナリ列を、置換群で並べ替えている。

MOBSを使ってAAGを構成するとどうなるの?

バイナリ列と置換群の組み合わせという発想はなかったのでやってみる。
主役の登場である。
行列でも、非対称な公開鍵になら、わずかながら使えるらしい。
ところが、AAGは共役元探索問題に行列を使おうとすると、鍵の構造が対称的なので線形代数攻撃で解読されてしまう。
そこでMOBSというプラットホームを使うことを考える。(続く)

非対称構造の鍵はMOBSで復活するか?

非対称構造にすることでy=x^mzy^ny,zからxを求めたいと言っている。
これは共役元探索問題のマイナーバージョンである。(どこかで見つけたけど何だか忘れた)

以下予定

https://eprint.iacr.org/2021/560.pdf

非可換群は暗号の宝庫ではなかったらしい。