暗号多線型マップ

暗号-多重線型写像は多重線型写像の一種であり、任意の整数および要素に対して、 、かつ となる関数であり、さらに効率的に計算可能で、いくつかのセキュリティ特性を満たす。暗号学では、鍵交換プロトコル、アイデンティティベース暗号化、ブロードキャスト暗号化など、さまざまな用途がある。${\displaystyle n}$暗号2-多重線型写像の構築は双線形写像として知られているが^{[1] 、このような多重線型[1]}写像を に対して構築する問題ははるかに困難であるように思われ^[2] 、提案された候補のセキュリティはまだ不明確である。^[3]${\displaystyle e:G_{1}\times \cdots \times G_{n}\rightarrow G_{T}}$${\displaystyle a_{1},\ldots ,a_{n}}$${\displaystyle g_{i}\in G_{i}}$${\displaystyle e(g_{1}^{a_{1}},\ldots ,g_{n}^{a_{n}})=e(g_{1},\ldots ,g_{n})^{\prod _{i=1}^{n}a_{i}}}$${\displaystyle n>2}$

この場合、多重線型写像は主に双線型写像またはペアリングとして知られ、通常は次のように定義されます。^[4]を素数位数の加法巡回群 2 つと、乗法的に記述された位数の別の巡回群と します。ペアリングは写像 であり、次の特性を満たします。 ${\displaystyle G_{1},G_{2}}$${\displaystyle q}$${\displaystyle G_{T}}$${\displaystyle q}$${\displaystyle e:G_{1}\times G_{2}\rightarrow G_{T}}$

双線形性

${\displaystyle \forall a,b\in F_{q}^{*},\ \forall P\in G_{1},Q\in G_{2}:\ e(aP,bQ)=e(P,Q)^{ab}}$

非退化

および がそれぞれおよびの生成元である場合、 はの生成元です。${\displaystyle g_{1}}$${\displaystyle g_{2}}$${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle e(g_{1},g_{2})}$${\displaystyle G_{T}}$

計算可能性

を計算するための効率的なアルゴリズムが存在します。${\displaystyle e}$

さらに、セキュリティ上の理由から、離散対数問題はと の両方において困難である必要があります。 ${\displaystyle G_{1}}$${\displaystyle G_{2}}$

次の特性を満たす場合、 その写像は-多重線型写像であると言えます。${\displaystyle e:G_{1}\times \cdots \times G_{n}\rightarrow G_{T}}$${\displaystyle n}$

1. すべて（ について）およびは同じ位数のグループです。${\displaystyle G_{i}}$${\displaystyle 1\leq i\leq n}$${\displaystyle G_{T}}$
2. かつならば;​${\displaystyle a_{1},\ldots ,a_{n}\in \mathbb {Z} }$${\displaystyle (g_{1},\ldots ,g_{n})\in G_{1}\times \cdots \times G_{n}}$${\displaystyle e(g_{1}^{a_{1}},\ldots ,g_{n}^{a_{n}})=e(g_{1},\ldots ,g_{n})^{\prod _{i=1}^{n}a_{i}}}$
3. 写像は、がそれぞれ のジェネレータである場合、 が の ジェネレータであるという意味で退化していない。${\displaystyle g_{1},\ldots ,g_{n}}$${\displaystyle G_{1},\ldots ,G_{n}}$${\displaystyle e(g_{1},\ldots ,g_{n})}$${\displaystyle G_{T}}$
4. を計算するための効率的なアルゴリズムが存在します。${\displaystyle e}$

さらに、セキュリティ上の理由から、離散対数問題は で困難である必要があります。 ${\displaystyle G_{1},\ldots ,G_{n}}$

候補となるすべての多重線型マップは、実際には段階的符号化システムとして知られる多重線型マップを少し一般化したものです。これは、マップを部分的に適用できるためです。つまり、一度にすべての値に適用してターゲット セット に値を生成する代わりに、いくつかの値に適用して中間のターゲット セットに値を生成することができます。たとえば、 の場合、を実行してからを行うことができます。 ${\displaystyle e}$${\displaystyle n}$${\displaystyle G_{T}}$${\displaystyle e}$${\displaystyle n=3}$${\displaystyle y=e(g_{2},g_{3})\in G_{T_{2}}}$${\displaystyle e(g_{1},y)\in G_{T}}$

主な候補としては、多項式環のイデアルに基づくGGH13 ^[5]、近似GCD問題に基づき整数上で動作するためGGH13多重線型写像よりも理解しやすいとされるCLT13 [ ^6] 、グラフに基づく GGH15 ^{[7]の3つがある。}