ペアリング関数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/05/13 09:27 UTC 版)
「ボネ・リン・シャチャム署名」の記事における「ペアリング関数」の解説
BLS署名は、Computational Diffie-Hellman問題（CDH）は困難であるがDecisional Diffie-Hellman問題 (DDH) は容易に解けるような群を利用している。このような性質を持つ群は、非退化かつ効率的に計算可能な双線型写像によって得ることができる。 G {\displaystyle G} と G T {\displaystyle G_{T}} を、同じ素数の位数 r {\displaystyle r} を持つ乗法群とし、 g {\displaystyle g} を、群 G {\displaystyle G} の生成元とする。 G {\displaystyle G} 上のCDH問題は困難であるとしよう。つまり、インスタンス ( g , g x , g y ) {\displaystyle (g,g^{x},g^{y})} が与えられたとき、 g x y {\displaystyle g^{xy}} を計算するのは難しい。 関数 e : G × G → G T {\displaystyle e\colon G\times G\rightarrow G_{T}} を、 非退化： e ( g , g ) {\displaystyle e(g,g)} は G T {\displaystyle G_{T}} の単位元ではない a , b ∈ G {\displaystyle a,b\in G} が与えられたとき、 e ( a , b ) {\displaystyle e(a,b)} は効率的に計算可能 双線型性：任意の a , b ∈ G {\displaystyle a,b\in G} と任意の自然数 m , n {\displaystyle m,n} に対して、 e ( a m , b n ) = e ( a , b ) m n {\displaystyle e(a^{m},b^{n})=e(a,b)^{mn}} が成り立つ という性質を満たす関数（ペアリング関数）とする。直感的に、ペアリング関数 e {\displaystyle e} は、 G {\displaystyle G} 上のCDH問題の解決の助けにはならず、このような関数が存在しても、CDH問題を解くことは困難であると推測できる。一方、DDH問題のインスタンス ( g , g x , g y , g z ) {\displaystyle (g,g^{x},g^{y},g^{z})} が与えられたとき、 g z = g x y {\displaystyle g^{z}=g^{xy}} が成り立つかどうかは、 x {\displaystyle x} 、 y {\displaystyle y} 、 z {\displaystyle z} が分からなくても、式 e ( g x , g y ) = e ( g , g z ) {\displaystyle e(g^{x},g^{y})=e(g,g^{z})} によって確認できる。これにより、DDH問題は容易に解けることがわかる。
※この「ペアリング関数」の解説は、「ボネ・リン・シャチャム署名」の解説の一部です。
「ペアリング関数」を含む「ボネ・リン・シャチャム署名」の記事については、「ボネ・リン・シャチャム署名」の概要を参照ください。
- ペアリング関数のページへのリンク
