ボネ・リン・シャチャム署名
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)} は効率的に計算可能
鍵生成アルゴリズムは、まず、区間[0, r − 1]からランダムな整数 x {\displaystyle x} を選ぶ。秘密鍵(署名鍵)は x {\displaystyle x} である。公開される公開鍵(検証鍵)は g x {\displaystyle g^{x}} である。また、 H : { 0 , 1 } ∗ → G {\displaystyle H:\{0,1\}^{*}\to G} を暗号学的ハッシュ関数とする。