暗号を作るために非可換群を工夫する
この記事はなるべく正確に書くつもりですが、正しくないかもしれないので間違っていたらご指摘いただけたら直します。
支離滅裂かもしれませんが、これでもわかりやすく整理して書いているつもりです。
まあスクラップは自分用なのでてきとー。
半直積とは?
下記解説を参照。
半分配環とは
楕円曲線とスカラーからできた半直積(これを楕円-スカラー半直積とここでは呼ぶことにする)にもう一つ可能な演算を定義します。
つまりこの半直積の元同士に足し算を定義して、その代数系が環になるかどうかを検査します。
とします。この時この2元の掛け算は、
こうなります。P,Qは楕円曲線の点、
更に
と、加法を定義することができました。
これは片側からしか分配則が成り立たない。
そのような代数系は半分配環とか半分配体などと言われる代数系になります。
結合則も満たすし、加法および積に関する逆元もあるし、それを考えるとただの非可換環でもなさそう。
という訳で調べてみると、加法と積の両方が群の場合を体という代数系になる。
0以外の元に対して逆元の存在を考えるとわり算もできることになる。
なので楕円-スカラー半直積の2つの演算に群の性質をもたせると、これは体になるということらしい。
積に関しては片側からの分配則しか成り立たいので、これは半分配体になります。
加法が導入できたのは楕円-スカラー半直積の場合だけなので、他にも試してみたいのですが、とりあえずここでは1つだけにします。
小さな半直積の離散対数問題は、半直積の第2要素であるスカラー部分の計算は普通の有限体上の離散対数問題になるので古典計算機でも量子計算機にも両方弱い。
なのでここは離散対数によらない秘密の守り方をしなければならない。
AAG鍵共有に対する実験的構成
RHAMANの場合離散対数問題を使っているが、ここでは同じ材料でAAG方式を構成してみる。
まずアリスとボブは、ある非可換群の中から任意の元
例えば、アリスが元を
この時アリスとボブは互いにどのパラメーターを選んだのかを相手に通知する必要がない。
アリスは鍵を交換するためにランダムな長さ
としてこれをアリスの公開鍵にする。ボブも秘密の2進列を
として公開鍵にする。
ここで互いに相手の公開鍵を使って自分の秘密鍵を構成すれば、自然と相手の秘密鍵も手に入るという事になる。
トリッキーですね。
この方式は最初ポリサイクリック群(何だかよくわからない)で構成されたんですが、攻撃方法が見つかってなかなか新素材を見つけるのは難しいということが解ってきた。
これからプラットホームは、それぞれバイナリ行列(ブール行列)と置換群、あるいは楕円曲線の点とスカラー、そして置換ベクトル(行列にすると演算が足りない)、楕円-スカラーの半直積からなる行列と置換群の4種類を試してみる。
いくらでも定義できそうだが、安全であるためには何が必要なのだろう。
この問題は行列が使えない。
なぜなら線形代数を使うことで秘密鍵
共役元探索(決定)問題についてざっくりと
今、
ここで
その場合、与えられた2つの生成元
例えば、ベクトル
そしてある性質を満たすこと以上は、単に予測するよりいい方法がないらしい。(公開鍵以外は何もわからないので)
今、
と変形するのは簡単である。
ここで
MOBS
ここで漸く真打ち登場。
MOBSとはNEAL RAHMAN とSHPILRHAINらが構成した鍵交換の方法がある。
詳しくは以下のリンクで読める。
MOBSで使われている半直積を材料に、離散対数以外の問題で暗号を構築したい。
半直積の元を、
ここで、
オリジナルは行列の要素であるバイナリ列を、置換群で並べ替えている。
MOBSを使ってAAGを構成するとどうなるの?
バイナリ列と置換群の組み合わせという発想はなかったのでやってみる。
主役の登場である。
行列でも、非対称な公開鍵になら、わずかながら使えるらしい。
ところが、AAGは共役元探索問題に行列を使おうとすると、鍵の構造が対称的なので線形代数攻撃で解読されてしまう。
そこでMOBSというプラットホームを使うことを考える。(続く)
非対称構造の鍵はMOBSで復活するか?
非対称構造にすることで
これは共役元探索問題のマイナーバージョンである。(どこかで見つけたけど何だか忘れた)
以下予定
非可換群は暗号の宝庫ではなかったらしい。