ボネ・リン・シャチャム署名

暗号理論において、ボネ・リン・シャチャム (BLS) 署名方式は、署名検証にペアリングと呼ばれる双線型写像を用いている署名方式である。署名は楕円曲線の１つの群要素（楕円曲線上の１つの点）で表される。楕円曲線上の群はindex calculus攻撃に対して耐性があるため、同じ安全性レベルを持つRSA署名などに比べて署名長が短いという利点を持つ。このため、BLS署名は「short signatures」や「BLSのshort signatures」とも呼ばれる。この署名方式は、証明可能安全性を持ち、ランダムオラクルとギャップ ディフィー・ヘルマン問題の困難性の元で、選択メッセージ攻撃に対する存在的偽造不可能性が証明されている。
ペアリング関数.
BLS署名は、Computational Diffie-Hellman問題（CDH）は困難であるがDecisional Diffie-Hellman問題 (DDH) は容易に解けるような群を利用している。このような性質を持つ群は、非退化かつ効率的に計算可能な双線型写像によって得ることができる。
formula_1とformula_2を、同じ素数の位数formula_3を持つ乗法群とし、formula_4を、群formula_1の生成元とする。formula_1上のCDH問題は困難であるとしよう。つまり、インスタンスformula_7が与えられたとき、formula_8を計算するのは難しい。
関数formula_9を、
という性質を満たす関数（ペアリング関数）とする。直感的に、ペアリング関数formula_17は、formula_1上のCDH問題の解決の助けにはならず、このような関数が存在しても、CDH問題を解くことは困難であると推測できる。一方、DDH問題のインスタンスformula_19が与えられたとき、formula_20が成り立つかどうかは、formula_21、formula_22、formula_23が分からなくても、式formula_24によって確認できる。これにより、DDH問題は容易に解けることがわかる。
署名方式.
デジタル署名方式は、鍵生成、署名生成、署名検証の３つのアルゴリズムからなる。
鍵生成.
鍵生成アルゴリズムは、まず、区間[0, "r" − 1]からランダムな整数formula_21を選ぶ。秘密鍵（署名鍵）はformula_21である。公開される公開鍵（検証鍵）はformula_27である。また、formula_28を暗号学的ハッシュ関数とする。
署名生成.
署名鍵formula_21と署名したいメッセージformula_30が与えられたとき、まず、formula_30のハッシュ値formula_32を計算する。そして、署名formula_33を出力する。
署名検証.
メッセージがformula_30、署名がformula_35、署名者の公開鍵がformula_27であるとき、式formula_37が成り立てば、署名は正しい署名であると検証される。