BBS+ Signature Scheme理解メモ (1) - 署名・検証アルゴリズム

DID・VC界隈で最近話題のBBS+ Signature Schemeについて理解を深めるためのメモです。
BBS+について全部解説しようとすると1記事には収まらないため、複数回に分けて書くことにしました。
第1回はBBS+の概要、及び署名アルゴリズムの詳細について解説します。

概要

BBS+ Signature Schemeはマルチメッセージに特化した署名スキームで、その最大の特徴はZKPによるメッセージの選択的開示のサポートです。その性質から、検証可能クレデンシャル(VC)の署名形式として有用ではないかと注目を集めています。

選択的開示 (selective disclosure)

通常の署名形式では、署名はメッセージ全体に対して作成されます。検証者は、メッセージ全体を知らなければ、署名が正しいことを検証できません。

これに対し、メッセージの一部だけを開示し、それが正しく署名されたメッセージの部分集合であることを証明することを、メッセージの選択的開示と呼びます。BBS+の選択的開示アルゴリズムでは、検証者はメッセージ全てを知ることも、署名の値そのものを知ることもありません。その代わりに、検証者は対応するゼロ知識証明(ZKP)を検証することで、開示されたメッセージの正しさを判断することができます。

例として、学生証と学割キャンペーンの関係を考えてみましょう。

1. 大学は学生に対し、毎年デジタルな学生証を発行する。それは大学によってデジタルな署名がなされている。
2. 学割キャンペーンはサービスのユーザーに対し、特定の大学の学生であることの証明を要求する。
3. ユーザーは学割を適用してほしいが、必要以上の個人情報をサービスに渡したくはない。

この場合、学生証をそのままサービスに提示してしまうのが従来の署名検証の方法、一部の情報だけをサービスに提示し、それが学生証に由来することを証明するのが選択的開示、ということになります。

署名アルゴリズム

選択的開示のアルゴリズムの前に、今回はまずBBS+の署名がどのように生成されるのかをざっくり解説します。この署名生成アルゴリズムが選択的開示のZKPでどのように効いてくるのかについては次回以降に回したいと思います。

鍵生成

ある有限体上の楕円曲線の群構造$G_1$, $G_2$について、その位数が$r$であるとします。
また、$P_1$, $P_2$はそれぞれ$G_1$, $G_2$の生成元であるとします。

• 秘密鍵 $SK$ は $0 < SK < r$ であるようなランダムな整数です。
• 公開鍵 $w \in G_2$ を、$w = SK * P_2$ で定義します。

これに加えて、メッセージの個数が$L$であるとき、$L+1$個の$G_1$の元$h_i (i = 0, 1, ..., L)$を$w$から生成します。これらも公開鍵と呼びます。

• $h_i$は$w, i$から決定的に計算するため、$w$をshort form public keyと呼びます。
• $h_i$の具体的な計算にはhashを用いますが、本質ではないため詳細は省きます。$w$から有限個の$G_1$の元が生成できるという点が重要です。

署名の生成

L個のメッセージ$msg_1, msg_2, ..., msg_L$と鍵$SK, w, h_0, h_1, ..., h_L$から、次のように署名を生成します。

1. $0 < e, s < r$ を満たすランダムな整数 $e, s$ を定める。
2. $b = P_1 + h_0 * s + h_1 * msg_1 + ... + h_L * msg_L$ を計算する。
3. $A = b * (1 / (SK + e))$ を計算する。
4. $(A, e, s)$ の三組を署名とする。

乱数$s, e$はそれぞれソルトのように働きます。$b$はメッセージ・公開鍵・ソルトから計算できるダイジェスト値です。

署名の検証

署名を検証するためには、更に次の道具が必要です。

• 非退化双線型写像$E : G_1 \times G_2 \to GT$。$GT$は位数rの乗法群とする。

検証アルゴリズムは次のようになります。
1. 署名$(A, e, s)$、メッセージ$msg_1, ..., msg_L$、公開鍵$w, h_0, ..., h_L$ を入力とする。
1. $b = P_1 + h_0 * s + h_1 * msg_1 + ... + h_L * msg_L$ を計算する。
1. $C1 = E(A, w + P_2 * e)$とする。
1. $C2 = E(b, P_2)$とする。
1. $C1 = C2$であれば検証成功、そうでなければ検証失敗とする。

写像$E$の双線型性より、$A$が正しく生成されていれば $C_1 = E(A, w + P_2 * e) = E(b * (1 / (SK + e)), P_2 * (SK + e)) = E(b, P_2) = C2$ となるので、この検証過程が正しいことがわかります。

次回予告：ZKPによるメッセージの選択的開示

今回解説した署名の値$(A, e, s)$を直接検証するには、元の全メッセージを知っている必要があります。
学生証の例で言えば、学生証の保持者は自分の学生証の真贋を上記のアルゴリズムで検証することはできますが、選択的開示にはまた別のアルゴリズムが必要になります。

次回はこの選択的開示がゼロ知識証明(ZKP)でできること、その証明の構築には署名の値・全メッセージ・署名者の公開鍵さえ知っていれば良いことを示し、アルゴリズムの詳細を解説したいと思います。