初めに

今回はペアリングを用いたBLS署名を紹介して実装します。
この署名はTLSなどでよく使われる楕円曲線を用いた署名ECDSAと違って秘密分散と相性がよく、いろいろ面白いことができます。

BLS署名

BLS署名はBoneh, Lynn, Shachamが提案したペアリングを使った署名です。

記号の準備

まずアルゴリズムに必要な記号を用意します。
rを素数とし、r個の要素からなる巡回群G1, G2, GTと

e : G_1 \times G_2 \rightarrow G_T

というペアリングを考えます。ペアリングについてはペアリングの双線形性をmclを用いて確認するや『クラウドを支えるこれからの暗号技術』を参照してください。

そして文字列からG1へのハッシュ関数H : {文字列} → G1とG2の点Qを一つ固定し、みなで共有します。準備はこれで終わりです。

BLS署名のアルゴリズム

1. 鍵生成 : 0以上r未満の乱数sを一つ取り秘密鍵とします。公開鍵はsQです。
2. 署名 : メッセージmに対してそのハッシュ値H(m)をとり、秘密鍵s倍して署名s H(m)を作ります。
3. 検証 : メッセージmと署名σをもらった人は自分でハッシュ値H(m)を計算し公開鍵sQを使って

e(σ, Q) = e(H(m), sQ) 

が成り立つかどうかを確認します。成立するなら署名は正しく、そうでなければ不正です。

σが正しい署名のときはσ = s H(m)ですから、ペアリングの双線形性$e(aP, bQ)=e(P,Q)^{ab}$から

e(σ, Q) = e(s H(m), Q) = e(H(m), Q)^s = e(H(m), sQ)

となり等号が成り立ちます。
適切なパラメータの元では、秘密鍵xを知らない第三者がx H(m)を作れないと考えられています。

意外とシンプルなアルゴリズムなことに驚かれたでしょうか。これだけで署名になるのはちょっと不思議ですね。なんと署名時に乱数を使いません。確定的な署名アルゴリズムです。

BLS署名の実装

mclを使ってBLS署名を試してみましょう。

初期化

G2の点Qを固定します。G1, G2の点P, Qの設定と同じでもよいですが今回は違う方法でQを決めました。

bn256init();
G2 Q;
BN::mapToG2(Q, 1);

BN::mapToG2は0でない適当な整数をG2の元に割り当てるハッシュ関数です。決定的なので毎回同じ値になります。アルゴリズムはIndifferentiable Hashing to. Barreto–Naehrig Curvesを用いています。

鍵生成

0以上r未満の整数をランダムに選んで秘密鍵とします。乱数は暗号論的擬似乱数でなければなりません。C++11以降ならstd::random_deviceを使います。ただし規格的にはこの値が非決定的とは限らないので注意が必要です。

std::random_device rd;
Fr s;
s.setRand(rd);

Fr::setRandに乱数生成のインスタンスを渡すとそれを使って乱数を設定します。
公開鍵pubはQをs倍したものです。

G2 pub;
G2::mul(pub, Q, s); // pub = sQ

署名

まず文字列からG1へのハッシュ関数H : {文字列} → G1を作ります。
メッセージmのハッシュをとってFpの元を作り、それをもとにBN::mapToG1を使っ
てG1の元を作ります。

void Hash(G1& P, const std::string& m)
{
    Fp t;
    t.setMsg(m);
    BN::mapToG1(P, t);
}

この関数を使って署名します。

G1 Hm;
Hash(Hm, m);
G1::mul(sign, Hm, s); // sign = s H(m)

検証

最後にVerify関数を作りましょう。
公開鍵(Q, sQ = pub)と署名signとメッセージmから二つのペアリングを作り同じかどうかをみます。

bool Verify(const G1& sign, const G2& Q, const G2& pub, const std::string& m)
{
    Fp12 e1, e2;
    G1 Hm;
    Hash(Hm, m);
    BN::pairing(e1, sign, Q); // e1 = e(sign, Q)
    BN::pairing(e2, Hm, pub); // e2 = e(Hm, sQ)
    return e1 == e2;
}

全部を行うサンプルはbin/bls_sig.cppにあります。Linuxならmclのディレクトリで

make bin/bls_sig.exe

とすればビルドされます。

まとめと次回

今回はBLS署名の基本を紹介しました。

BLS署名はペアリングとハッシュ関数を除けば○○倍するという操作しかない実に簡単なアルゴリズムです。したがって容易に秘密分散と組み合わせられます。

そうすると、たとえば秘密鍵を100人に分散して配布し、それぞれが署名したものが50個集まれば、元の署名が復元できるといったことができます。
これはブロックチェーン系の多数決と相性がよいのでいろいろ面白いことができそうです。そのあたりについては次回（か次々回）紹介しましょう。