双線形写像について

エルガマル暗号は離散対数問題（DH問題）に基づいた暗号方式ですが、双線形写像を用いて離散対数問題を拡張した方式が考えられています。 双線形写像で二つの離散対数問題が結びつけられることにより、暗号方式に付加的な機能を実現することができる様になっています。 双線形写像としては楕円曲線上のペアリングと呼ばれる写像が用いられるのですが、この写像の実際の計算の仕方はとても難しく私の手には負えないので、実現されている双線形写像を道具として用いることについて考察して行きます。

群

G上の演算＊

ある集合Gがあり、その集合上で演算＊が定義されているとき、これを代数系と呼び、(G,＊)、または、簡単にGと表すことにします。 代数系(G,＊)では、a,b ∈ Gに対して、c=a＊bとなるGの要素cが必ずあります（演算＊は＋や×に置き換えて考えた方が分かりやすいです）。

1. 任意のa,b,c∈Gに対して、(a＊b)＊c=a＊(b＊c)　：結合律
2. 任意のa∈Gに対してa＊e = e＊a = a となるe∈Gが存在する。　：単位元の存在
3. それぞれのa∈Gに対して、a＊a’ = a’＊a = e となるa’が存在する　：逆元の存在
4. 任意のa,b∈Gに対して、a＊b = b＊a　：交換律

巡回群

Gのある要素gを用いて、Gの任意の要素aがgを何回か演算することによって得られるときGは巡回群であるといいます。 すなわち、任意の要素aをある要素gを用いて、

例：

Z3 = {0, 1, 2}とし、Z3上の演算として＋を法3の足し算として定義します。 Z3と演算+の組(Z3,+)は可換群になり、以下のようになります。 0＋1=1、2＋1=0、2＋2＝4　 このとき、0が単位元となり、2＋1＝0より、2の逆元は1、1の逆元は2となります。 1＝1、2＝1＋1、0＝1＋1＋1 より、Z3は巡回群となり１が生成元になります。 このとき２も生成元になります。

加法群、乗法群

群Gにおける演算としてはいろいろなものが考えられますが、代表的なものは足し算＋と掛け算×です。 足し算とみなせるような演算をもつ群を加法群、掛け算とみなせるような演算をもつ群を乗法群と呼びます。 ここでは、群を考える場合は足し算も掛け算も＊で表すことにします。

加法群：

単位元は０と表し、aの逆元は−aと表すことにします。 a ＊ 0 = a, a＊(−a) = 0 などとなります。aをn回足すことn・aと表すことにします。n・a =a＊…＊aです(aはn個)

乗法群：

単位元は１と表し、aの逆元は1/aと表すことにします。 a ＊ 1 = a, a＊(1/a) = 1 などとなります。aをn回かけることaⁿと表すことにします。aⁿ =a＊…＊aです(aはn個)。乗法群の場合はa＊bをabと略記する場合があります。

離散対数問題の一般化

巡回群Gにおいて生成元をgとしたときに、Gのある要素a ∈ Gがgを何個演算するとaになるかを求める問題を群G上の離散対数問題ということができます。

Gが乗法群のとき：

g^x = a となるxを求める問題。

Gが加法群のとき：

x・g = a となるxを求める問題。

楕円曲線上の群

楕円曲線：

楕円曲線とは以下の式で表される曲線です。 y² = x³+ax+b 点(x,y)が曲線上にあるならばy軸に関して対称となる点(x,−y)もこの曲線上の点になることがすぐに分かりますので、楕円曲線はx軸に関して対象であることが分かります。 直線 y=cx+dとの交点を考えるために、y=cx+dを代数曲線の式に代入するとxに関する3次式となることから、直線とは3点で交わることが分かります。

楕円曲線上の点の加算：

楕円曲線C上の点P₁, P₂に対して、P₁, P₂を通る直線fを考えると、fとCの交点は点P₁, P₂以外にもう一点あり、それをP’とします。P’のC上のx軸に対称点を点P₃とし、点P₃=P₁+P₂と定義します。 P₁とP₂がx軸に関して対象となる点の場合にはP₁, P₂を通る直線fはy軸と平行になってしまいます。 この場合には無限遠の点をOと定義して、O=P₁+ P₂とします。 P₁+O=O+P₁=Oとすると、楕円曲線上の点にOを加えた集合はこの加算により群になることが知られています。

楕円曲線上の群：

単位元はO、P₁とP₂がx軸に関して対象ならばP₂ = −P₁となります。 素数pに対してZ_p={0,1,…,p-1}上で法pの加算と乗算を考えると実数と同じ様に四則演算ができることが分かります。 実数の様に四則演算のできる代数系を体（たい）と呼びます。 Z_p上で法pの加算と乗算を考える場合は有限集合上の体ということで有限体と呼ばれます。 楕円曲線上は有限体上でも同様に考えることができ、有限体上の楕円曲線上の群も同様に生成できます。

楕円曲線上の離散対数問題：

有限体上の楕円曲線上の点は有限個しかありません。 この有限個の点上に先の様に加算を定義した加法群についても離散対数問題を考えることができ、この離散対数問題は効率的に解くのが難しい問題と考えられています。 楕円曲線上の点P₁,P₂に対して、 x・P₁ = P₁+P₁+…+P₁ (P₁をx個加算する) = P₂ が成り立つxを求める問題が楕円曲線上の離散対数問題になります。 楕円曲線上の離散対数問題の難しさに基づいたエルガマル暗号を構成することができます。

双線形写像

線形写像：

ベクトル空間上の写像fが以下の性質を満たすとき線形写像といいます。
任意のベクトルx, yと任意のスカラーcに対して、 f(x+y) = f(x) + f(y), f(cx) = cf(x). 線形写像fはベクトルの和をとるとfの値も和となり、ベクトルをc倍するとfの値もc倍になるような写像です。 ベクトルでの演算がfの値の演算にそのまま反映する写像と見ることがでいます。

群上の線形写像：

群G₁から群G_Tへの写像f: G₁→G_Tについて線形写像というものを考えると以下の性質を満たすことが対応します。 任意のa,b∈G₁に対して　f(a＊b) = f(a) ＊ f(b) この性質から、G₁, G_Tが加法群のとき、 f(n・a) = f(a＊…＊a) = f(a)＊…＊f(a) = n・f(a), となります。このとき、G_Tのみ乗法群であるとすると、 f(n・a) = f(a＊…＊a) = f(a)＊…＊f(a) = f(a)ⁿ となります。更に、G₁, G_Tが乗法群のとき、 f(an) = f(a＊…＊a) = f(a)＊…＊f(a) = f(a)ⁿ, となります。 ここではG_Tが加法群の場合もありますが、G_Tが乗法群の場合しか扱いませんので省略します。

双線形写像：

２つのベクトルに対して一つの値を与える２変数の写像fについて、それぞれのベクトルについて線形性を考えると双線形写像になります。 任意のベクトルx₁,x₂, y₁,y₂と任意のスカラーcに対して、 f(x₁+x₂,y₁) = f(x₁,y₁) + f(x₂,y₁), f(cx₁,y₁) = cf(x₁,y₁),
f(x₁,y₁+y₂) = f(x₁,y₁) + f(x₁,y₂), f(x₁,cy₁) = cf(x₁,y₁). この性質から例えば以下の等式が導けます。
任意のベクトルx₁,x₂, y₁,y₂に対して、 f(x₁+x₂,y₁+y₂) = f(x₁+x₂,y₁) + f(x₁+x₂,y₂)
f(x₁+x₂,y₁+y₂) = f(x₁,y₁) + f(x₂,y₁) +f(x₁,y₂) +f(x₂,y₂)

群上の双線形写像

群の二つの要素に対して別の群の要素を割当てる写像e: G₁×G₁→GTを考えます。 G₁,GT共に素数位数qの巡回群であるとします。 GTは乗法群とします。

G₁が加法群のとき：

任意の要素P₁,P₂,Q₁,Q₂ ∈ G₁に対して、 e(P₁+P₂,Q₁) = e(P₁,Q₁)e(P₂,Q₁), e(P₁,Q₁+Q₂) = e(P₁,Q₁)e(P₁,Q₂) となります。この性質から、 e(n・P₁,Q₁) = e(P₁,Q₁)ⁿ, e(P₁,n・Q₁) = e(P₁,Q₁)ⁿ が導かれます。

G₁が乗法群のとき：

任意の要素f₁,f₂,g₁,g₂ ∈ G₁に対して、 e(f₁＊f₂,g₁) = e(f₁,g₁)e(f₂,g₁), e(f₁,g₁＊g₂) = e(f₁,g₁)e(f₁,g₂) となります。この性質から、 e(f₁n,g₁) = e(f₁,g₁)ⁿ, e(f₁,g₁n) = e(f₁,g₁)ⁿ が導かれます。

非退化性

双線形写像は非退化性と呼ばれる次の性質を満たしているものが使われます。 G_Tの単位元を1とします。

G₁が加法群の場合：

G₁の生成元をPとすると、　e(P,P) = 1とはならない。

G₁が乗法群の場合：

G₁の生成元をgとすると、　e(g,g) = 1とはならない。

双線形群