From 76d28310b055dd596f4cd67fc7de49624948a85f Mon Sep 17 00:00:00 2001 From: MITSUNARI Shigeo Date: Sun, 21 Aug 2016 15:34:52 +0900 Subject: design IF again --- include/bls.hpp | 87 ++++++++++++++++++---------- src/bls.cpp | 165 +++++++++++++++++++++++++++--------------------------- test/bls_test.cpp | 37 ++++++++---- 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 SignVec; +typedef std::vector PublicKeyVec; +typedef std::vector PrivateKeyVec; + +/* + [s_0, s_1, ..., s_{k-1}] + s_0 is original private key +*/ +typedef std::vector MasterPrivateKey; +/* + [s_0 Q, ..., s_{k-1} Q] + Q is global fixed parameter +*/ +typedef std::vector MasterPublicKey; class Sign { impl::Sign *self_; @@ -56,6 +74,10 @@ public: friend std::ostream& operator<<(std::ostream& os, const Sign& s); 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 */ @@ -66,28 +88,6 @@ public: void add(const Sign& rhs); }; -/* - (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 */ @@ -98,6 +98,8 @@ class PublicKey { friend class Sign; template friend void LagrangeInterpolation(G& r, const T& vec); + template + 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& 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& 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 friend void LagrangeInterpolation(G& r, const T& vec); + template + 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& 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& 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 -void evalPoly(G& y, const T& x, const std::vector& c) +template +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& c) } } +template +struct Wrap { + const std::vector *pv; + Wrap(const std::vector& 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 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& 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 w(mpk); + evalPoly(self_->sQ, Fr(id), w); + id_ = id; +} + void PublicKey::recover(const std::vector& pubVec) { G2 sQ; @@ -342,13 +322,6 @@ void PublicKey::recover(const std::vector& 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& 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& 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 w(msk); + evalPoly(self_->s, id, w); + id_ = id; } void PrivateKey::recover(const std::vector& 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& 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 allPrvVec; - prv0.share(allPrvVec, n, k); + bls::MasterPrivateKey msk; + prv0.getMasterPrivateKey(msk, k); + + std::vector 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 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) -- cgit v1.2.3