ボネ・リン・シャチャム署名
暗号理論において、ボネ・リン・シャチャム (BLS) 署名方式は、署名検証にペアリングと呼ばれる双線型写像を用いている署名方式である。署名は楕円曲線の1つの群要素(楕円曲線上の1つの点)で表される。楕円曲線上の群はindex calculus攻撃に対して耐性があるため、同じ安全性レベルを持つRSA署名などに比べて署名長が短いという利点を持つ。このため、BLS署名は「short signatures」や「BLSのshort signatures」とも呼ばれる。この署名方式は、証明可能安全性を持ち、ランダムオラクルとギャップ ディフィー・ヘルマン問題の困難性の元で、選択メッセージ攻撃に対する存在的偽造不可能性が証明されている。
双線型性:任意の 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問題は容易に解けることがわかる。