design IF again

3 files changed, 163 insertions, 126 deletions

diff --git a/include/bls.hpp b/include/bls.hpp
index b2c8e71..31b3d1c 100644
--- a/include/bls.hpp
+++ b/include/bls.hpp
@@ -17,7 +17,6 @@ namespace impl {
 struct PublicKey;
 struct PrivateKey;
 struct Sign;
-struct MasterPublicKey;
 
 } // bls::impl
 
@@ -32,11 +31,30 @@ struct MasterPublicKey;
 	verify ; e(sQ, H(m)) = e(Q, s H(m))
 */
 
+/*
+	initialize this library
+	call this once before using the other method
+*/
+void init();
+
 class Sign;
 class PublicKey;
 class PrivateKey;
 
-void init();
+typedef std::vector<Sign> SignVec;
+typedef std::vector<PublicKey> PublicKeyVec;
+typedef std::vector<PrivateKey> PrivateKeyVec;
+
+/*
+	[s_0, s_1, ..., s_{k-1}]
+	s_0 is original private key
+*/
+typedef std::vector<PrivateKey> MasterPrivateKey;
+/*
+	[s_0 Q, ..., s_{k-1} Q]
+	Q is global fixed parameter
+*/
+typedef std::vector<PublicKey> MasterPublicKey;
 
 class Sign {
 	impl::Sign *self_;
@@ -57,6 +75,10 @@ public:
 	friend std::istream& operator>>(std::istream& is, Sign& s);
 	bool verify(const PublicKey& pub, const std::string& m) const;
 	/*
+		verify self(pop) with pub
+	*/
+	bool verify(const PublicKey& pub) const;
+	/*
 		recover sign from k signVec
 	*/
 	void recover(const std::vector<Sign>& signVec);
@@ -67,28 +89,6 @@ public:
 };
 
 /*
-	(Q, sQ, c_1 Q, ..., c_{k-1}Q)
-	s = c_0 ; private key
-	c_1, ..., c_{k-1} ; secret sharing
-	f(x) = c_0 + c_1 x + ... + c_{k-1} x^{k-1}
-	f(id) ; private key for user id(>0)
-*/
-class MasterPublicKey {
-	impl::MasterPublicKey *self_;
-	friend class PrivateKey;
-	friend class PublicKey;
-public:
-	MasterPublicKey();
-	~MasterPublicKey();
-	MasterPublicKey(const MasterPublicKey& rhs);
-	MasterPublicKey& operator=(const MasterPublicKey& rhs);
-	bool operator==(const MasterPublicKey& rhs) const;
-	bool operator!=(const MasterPublicKey& rhs) const { return !(*this == rhs); }
-	friend std::ostream& operator<<(std::ostream& os, const MasterPublicKey& mpk);
-	friend std::istream& operator>>(std::istream& is, MasterPublicKey& mpk);
-};
-
-/*
 	sQ ; public key
 */
 class PublicKey {
@@ -98,6 +98,8 @@ class PublicKey {
 	friend class Sign;
 	template<class G, class T>
 	friend void LagrangeInterpolation(G& r, const T& vec);
+	template<class T, class G>
+	friend struct Wrap;
 public:
 	PublicKey();
 	~PublicKey();
@@ -108,14 +110,15 @@ public:
 	int getId() const { return id_; }
 	friend std::ostream& operator<<(std::ostream& os, const PublicKey& pub);
 	friend std::istream& operator>>(std::istream& is, PublicKey& pub);
+	void getStr(std::string& str) const;
 	/*
-		recover publicKey from k pubVec
+		set public for id from mpk
 	*/
-	void recover(const std::vector<PublicKey>& pubVec);
+	void set(const MasterPublicKey& mpk, int id);
 	/*
-		validate self by MasterPublicKey
+		recover publicKey from k pubVec
 	*/
-	bool isValid(const MasterPublicKey& mpk) const;
+	void recover(const std::vector<PublicKey>& pubVec);
 	/*
 		add public key only if id_ == 0
 	*/
@@ -130,6 +133,8 @@ class PrivateKey {
 	int id_; // master if id_ = 0, shared if id_ > 0
 	template<class G, class T>
 	friend void LagrangeInterpolation(G& r, const T& vec);
+	template<class T, class G>
+	friend struct Wrap;
 public:
 	PrivateKey();
 	~PrivateKey();
@@ -140,14 +145,24 @@ public:
 	int getId() const { return id_; }
 	friend std::ostream& operator<<(std::ostream& os, const PrivateKey& prv);
 	friend std::istream& operator>>(std::istream& is, PrivateKey& prv);
+	/*
+		make a private key for id = 0
+	*/
 	void init();
 	void getPublicKey(PublicKey& pub) const;
 	void sign(Sign& sign, const std::string& m) const;
 	/*
-		k-out-of-n secret sharing of privateKey
-		set verifier if mpk is not 0
+		make Pop(Proof of Possesion)
+	*/
+	void getPop(Sign& pop, const PublicKey& pub) const;
+	/*
+		make [s_0, ..., s_{k-1}] to prepare k-out-of-n secret sharing
 	*/
-	void share(std::vector<PrivateKey>& prvVec, int n, int k, MasterPublicKey *mpk = 0);
+	void getMasterPrivateKey(MasterPrivateKey& msk, int k) const;
+	/*
+		set a private key for id > 0 from msk
+	*/
+	void set(const MasterPrivateKey& msk, int id);
 	/*
 		recover privateKey from k prvVec
 	*/
@@ -158,6 +173,16 @@ public:
 	void add(const PrivateKey& rhs);
 };
 
+/*
+	make master public key [s_0 Q, ..., s_{k-1} Q] from msk
+*/
+void getMasterPublicKey(MasterPublicKey& mpk, const MasterPrivateKey& msk);
+
+/*
+	make pop from msk and mpk
+*/
+void getPopVec(std::vector<Sign>& popVec, const MasterPrivateKey& msk, const MasterPublicKey& mpk);
+
 inline Sign operator+(const Sign& a, const Sign& b) { Sign r(a); r.add(b); return r; }
 inline PublicKey operator+(const PublicKey& a, const PublicKey& b) { PublicKey r(a); r.add(b); return r; }
 inline PrivateKey operator+(const PrivateKey& a, const PrivateKey& b) { PrivateKey r(a); r.add(b); return r; }
diff --git a/src/bls.cpp b/src/bls.cpp
index 949cdf6..b887469 100644
--- a/src/bls.cpp
+++ b/src/bls.cpp
@@ -65,8 +65,8 @@ static void HashAndMapToG1(G1& P, const std::string& m)
 	mapToG1(P, t);
 }
 
-template<class T, class G>
-void evalPoly(G& y, const T& x, const std::vector<G>& c)
+template<class T, class G, class Vec>
+void evalPoly(G& y, const T& x, const Vec& c)
 {
 	if (c.size() < 2) throw cybozu::Exception("bls:evalPoly:bad size") << c.size();
 	y = c[c.size() - 1];
@@ -76,6 +76,17 @@ void evalPoly(G& y, const T& x, const std::vector<G>& c)
 	}
 }
 
+template<class T, class G>
+struct Wrap {
+	const std::vector<T> *pv;
+	Wrap(const std::vector<T>& v) : pv(&v) {}
+	const G& operator[](size_t i) const
+	{
+		return (*pv)[i].self_->get();
+	}
+	size_t size() const { return pv->size(); }
+};
+
 struct Polynomial {
 	FrVec c; // f[x] = sum_{i=0}^{k-1} c[i] x^i
 	void init(const Fr& s, int k)
@@ -166,10 +177,6 @@ inline bool Sign::verify(const PublicKey& pub, const std::string& m) const
 	return e1 == e2;
 }
 
-struct MasterPublicKey {
-	std::vector<G2> vecR;
-};
-
 struct PrivateKey {
 	Fr s;
 	const Fr& get() const { return s; }
@@ -234,6 +241,12 @@ bool Sign::verify(const PublicKey& pub, const std::string& m) const
 {
 	return self_->verify(*pub.self_, m);
 }
+bool Sign::verify(const PublicKey& pub) const
+{
+	std::string str;
+	pub.getStr(str);
+	return verify(pub, str);
+}
 void Sign::recover(const std::vector<Sign>& signVec)
 {
 	G1 sHm;
@@ -248,53 +261,6 @@ void Sign::add(const Sign& rhs)
 	self_->sHm += rhs.self_->sHm;
 }
 
-MasterPublicKey::MasterPublicKey()
-	: self_(new impl::MasterPublicKey())
-{
-}
-
-MasterPublicKey::~MasterPublicKey()
-{
-	delete self_;
-}
-
-MasterPublicKey::MasterPublicKey(const MasterPublicKey& rhs)
-	: self_(new impl::MasterPublicKey(*rhs.self_))
-{
-}
-
-MasterPublicKey& MasterPublicKey::operator=(const MasterPublicKey& rhs)
-{
-	*self_ = *rhs.self_;
-	return *this;
-}
-
-bool MasterPublicKey::operator==(const MasterPublicKey& rhs) const
-{
-	return self_->vecR == rhs.self_->vecR;
-}
-
-std::ostream& operator<<(std::ostream& os, const MasterPublicKey& mpk)
-{
-	const size_t n = mpk.self_->vecR.size();
-	os << n;
-	for (size_t i = 0; i < n; i++) {
-		os << '\n' << mpk.self_->vecR[i];
-	}
-	return os;
-}
-
-std::istream& operator>>(std::istream& is, MasterPublicKey& mpk)
-{
-	size_t n;
-	is >> n;
-	mpk.self_->vecR.resize(n);
-	for (size_t i = 0; i < n; i++) {
-		is >> mpk.self_->vecR[i];
-	}
-	return is;
-}
-
 PublicKey::PublicKey()
 	: self_(new impl::PublicKey())
 	, id_(0)
@@ -334,6 +300,20 @@ std::istream& operator>>(std::istream& is, PublicKey& pub)
 	return is >> pub.id_ >> pub.self_->sQ;
 }
 
+void PublicKey::getStr(std::string& str) const
+{
+	std::ostringstream os;
+	os << *this;
+	str = os.str();
+}
+
+void PublicKey::set(const MasterPublicKey& mpk, int id)
+{
+	Wrap<PublicKey, G2> w(mpk);
+	evalPoly(self_->sQ, Fr(id), w);
+	id_ = id;
+}
+
 void PublicKey::recover(const std::vector<PublicKey>& pubVec)
 {
 	G2 sQ;
@@ -342,13 +322,6 @@ void PublicKey::recover(const std::vector<PublicKey>& pubVec)
 	id_ = 0;
 }
 
-bool PublicKey::isValid(const MasterPublicKey& mpk) const
-{
-	G2 v;
-	evalPoly(v, Fr(id_), mpk.self_->vecR);
-	return v == self_->sQ;
-}
-
 void PublicKey::add(const PublicKey& rhs)
 {
 	if (id_ != 0 || rhs.id_ != 0) throw cybozu::Exception("bls:PublicKey:add:bad id") << id_ << rhs.id_;
@@ -384,6 +357,16 @@ bool PrivateKey::operator==(const PrivateKey& rhs) const
 	return id_ == rhs.id_ && self_->s == rhs.self_->s;
 }
 
+std::ostream& operator<<(std::ostream& os, const PrivateKey& prv)
+{
+	return os << prv.id_ << ' ' << prv.self_->s;
+}
+
+std::istream& operator>>(std::istream& is, PrivateKey& prv)
+{
+	return is >> prv.id_ >> prv.self_->s;
+}
+
 void PrivateKey::init()
 {
 	self_->init();
@@ -395,40 +378,34 @@ void PrivateKey::getPublicKey(PublicKey& pub) const
 	pub.id_ = id_;
 }
 
-std::ostream& operator<<(std::ostream& os, const PrivateKey& prv)
+void PrivateKey::sign(Sign& sign, const std::string& m) const
 {
-	return os << prv.id_ << ' ' << prv.self_->s;
+	self_->sign(*sign.self_, m);
+	sign.id_ = id_;
 }
 
-std::istream& operator>>(std::istream& is, PrivateKey& prv)
+void PrivateKey::getPop(Sign& pop, const PublicKey& pub) const
 {
-	return is >> prv.id_ >> prv.self_->s;
+	std::string m;
+	pub.getStr(m);
+	sign(pop, m);
 }
 
-void PrivateKey::sign(Sign& sign, const std::string& m) const
+void PrivateKey::getMasterPrivateKey(MasterPrivateKey& msk, int k) const
 {
-	self_->sign(*sign.self_, m);
-	sign.id_ = id_;
+	if (k <= 1) throw cybozu::Exception("bls:PrivateKey:getMasterPrivateKey:bad k") << k;
+	msk.resize(k);
+	msk[0] = *this;
+	for (int i = 1; i < k; i++) {
+		msk[i].init();
+	}
 }
 
-void PrivateKey::share(std::vector<PrivateKey>& prvVec, int n, int k, MasterPublicKey *mpk)
+void PrivateKey::set(const MasterPrivateKey& msk, int id)
 {
-	if (id_ != 0) throw cybozu::Exception("bls:PrivateKey:share:already shared") << id_;
-	if (n <= 0 || k <= 0 || k > n) throw cybozu::Exception("bls:PrivateKey:share:bad n, k") << n << k;
-	Polynomial poly;
-	poly.init(self_->s, k);
-	prvVec.resize(n);
-	for (int i = 0; i < n; i++) {
-		int id = i + 1;
-		poly.eval(prvVec[i].self_->s, id);
-		prvVec[i].id_ = id;
-	}
-	if (mpk == 0) return;
-	std::vector<G2>& vecR = mpk->self_->vecR;
-	vecR.resize(k);
-	for (size_t i = 0; i < vecR.size(); i++) {
-		G2::mul(vecR[i], getQ(), poly.c[i]);
-	}
+	Wrap<PrivateKey, Fr> w(msk);
+	evalPoly(self_->s, id, w);
+	id_ = id;
 }
 
 void PrivateKey::recover(const std::vector<PrivateKey>& prvVec)
@@ -445,4 +422,24 @@ void PrivateKey::add(const PrivateKey& rhs)
 	self_->s += rhs.self_->s;
 }
 
+void getMasterPublicKey(MasterPublicKey& mpk, const MasterPrivateKey& msk)
+{
+	mpk.resize(msk.size());
+	for (size_t i = 0; i < msk.size(); i++) {
+		msk[i].getPublicKey(mpk[i]);
+	}
+}
+
+void getPopVec(std::vector<Sign>& popVec, const MasterPrivateKey& msk, const MasterPublicKey& mpk)
+{
+	if (msk.size() != mpk.size()) throw cybozu::Exception("bls:getPopVec:bad size") << msk.size() << mpk.size();
+	const size_t n = msk.size();
+	popVec.resize(n);
+	std::string m;
+	for (size_t i = 0; i < n; i++) {
+		mpk[i].getStr(m);
+		msk[i].sign(popVec[i], m);
+	}
+}
+
 } // bls
diff --git a/test/bls_test.cpp b/test/bls_test.cpp
index 9cacc05..08da1a2 100644
--- a/test/bls_test.cpp
+++ b/test/bls_test.cpp
@@ -46,8 +46,14 @@ CYBOZU_TEST_AUTO(k_of_n)
 	prv0.getPublicKey(pub0);
 	CYBOZU_TEST_ASSERT(s0.verify(pub0, m));
 
-	std::vector<bls::PrivateKey> allPrvVec;
-	prv0.share(allPrvVec, n, k);
+	bls::MasterPrivateKey msk;
+	prv0.getMasterPrivateKey(msk, k);
+
+	std::vector<bls::PrivateKey> allPrvVec(n);
+	for (int i = 0; i < n; i++) {
+		int id = i + 1;
+		allPrvVec[i].set(msk, id);
+	}
 	CYBOZU_TEST_EQUAL(allPrvVec.size(), n);
 	for (int i = 0; i < n; i++) {
 		CYBOZU_TEST_EQUAL(allPrvVec[i].getId(), i + 1);
@@ -163,24 +169,33 @@ CYBOZU_TEST_AUTO(k_of_n)
 	}
 }
 
-CYBOZU_TEST_AUTO(MasterPublicKey)
+CYBOZU_TEST_AUTO(MasterPrivateKey)
 {
-	const int n = 6;
 	const int k = 3;
+	const int n = 6;
 	bls::PrivateKey prv0;
 	prv0.init();
 	bls::PublicKey pub0;
 	prv0.getPublicKey(pub0);
-	std::vector<bls::PrivateKey> prvVec;
+	bls::MasterPrivateKey msk;
+	prv0.getMasterPrivateKey(msk, k);
+
 	bls::MasterPublicKey mpk;
-	prv0.share(prvVec, n, k, &mpk);
-	CYBOZU_TEST_ASSERT(pub0.isValid(mpk));
-	for (size_t i = 0; i < prvVec.size(); i++) {
+	bls::getMasterPublicKey(mpk, msk);
+
+	const int idTbl[n] = {
+		3, 5, 193, 22, 15
+	};
+	bls::PrivateKeyVec prvVec(n);
+	bls::PublicKeyVec pubVec(n);
+	for (int i = 0; i < n; i++) {
+		int id = idTbl[i];
+		prvVec[i].set(msk, id);
+		prvVec[i].getPublicKey(pubVec[i]);
 		bls::PublicKey pub;
-		prvVec[i].getPublicKey(pub);
-		CYBOZU_TEST_ASSERT(pub.isValid(mpk));
+		pub.set(mpk, id);
+		CYBOZU_TEST_EQUAL(pubVec[i], pub);
 	}
-	streamTest(mpk);
 }
 
 CYBOZU_TEST_AUTO(add)