PROFILPELAJAR.COM

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

ペアリング関数

BLS署名は、Computational Diffie-Hellman問題（CDH）は困難であるがDecisional Diffie-Hellman問題 (DDH) は容易に解けるような群を利用している。このような性質を持つ群は、非退化かつ効率的に計算可能な双線型写像によって得ることができる。

$G$ と $G_{T}$ を、同じ素数の位数 $r$ を持つ乗法群とし、 $g$ を、群 $G$ の生成元とする。 $G$ 上のCDH問題は困難であるとしよう。つまり、インスタンス $(g,g^{x},g^{y})$ が与えられたとき、 $g^{xy}$ を計算するのは難しい。

関数 $e\colon G\times G\rightarrow G_{T}$ を、

非退化： $e(g,g)$ は $G_{T}$ の単位元ではない
$a,b\in G$ が与えられたとき、 $e(a,b)$ は効率的に計算可能
双線型性：任意の $a,b\in G$ と任意の自然数 $m,n$ に対して、 $e(a^{m},b^{n})=e(a,b)^{mn}$ が成り立つ

という性質を満たす関数（ペアリング関数）とする。直感的に、ペアリング関数 $e$ は、 $G$ 上のCDH問題の解決の助けにはならず、このような関数が存在しても、CDH問題を解くことは困難であると推測できる。一方、DDH問題のインスタンス $(g,g^{x},g^{y},g^{z})$ が与えられたとき、 $g^{z}=g^{xy}$ が成り立つかどうかは、 $x$ 、 $y$ 、 $z$ が分からなくても、式 $e(g^{x},g^{y})=e(g,g^{z})$ によって確認できる。これにより、DDH問題は容易に解けることがわかる。

署名方式

デジタル署名方式は、鍵生成、署名生成、署名検証の３つのアルゴリズムからなる。

鍵生成

鍵生成アルゴリズムは、まず、区間[0, r − 1]からランダムな整数 $x$ を選ぶ。秘密鍵（署名鍵）は $x$ である。公開される公開鍵（検証鍵）は $g^{x}$ である。また、 $H:\{0,1\}^{*}\to G$ を暗号学的ハッシュ関数とする。

署名生成

署名鍵 $x$ と署名したいメッセージ $m$ が与えられたとき、まず、 $m$ のハッシュ値 $h=H(m)$ を計算する。そして、署名 $\sigma =h^{x}$ を出力する。

署名検証

メッセージが $m$ 、署名が $\sigma$ 、署名者の公開鍵が $g^{x}$ であるとき、式 $e(\sigma ,g)=e(H(m),g^{x})$ が成り立てば、署名は正しい署名であると検証される。

性質

シンプルな閾値署名が可能。
集約署名：複数のメッセージに対して複数の署名者によって作成された複数の署名を、一つの署名に集約することが可能。^[3]
確定的：一つの鍵と一つのメッセージに対して、正当な署名は一つだけしか存在ない。この性質は、RSA-PKCS#1 v1.5 や EdDSAと同じであり、確率的署名であるRSA-PSS, DSA, ECDSA, Schnorr署名とは異なる。

脚注

^ ただし、ペアリングのターゲット群 $G_{T}$ においては同様の攻撃ができてしまうため、注意が必要。
^ Dan Boneh; Ben Lynn; Hovav Shacham (2004). “Short Signatures from the Weil Pairing”. Journal of Cryptology 17 (4): 297–319. doi:10.1007/s00145-004-0314-9.
^ D. Boneh, C. Gentry, H. Shacham, and B. Lynn [1] In proceedings of Eurocrypt 2003, LNCS 2656, pp. 416-432, 2003