はじめに

ペアリング暗号ライブラリ mcl を使って電子署名を実装します。
ペアリングを用いた電子署名には、BLS署名などがあります。
この記事ではBGLS署名を実装します。

mclの導入方法、ペアリングとは？については光成さんが解説しているのでそちらをご参照下さい。

BGLS署名

BGLS署名は、BLS署名の著者(Boneh, Lynn, Shacham)とGentryが提案した集約署名です。
mclではBLS署名のサンプルがあるため、これを加工してBGLS署名を実装します。

集約署名

集約署名（aggregate signature）とは、複数の署名を１つに集約することのできる署名方式です。
集約される署名は、複数の異なる文書に対して作成されています。

集約署名の登場人物

集約署名では、署名者、集約者、検証者がいます。
それぞれの役割は次のようになっています。

署名者：署名鍵を用いて文書の署名を生成する。
集約者：（複数の）署名を集約し、集約署名を作成する。
検証者：（集約）署名を受け取り、文書と検証鍵とともに用いて署名が有効/無効を検証する。

BGLS署名の実装

記号の準備

（光成さんのBLS署名の記事を引用しています）
まずアルゴリズムに必要な記号を用意します。

$r$ : 素数
$r$ 個の要素からなる巡回群 $G_1$, $G_2$, $G_T$
$e:G_1\times G_2 \rightarrow G_T $ :　ペアリング
文字列からG1へのハッシュ関数 $H : \bigl\{文字列\bigr\} \rightarrow G_1$
$Q$ : $G_2$上の点（共有パラメータ）

BGLS署名のアルゴリズム

ここでは、署名者が$n$人いる場合を考えます。

【鍵生成】：署名者 $i$ は、0以上$r$未満の乱数$s_i$を一つ取り秘密鍵とします。公開鍵は$s_iQ$です。
【署名】：署名者 $i$ は、文書$m_i$に対してそのハッシュ値$H(m_i)$をとり、秘密鍵$s_i$倍して、署名$\sigma_i=s_i H(m_i)$を作ります。
【検証】：検証者は、文書$m_i$と署名$\sigma_i$を受け取り、自分でハッシュ値$H(m_i)$を計算し公開鍵$s_iQ$を使って$$e(\sigma_i,Q)=e(H(m_i),s_iQ)$$
が成り立つかどうかを確認します。成立するなら署名は有効、そうでなければ無効です。
【集約】：集約者は、署名の集合 $\left\{\sigma_1,\ldots,\sigma_n\right\}$ を受け取り、集約署名$$\sigma=\sum_{i=1}^n\sigma_i$$
を生成します。 (※指摘コメント頂き修正しました)
【集約検証】：検証者は、文書$\left\{m_1,\ldots,m_n\right\}$と公開鍵$\left\{s_1Q,\ldots,s_nQ\right\}$と集約署名$\sigma$を受け取ります。
$\left\{m_1,\ldots,m_n\right\}$が全て異なっていて、
$$e(\sigma,Q)=\prod_{i=1}^ne(H(m_i),s_iQ)$$
が成り立つかどうかを確認します。成立するなら集約署名は有効、そうでなければ無効です。

実装したコード

署名者、検証者をclassで定義しています。
また、署名者数$n$は実行時に入力します。
文書$m_i$は適当に決めています。

my_aggregate.cpp

#include <mcl/bn256.hpp>
#include <iostream>

//my includes
#include <vector>
#include <map>
#include <time.h>

using namespace mcl::bn256;

class User{
	public:
		std::string m;
		G1 sig;
		G2 pub_key;

		void KeyGen(const G2& Q){
			sec_key.setRand();
			G2::mul(pub_key, Q, sec_key);
		}
		void Sign(const G1& Hm){
			G1::mul(sig, Hm, sec_key);
		}

	private:
		Fr sec_key;
};

class Aggregator{
	public:
		std::vector<User> users;
		G1 agg_signatures;
};


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


void Agg(G1& agg_sig, std::vector<G1>& sigs){
	int n = sigs.size();
	agg_sig = sigs[0];
	for(int i=1;i<n;i++){
		G1::add(agg_sig, agg_sig, sigs[i]);
	}
	
}

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

bool AggVerify(G1& agg_sig, const G2& Q, const std::vector<G2> pubs, const std::vector<std::string> msgs)
{
	int n = msgs.size();
	std::map<std::string, int> distinct;
	for(int i=0;i<n;i++){
		distinct[msgs[i]] = i;
	}
	if(distinct.size()!=n){
		return false;
	}


	Fp12 e1, e2;
	G1 Hm;
	pairing(e1, agg_sig, Q); // e1 = e(sign, Q)
	Hash(Hm, msgs[0]);
	pairing(e2, Hm, pubs[0]); // e2 = e(Hm, sQ)
	
	for(int i=1;i<n;i++){
		Fp12 e;
		Hash(Hm, msgs[i]);
		pairing(e, Hm, pubs[i]); // e2 = e(Hm, sQ)
		Fp12::mul(e2, e2, e);
	}
	
	return e1 == e2;
}


int main(int argc, char *argv[])
{
	std::string m = argc == 1 ? "hello mcl" : argv[1];

	// setup parameter
	initPairing();
	G2 Q;
	mapToG2(Q, 1);

	
	Aggregator agg;

	int num;
	std::cin >> num;

	std::vector<std::string> messages;
	std::vector<G1> signatures;
	std::vector<G2> pubkeys;

	// generate secret key and public key
	for(int i=0;i<num;i++){
		User usr;
		std::string si = std::to_string(i);
		usr.m = m+si;
		usr.KeyGen(Q);

		messages.push_back(usr.m);
		pubkeys.push_back(usr.pub_key);

		agg.users.push_back(usr);
	}	

	// sign
	for(int i=0;i<num;i++){
		G1 Hm;
		Hash(Hm, agg.users[i].m);
		agg.users[i].Sign(Hm);
		signatures.push_back(agg.users[i].sig);
	}

	/*
	for(int i=0;i<num;i++){
		std::cout << "message " << i << " : " << agg.users[i].m << std::endl;
		std::cout << "pub_key " << i << " : " << agg.users[i].pub_key << std::endl;
		std::cout << "Signature " << i << " : " << agg.users[i].sig << std::endl;
	}
	*/
	
	//Aggregator agg
	clock_t start = clock();
	Agg(agg.agg_signatures, signatures);

	bool aggok2 = AggVerify(agg.agg_signatures, Q, pubkeys, messages);
	clock_t end = clock();
	std::cout << "AggVerification time : " << (double)(end-start)/CLOCKS_PER_SEC << std::endl;
	std::cout << "verify agg " << (aggok2 ? "ok" : "ng") << std::endl;

	start = clock();
	for(int i=0;i<num;i++){
		User u = agg.users[i];
		bool ok = Verify(u.sig, Q, u.pub_key, u.m);
		if(!ok){
			std::cout << "ng" << std::endl;
			exit(0);
		}
	}
	end = clock();
	std::cout << "NormalVerification time : " << (double)(end-start)/CLOCKS_PER_SEC << std::endl;
	std::cout << "all ok" << std::endl;

}

実際に実行してみましょう。

$ make bin/my_aggregate.exe

$ bin/my_aggregate.exe
 50 (←nの値を入力)
AggVerification time : 0.022148
verify agg ok
NormalVerification time : 0.039777
all ok
$

実行できました。

集約署名の利点・欠点

集約署名では、送信する署名長や検証時間についての効率性が利点となっています。

実際、BGLS署名では、署名長について$n$個から$1$個ぶんの署名長になり、検証時間については$n$個の署名検証に必要なペアリング演算回数が$2n$回（3.を$n$回実行）から$n+1$回(5.で左辺1回右辺$n$回)に削減できています。

一方、集約される署名集合の中に無効なものが1つでも混じっている場合、生成される集約署名も無効となる（他の正当な署名がムダになってしまう）という欠点もあります。これについて対処している集約署名方式もありますが、今回は扱わないことにします。

おわりに

本記事では、ペアリング暗号ライブラリを用いて集約署名の一つであるBGLS署名を実装しました。