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

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

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

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

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

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

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

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

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

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

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

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

• Ben Lynn's PBC Library

表 話 編 歴 公開鍵暗号 アルゴリズム Cramer-Shoup暗号 ディフィー・ヘルマン鍵共有（楕円DH） Digital Signature Algorithm（楕円DSA） エドワーズ曲線デジタル署名アルゴリズム ElGamal暗号（ElGamal署名） EPOC (暗号) Merkle-Hellmanナップサック暗号 NTRU暗号 Paillier暗号 Rabin暗号 RSA暗号 ランポート署名 理論 離散対数 素因数分解 楕円曲線暗号 標準化 CRYPTREC IEEE P1363（英語版） NESSIE NSA Suite B（英語版） CNSA 関連項目 デジタル署名 Optimal Asymmetric Encryption Padding 指紋 公開鍵基盤

表 話 編 歴 暗号 暗号史 暗号解読 Cryptography portal en:Outline of cryptography 共通鍵暗号 ブロック暗号 ストリーム暗号 暗号利用モード 公開鍵暗号 暗号学的ハッシュ関数 メッセージ認証コード 認証付き暗号 乱数生成器 ステガノグラフィー

カテゴリ