#pragma once
/**
	@file
	@brief somewhat homomorphic encryption with one-time multiplication, based on prime-order pairings
	@author MITSUNARI Shigeo(@herumi)
	see https://github.com/herumi/mcl/blob/master/misc/she/she.pdf
	@license modified new BSD license
	http://opensource.org/licenses/BSD-3-Clause

	David Mandell Freeman:
	Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups. EUROCRYPT 2010: 44-61
	http://theory.stanford.edu/~dfreeman/papers/subgroups.pdf
	this algorithm reduces public key size compared to the paper by Sakai's idea.

	BGN encryption
	http://theory.stanford.edu/~dfreeman/cs259c-f11/lectures/bgn
*/
#include <cmath>
#include <vector>
#include <iosfwd>
#ifndef MCLBN_FP_UNIT_SIZE
	#define MCLBN_FP_UNIT_SIZE 4
#endif
#if MCLBN_FP_UNIT_SIZE == 4
#include <mcl/bn256.hpp>
namespace mcl {
namespace bn_current = mcl::bn256;
}
#elif MCLBN_FP_UNIT_SIZE == 6
#include <mcl/bn384.hpp>
namespace mcl {
namespace bn_current = mcl::bn384;
}
#elif MCLBN_FP_UNIT_SIZE == 8
#include <mcl/bn512.hpp>
namespace mcl {
namespace bn_current = mcl::bn512;
}
#else
	#error "MCLBN_FP_UNIT_SIZE must be 4, 6, or 8"
#endif

#if CYBOZU_CPP_VERSION >= CYBOZU_CPP_VERSION_CPP11
#include <random>
#else
#include <cybozu/random_generator.hpp>
#endif
#include <mcl/window_method.hpp>

namespace mcl { namespace she {

namespace local {

#if CYBOZU_CPP_VERSION >= CYBOZU_CPP_VERSION_CPP11
typedef std::random_device RandomDevice;
static thread_local std::random_device g_rg;
#else
static cybozu::RandomGenerator g_rg;
#endif
#ifndef MCLSHE_WIN_SIZE
	#define MCLSHE_WIN_SIZE 10
#endif
const size_t winSize = MCLSHE_WIN_SIZE;

struct KeyCount {
	uint32_t key;
	int32_t count; // power
	bool operator<(const KeyCount& rhs) const
	{
		return key < rhs.key;
	}
	bool isSame(const KeyCount& rhs) const
	{
		return key == rhs.key && count == rhs.count;
	}
};

template<class G, bool = true>
struct InterfaceForHashTable : G {
	static G& castG(InterfaceForHashTable& x) { return static_cast<G&>(x); }
	static const G& castG(const InterfaceForHashTable& x) { return static_cast<const G&>(x); }
	void clear() { clear(castG(*this)); }
	void normalize() { normalize(castG(*this)); }
	static bool isOdd(const G& P) { return P.y.isOdd(); }
	static bool isZero(const G& P) { return P.isZero(); }
	static bool isSameX(const G& P, const G& Q) { return P.x == Q.x; }
	static uint32_t getHash(const G& P) { return uint32_t(*P.x.getUnit()); }
	static void clear(G& P) { P.clear(); }
	static void normalize(G& P) { P.normalize(); }
	static void dbl(G& Q, const G& P) { G::dbl(Q, P); }
	static void neg(G& Q, const G& P) { G::neg(Q, P); }
	static void add(G& R, const G& P, const G& Q) { G::add(R, P, Q); }
	template<class INT>
	static void mul(G& Q, const G& P, const INT& x) { G::mul(Q, P, x); }
};

/*
	treat Fp12 as EC
	unitary inverse of (a, b) = (a, -b)
	then b.a.a or -b.a.a is odd
*/
template<class G>
struct InterfaceForHashTable<G, false> : G {
	static G& castG(InterfaceForHashTable& x) { return static_cast<G&>(x); }
	static const G& castG(const InterfaceForHashTable& x) { return static_cast<const G&>(x); }
	void clear() { clear(castG(*this)); }
	void normalize() { normalize(castG(*this)); }
	static bool isOdd(const G& x) { return x.b.a.a.isOdd(); }
	static bool isZero(const G& x) { return x.isOne(); }
	static bool isSameX(const G& x, const G& Q) { return x.a == Q.a; }
	static uint32_t getHash(const G& x) { return uint32_t(*x.getFp0()->getUnit()); }
	static void clear(G& x) { x = 1; }
	static void normalize(G&) { }
	static void dbl(G& y, const G& x) { G::sqr(y, x); }
	static void neg(G& Q, const G& P) { G::unitaryInv(Q, P); }
	static void add(G& z, const G& x, const G& y) { G::mul(z, x, y); }
	template<class INT>
	static void mul(G& z, const G& x, const INT& y) { G::pow(z, x, y); }
};

/*
	HashTable<EC, true> or HashTable<Fp12, false>
*/
template<class G, bool isEC = true>
class HashTable {
	typedef InterfaceForHashTable<G, isEC> I;
	typedef std::vector<KeyCount> KeyCountVec;
	KeyCountVec kcv;
	G P_;
	mcl::fp::WindowMethod<I> wm_;
	G nextP_;
	G nextNegP_;
	size_t tryNum_;
	union ic {
		uint64_t i;
		char c[8];
	};
	static void saveUint64(std::ostream& os, uint64_t v)
	{
		ic ic;
		ic.i = v;
		os.write(ic.c, sizeof(ic));
	}
	static uint64_t loadUint64(std::istream& is)
	{
		ic ic;
		is.read(ic.c, sizeof(ic));
		return ic.i;
	}
	void setWindowMethod()
	{
		const size_t bitSize = G::BaseFp::BaseFp::getBitSize();
		wm_.init(static_cast<const I&>(P_), bitSize, local::winSize);
	}
public:
	HashTable() : tryNum_(0) {}
	bool operator==(const HashTable& rhs) const
	{
		if (kcv.size() != rhs.kcv.size()) return false;
		for (size_t i = 0; i < kcv.size(); i++) {
			if (!kcv[i].isSame(rhs.kcv[i])) return false;
		}
		return P_ == rhs.P_ && nextP_ == rhs.nextP_ && tryNum_ == rhs.tryNum_;
	}
	bool operator!=(const HashTable& rhs) const { return !operator==(rhs); }
	/*
		compute log_P(xP) for |x| <= hashSize * tryNum
	*/
	void init(const G& P, size_t hashSize, size_t tryNum = 0)
	{
		if (hashSize == 0) {
			kcv.clear();
			return;
		}
		if (hashSize >= 0x80000000u) throw cybozu::Exception("HashTable:init:hashSize is too large");
		P_ = P;
		tryNum_ = tryNum;
		kcv.resize(hashSize);
		G xP;
		I::clear(xP);
		for (int i = 1; i <= (int)kcv.size(); i++) {
			I::add(xP, xP, P_);
			I::normalize(xP);
			kcv[i - 1].key = I::getHash(xP);
			kcv[i - 1].count = I::isOdd(xP) ? i : -i;
		}
		nextP_ = xP;
		I::dbl(nextP_, nextP_);
		I::add(nextP_, nextP_, P_); // nextP = (hasSize * 2 + 1)P
		I::neg(nextNegP_, nextP_); // nextNegP = -nextP
		/*
			ascending order of abs(count) for same key
		*/
		std::stable_sort(kcv.begin(), kcv.end());
		setWindowMethod();
	}
	void setTryNum(size_t tryNum)
	{
		this->tryNum_ = tryNum;
	}
	/*
		log_P(xP)
		find range which has same hash of xP in kcv,
		and detect it
	*/
	int basicLog(G xP, bool *ok = 0) const
	{
		if (ok) *ok = true;
		if (I::isZero(xP)) return 0;
		typedef KeyCountVec::const_iterator Iter;
		KeyCount kc;
		I::normalize(xP);
		kc.key = I::getHash(xP);
		kc.count = 0;
		std::pair<Iter, Iter> p = std::equal_range(kcv.begin(), kcv.end(), kc);
		G Q;
		I::clear(Q);
		int prev = 0;
		/*
			check range which has same hash
		*/
		while (p.first != p.second) {
			int count = p.first->count;
			int abs_c = std::abs(count);
			assert(abs_c >= prev); // assume ascending order
			bool neg = count < 0;
			G T;
//			I::mul(T, P, abs_c - prev);
			mulByWindowMethod(T, abs_c - prev);
			I::add(Q, Q, T);
			I::normalize(Q);
			if (I::isSameX(Q, xP)) {
				bool QisOdd = I::isOdd(Q);
				bool xPisOdd = I::isOdd(xP);
				if (QisOdd ^ xPisOdd ^ neg) return -count;
				return count;
			}
			prev = abs_c;
			++p.first;
		}
		if (ok) {
			*ok = false;
			return 0;
		}
		throw cybozu::Exception("HashTable:basicLog:not found");
	}
	/*
		compute log_P(xP)
		call basicLog at most 2 * tryNum
	*/
	int64_t log(const G& xP) const
	{
		bool ok;
		int c = basicLog(xP, &ok);
		if (ok) {
			return c;
		}
		G posP = xP, negP = xP;
		int64_t posCenter = 0;
		int64_t negCenter = 0;
		int64_t next = (int64_t)kcv.size() * 2 + 1;
		for (size_t i = 1; i < tryNum_; i++) {
			I::add(posP, posP, nextNegP_);
			posCenter += next;
			c = basicLog(posP, &ok);
			if (ok) {
				return posCenter + c;
			}
			I::add(negP, negP, nextP_);
			negCenter -= next;
			c = basicLog(negP, &ok);
			if (ok) {
				return negCenter + c;
			}
		}
		throw cybozu::Exception("HashTable:log:not found");
	}
	void save(std::ostream& os) const
	{
		saveUint64(os, kcv.size());
		saveUint64(os, tryNum_);
		os.write((const char*)&kcv[0], sizeof(kcv[0]) * kcv.size());
		os << P_.getStr(mcl::IoArray);
	}
	void load(std::istream& is)
	{
		size_t hashSize = size_t(loadUint64(is));
		kcv.resize(hashSize);
		tryNum_ = loadUint64(is);
		is.read((char*)&kcv[0], sizeof(kcv[0]) * kcv.size());
		P_.readStream(is, mcl::IoArray);
		I::mul(nextP_, P_, (hashSize * 2) + 1);
		I::neg(nextNegP_, nextP_);
		setWindowMethod();
	}
	const mcl::fp::WindowMethod<I>& getWM() const { return wm_; }
	/*
		mul(x, P, y);
	*/
	template<class T>
	void mulByWindowMethod(G& x, const T& y) const
	{
		wm_.mul(static_cast<I&>(x), y);
	}
};

template<class G>
int log(const G& P, const G& xP)
{
	if (xP.isZero()) return 0;
	if (xP == P) return 1;
	G negT;
	G::neg(negT, P);
	if (xP == negT) return -1;
	G T = P;
	for (int i = 2; i < 100; i++) {
		T += P;
		if (xP == T) return i;
		G::neg(negT, T);
		if (xP == negT) return -i;
	}
	throw cybozu::Exception("she:log:not found");
}

} // mcl::she::local

template<class BN, class Fr>
struct SHET {
	typedef typename BN::G1 G1;
	typedef typename BN::G2 G2;
	typedef typename BN::Fp12 GT;

	class SecretKey;
	class PublicKey;
	class PrecomputedPublicKey;
	// additive HE
	class CipherTextA; // = CipherTextG1 + CipherTextG2
	class CipherTextGT; // multiplicative HE
	class CipherText; // CipherTextA + CipherTextGT

	static G1 P_;
	static G2 Q_;
	static GT ePQ_; // e(P, Q)
	static std::vector<bn_current::Fp6> Qcoeff_;
	static local::HashTable<G1> PhashTbl_;
	static local::HashTable<G2> QhashTbl_;
	static mcl::fp::WindowMethod<G2> Qwm_;
	typedef local::InterfaceForHashTable<GT, false> GTasEC;
	static local::HashTable<GT, false> ePQhashTbl_;
private:
	template<class G>
	class CipherTextAT {
		G S_, T_;
		friend class SecretKey;
		friend class PublicKey;
		friend class PrecomputedPublicKey;
		friend class CipherTextA;
		friend class CipherTextGT;
		bool isZero(const Fr& x) const
		{
			G xT;
			G::mul(xT, T_, x);
			return S_ == xT;
		}
	public:
		void clear()
		{
			S_.clear();
			T_.clear();
		}
		static void add(CipherTextAT& z, const CipherTextAT& x, const CipherTextAT& y)
		{
			/*
				(S, T) + (S', T') = (S + S', T + T')
			*/
			G::add(z.S_, x.S_, y.S_);
			G::add(z.T_, x.T_, y.T_);
		}
		static void sub(CipherTextAT& z, const CipherTextAT& x, const CipherTextAT& y)
		{
			/*
				(S, T) - (S', T') = (S - S', T - T')
			*/
			G::sub(z.S_, x.S_, y.S_);
			G::sub(z.T_, x.T_, y.T_);
		}
		// INT = int64_t or Fr
		template<class INT>
		static void mul(CipherTextAT& z, const CipherTextAT& x, const INT& y)
		{
			G::mul(z.S_, x.S_, y);
			G::mul(z.T_, x.T_, y);
		}
		static void neg(CipherTextAT& y, const CipherTextAT& x)
		{
			G::neg(y.S_, x.S_);
			G::neg(y.T_, x.T_);
		}
		void add(const CipherTextAT& c) { add(*this, *this, c); }
		void sub(const CipherTextAT& c) { sub(*this, *this, c); }
		std::istream& readStream(std::istream& is, int ioMode)
		{
			S_.readStream(is, ioMode);
			T_.readStream(is, ioMode);
			return is;
		}
		void getStr(std::string& str, int ioMode = 0) const
		{
			const char *sep = fp::getIoSeparator(ioMode);
			str = S_.getStr(ioMode);
			str += sep;
			str += T_.getStr(ioMode);
		}
		void setStr(const std::string& str, int ioMode = 0)
		{
			std::istringstream is(str);
			readStream(is, ioMode);
		}
		std::string getStr(int ioMode = 0) const
		{
			std::string str;
			getStr(str, ioMode);
			return str;
		}
		friend std::istream& operator>>(std::istream& is, CipherTextAT& self)
		{
			return self.readStream(is, fp::detectIoMode(G::getIoMode(), is));
		}
		friend std::ostream& operator<<(std::ostream& os, const CipherTextAT& self)
		{
			return os << self.getStr(fp::detectIoMode(G::getIoMode(), os));
		}
		bool operator==(const CipherTextAT& rhs) const
		{
			return S_ == rhs.S_ && T_ == rhs.T_;
		}
		bool operator!=(const CipherTextAT& rhs) const { return !operator==(rhs); }
		size_t serialize(void *buf, size_t maxBufSize) const
		{
			return mcl::local::serialize2(buf, maxBufSize, S_, T_);
		}
		size_t deserialize(const void *buf, size_t bufSize)
		{
			return mcl::local::deserialize2(S_, T_, buf, bufSize);
		}
	};
	/*
		g1 = millerLoop(P1, Q)
		g2 = millerLoop(P2, Q)
	*/
	static void doubleMillerLoop(GT& g1, GT& g2, const G1& P1, const G1& P2, const G2& Q)
	{
#if 1
		std::vector<bn_current::Fp6> Qcoeff;
		BN::precomputeG2(Qcoeff, Q);
		BN::precomputedMillerLoop(g1, P1, Qcoeff);
		BN::precomputedMillerLoop(g2, P2, Qcoeff);
#else
		BN::millerLoop(g1, P1, Q);
		BN::millerLoop(g2, P2, Q);
#endif
	}
	static void finalExp4(GT out[4], const GT in[4])
	{
		for (int i =  0; i < 4; i++) {
			BN::finalExp(out[i], in[i]);
		}
	}
	static void tensorProductML(GT g[4], const G1& S1, const G1& T1, const G2& S2, const G2& T2)
	{
		/*
			(S1, T1) x (S2, T2) = (ML(S1, S2), ML(S1, T2), ML(T1, S2), ML(T1, T2))
		*/
		doubleMillerLoop(g[0], g[2], S1, T1, S2);
		doubleMillerLoop(g[1], g[3], S1, T1, T2);
	}
	static void tensorProduct(GT g[4], const G1& S1, const G1& T1, const G2& S2, const G2& T2)
	{
		/*
			(S1, T1) x (S2, T2) = (e(S1, S2), e(S1, T2), e(T1, S2), e(T1, T2))
		*/
		tensorProductML(g,S1, T1, S2,T2);
		finalExp4(g, g);
	}
public:

	typedef CipherTextAT<G1> CipherTextG1;
	typedef CipherTextAT<G2> CipherTextG2;

	static void init(const mcl::bn::CurveParam& cp = mcl::bn::CurveFp254BNb)
	{
		bn_current::initPairing(cp);
		BN::hashAndMapToG1(P_, "0");
		BN::hashAndMapToG2(Q_, "0");
		BN::pairing(ePQ_, P_, Q_);
		BN::precomputeG2(Qcoeff_, Q_);
	}
	/*
		set range for G1-DLP
	*/
	static void setRangeForG1DLP(size_t hashSize, size_t tryNum = 0)
	{
		PhashTbl_.init(P_, hashSize, tryNum);
	}
	/*
		set range for G2-DLP
	*/
	static void setRangeForG2DLP(size_t hashSize, size_t tryNum = 0)
	{
		QhashTbl_.init(Q_, hashSize, tryNum);
	}
	/*
		set range for GT-DLP
	*/
	static void setRangeForGTDLP(size_t hashSize, size_t tryNum = 0)
	{
		ePQhashTbl_.init(ePQ_, hashSize, tryNum);
	}
	/*
		set range for G1/G2/GT DLP
		decode message m for |m| <= hasSize * tryNum
		decode time = O(log(hasSize) * tryNum)
		@note if tryNum = 0 then fast but require more memory(TBD)
	*/
	static void setRangeForDLP(size_t hashSize, size_t tryNum = 0)
	{
		setRangeForG1DLP(hashSize, tryNum);
		setRangeForG2DLP(hashSize, tryNum);
		setRangeForGTDLP(hashSize, tryNum);
	}

	/*
		only one element is necessary for each G1 and G2.
		this is better than David Mandell Freeman's algorithm
	*/
	class SecretKey {
		Fr x_, y_;
		void getPowOfePQ(GT& v, const CipherTextGT& c) const
		{
			/*
				(s, t, u, v) := (e(S, S'), e(S, T'), e(T, S'), e(T, T'))
				s v^(xy) / (t^y u^x) = s (v^x / t) ^ y / u^x
				= e(P, Q)^(mm')
			*/
			GT t, u;
			GT::unitaryInv(t, c.g_[1]);
			GT::unitaryInv(u, c.g_[2]);
			GT::pow(v, c.g_[3], x_);
			v *= t;
			GT::pow(v, v, y_);
			GT::pow(u, u, x_);
			v *= u;
			v *= c.g_[0];
		}
	public:
		template<class RG>
		void setByCSPRNG(RG& rg)
		{
			x_.setRand(rg);
			y_.setRand(rg);
		}
		void setByCSPRNG() { setByCSPRNG(local::g_rg); }
		/*
			set xP and yQ
		*/
		void getPublicKey(PublicKey& pub) const
		{
			pub.set(x_, y_);
		}
#if 0
		// log_x(y)
		int log(const GT& x, const GT& y) const
		{
			if (y == 1) return 0;
			if (y == x) return 1;
			GT inv;
			GT::unitaryInv(inv, x);
			if (y == inv) return -1;
			GT t = x;
			for (int i = 2; i < 100; i++) {
				t *= x;
				if (y == t) return i;
				GT::unitaryInv(inv, t);
				if (y == inv) return -i;
			}
			throw cybozu::Exception("she:dec:log:not found");
		}
#endif
		int64_t dec(const CipherTextG1& c) const
		{
			/*
				S = mP + rxP
				T = rP
				R = S - xT = mP
			*/
			G1 R;
			G1::mul(R, c.T_, x_);
			G1::sub(R, c.S_, R);
			return PhashTbl_.log(R);
		}
		int64_t dec(const CipherTextG2& c) const
		{
			G2 R;
			G2::mul(R, c.T_, y_);
			G2::sub(R, c.S_, R);
			return QhashTbl_.log(R);
		}
		int64_t dec(const CipherTextA& c) const
		{
			return dec(c.c1_);
		}
		int64_t dec(const CipherTextGT& c) const
		{
			GT v;
			getPowOfePQ(v, c);
			return ePQhashTbl_.log(v);
//			return log(g, v);
		}
		int64_t dec(const CipherText& c) const
		{
			if (c.isMultiplied()) {
				return dec(c.m_);
			} else {
				return dec(c.a_);
			}
		}
		bool isZero(const CipherTextG1& c) const
		{
			return c.isZero(x_);
		}
		bool isZero(const CipherTextG2& c) const
		{
			return c.isZero(y_);
		}
		bool isZero(const CipherTextA& c) const
		{
			return c.c1_.isZero(x_);
		}
		bool isZero(const CipherTextGT& c) const
		{
			GT v;
			getPowOfePQ(v, c);
			return v.isOne();
		}
		bool isZero(const CipherText& c) const
		{
			if (c.isMultiplied()) {
				return isZero(c.m_);
			} else {
				return isZero(c.a_);
			}
		}
		std::istream& readStream(std::istream& is, int ioMode)
		{
			x_.readStream(is, ioMode);
			y_.readStream(is, ioMode);
			return is;
		}
		void getStr(std::string& str, int ioMode = 0) const
		{
			const char *sep = fp::getIoSeparator(ioMode);
			str = x_.getStr(ioMode);
			str += sep;
			str += y_.getStr(ioMode);
		}
		void setStr(const std::string& str, int ioMode = 0)
		{
			std::istringstream is(str);
			readStream(is, ioMode);
		}
		std::string getStr(int ioMode = 0) const
		{
			std::string str;
			getStr(str, ioMode);
			return str;
		}
		friend std::istream& operator>>(std::istream& is, SecretKey& self)
		{
			return self.readStream(is, fp::detectIoMode(Fr::getIoMode(), is));
		}
		friend std::ostream& operator<<(std::ostream& os, const SecretKey& self)
		{
			return os << self.getStr(fp::detectIoMode(Fr::getIoMode(), os));
		}
		bool operator==(const SecretKey& rhs) const
		{
			return x_ == rhs.x_ && y_ == rhs.y_;
		}
		bool operator!=(const SecretKey& rhs) const { return !operator==(rhs); }
		size_t serialize(void *buf, size_t maxBufSize) const
		{
			return mcl::local::serialize2(buf, maxBufSize, x_, y_);
		}
		size_t deserialize(const void *buf, size_t bufSize)
		{
			return mcl::local::deserialize2(x_, y_, buf, bufSize);
		}
	};

	class PublicKey {
		G1 xP_;
		G2 yQ_;
		friend class SecretKey;
		friend class PrecomputedPublicKey;
		/*
			(S, T) = (m P + r xP, rP)
		*/
		template<class G, class INT, class RG, class I>
		static void enc1(G& S, G& T, const G& /*P*/, const G& xP, const INT& m, RG& rg, const mcl::fp::WindowMethod<I>& wm)
		{
			Fr r;
			r.setRand(rg);
//			G::mul(T, P, r);
			wm.mul(static_cast<I&>(T), r);
			G::mul(S, xP, r);
			if (m == 0) return;
			G C;
//			G::mul(C, P, m);
			wm.mul(static_cast<I&>(C), m);
			S += C;
		}
		void set(const Fr& x, const Fr& y)
		{
			G1::mul(xP_, P_, x);
			G2::mul(yQ_, Q_, y);
		}
	public:
		/*
			you can use INT as int64_t and Fr,
			but the return type of dec() is int64_t.
		*/
		template<class INT, class RG>
		void enc(CipherTextG1& c, const INT& m, RG& rg) const
		{
			enc1(c.S_, c.T_, P_, xP_, m, rg, PhashTbl_.getWM());
		}
		template<class INT, class RG>
		void enc(CipherTextG2& c, const INT& m, RG& rg) const
		{
			enc1(c.S_, c.T_, Q_, yQ_, m, rg, QhashTbl_.getWM());
		}
		template<class INT, class RG>
		void enc(CipherTextA& c, const INT& m, RG& rg) const
		{
			enc(c.c1_, m, rg);
			enc(c.c2_, m, rg);
		}
		template<class INT, class RG>
		void enc(CipherTextGT& c, const INT& m, RG& rg) const
		{
			/*
				(s, t, u, v) = ((e^x)^a (e^y)^b (e^-xy)^c e^m, e^b, e^a, e^c)
				s = e(a xP + m P, Q)e(b P - c xP, yQ)
			*/
			Fr ra, rb, rc;
			ra.setRand(rg);
			rb.setRand(rg);
			rc.setRand(rg);
			GT e;

			G1 P1, P2;
			G1::mul(P1, xP_, ra);
			if (m) {
//				G1::mul(P2, P, m);
				PhashTbl_.mulByWindowMethod(P2, m);
				P1 += P2;
			}
//			BN::millerLoop(c.g[0], P1, Q);
			BN::precomputedMillerLoop(c.g_[0], P1, Qcoeff_);
//			G1::mul(P1, P, rb);
			PhashTbl_.mulByWindowMethod(P1, rb);
			G1::mul(P2, xP_, rc);
			P1 -= P2;
			BN::millerLoop(e, P1, yQ_);
			c.g_[0] *= e;
			BN::finalExp(c.g_[0], c.g_[0]);
#if 1
			ePQhashTbl_.mulByWindowMethod(c.g_[1], rb);
			ePQhashTbl_.mulByWindowMethod(c.g_[2], ra);
			ePQhashTbl_.mulByWindowMethod(c.g_[3], rc);
#else
			GT::pow(c.g_[1], ePQ_, rb);
			GT::pow(c.g_[2], ePQ_, ra);
			GT::pow(c.g_[3], ePQ_, rc);
#endif
		}
		template<class INT, class RG>
		void enc(CipherText& c, const INT& m, RG& rg, bool multiplied = false) const
		{
			c.isMultiplied_ = multiplied;
			if (multiplied) {
				enc(c.m_, m, rg);
			} else {
				enc(c.a_, m, rg);
			}
		}
		template<class INT>
		void enc(CipherTextG1& c, const INT& m) const { return enc(c, m, local::g_rg); }
		template<class INT>
		void enc(CipherTextG2& c, const INT& m) const { return enc(c, m, local::g_rg); }
		template<class INT>
		void enc(CipherTextA& c, const INT& m) const { return enc(c, m, local::g_rg); }
		template<class INT>
		void enc(CipherTextGT& c, const INT& m) const { return enc(c, m, local::g_rg); }
		template<class INT>
		void enc(CipherText& c, const INT& m, bool multiplied = false) const { return enc(c, m, local::g_rg, multiplied); }
		/*
			convert from CipherTextG1 to CipherTextGT
		*/
		void convert(CipherTextGT& cm, const CipherTextG1& c1) const
		{
			/*
				Enc(1) = (S, T) = (Q + r yQ, rQ) = (Q, 0) if r = 0
				cm = c1 * (Q, 0) = (S, T) * (Q, 0) = (e(S, Q), 1, e(T, Q), 1)
			*/
			BN::precomputedMillerLoop(cm.g_[0], c1.S_, Qcoeff_);
			BN::finalExp(cm.g_[0], cm.g_[0]);
			BN::precomputedMillerLoop(cm.g_[2], c1.T_, Qcoeff_);
			BN::finalExp(cm.g_[2], cm.g_[2]);

			cm.g_[1] = 1;
			cm.g_[3] = 1;
		}
		/*
			convert from CipherTextG2 to CipherTextGT
		*/
		void convert(CipherTextGT& cm, const CipherTextG2& c2) const
		{
			/*
				Enc(1) = (S, T) = (P + r xP, rP) = (P, 0) if r = 0
				cm = (P, 0) * c2
			*/
			G1 zero; zero.clear();
			tensorProduct(cm.g_, P_, zero, c2.S_, c2.T_);
		}
		void convert(CipherTextGT& cm, const CipherTextA& ca) const
		{
			convert(cm, ca.c1_);
		}
		void convert(CipherText& cm, const CipherText& ca) const
		{
			if (ca.isMultiplied()) throw cybozu::Exception("she:PublicKey:convertCipherText:already isMultiplied");
			cm.isMultiplied_ = true;
			convert(cm.m_, ca.a_);
		}
		/*
			c += Enc(0)
		*/
		template<class RG>
		void reRand(CipherTextG1& c, RG& rg) const
		{
			CipherTextG1 c0;
			enc(c0, 0, rg);
			CipherTextG1::add(c, c, c0);
		}
		template<class RG>
		void reRand(CipherTextG2& c, RG& rg) const
		{
			CipherTextG2 c0;
			enc(c0, 0, rg);
			CipherTextG2::add(c, c, c0);
		}
		template<class RG>
		void reRand(CipherTextA& c, RG& rg) const
		{
			CipherTextA c0;
			enc(c0, 0, rg);
			CipherTextA::add(c, c, c0);
		}
		template<class RG>
		void reRand(CipherTextGT& c, RG& rg) const
		{
#if 1 // for circuit security : 3.58Mclk -> 5.4Mclk
			CipherTextGT c0;
			enc(c0, 0, rg);
			CipherTextGT::add(c, c, c0);
#else
			/*
				add Enc(0) * Enc(0)
				(S1, T1) * (S2, T2) = (rxP, rP) * (r'yQ, r'Q)
				replace r <- rr', r' <- 1
				= (r xP, rP) * (yQ, Q)
			*/
			G1 S1, T1;
			Fr r;
			r.setRand(rg);
			G1::mul(S1, xP, r);
			G1::mul(T1, P, r);
			GT g_[4];
			tensorProduct(g_, S1, T1, yQ, Q);
			for (int i = 0; i < 4; i++) {
				c.g_[i] *= g_[i];
			}
#endif
		}
		template<class RG>
		void reRand(CipherText& c, RG& rg) const
		{
			if (c.isMultiplied()) {
				reRand(c.m_, rg);
			} else {
				reRand(c.a_, rg);
			}
		}
		void reRand(CipherTextG1& c) const { reRand(c, local::g_rg); }
		void reRand(CipherTextG2& c) const { reRand(c, local::g_rg); }
		void reRand(CipherTextA& c) const { reRand(c, local::g_rg); }
		void reRand(CipherTextGT& c) const { reRand(c, local::g_rg); }
		void reRand(CipherText& c) const { reRand(c, local::g_rg); }

		std::istream& readStream(std::istream& is, int ioMode)
		{
			xP_.readStream(is, ioMode);
			yQ_.readStream(is, ioMode);
			return is;
		}
		void getStr(std::string& str, int ioMode = 0) const
		{
			const char *sep = fp::getIoSeparator(ioMode);
			str = xP_.getStr(ioMode);
			str += sep;
			str += yQ_.getStr(ioMode);
		}
		void setStr(const std::string& str, int ioMode = 0)
		{
			std::istringstream is(str);
			readStream(is, ioMode);
		}
		std::string getStr(int ioMode = 0) const
		{
			std::string str;
			getStr(str, ioMode);
			return str;
		}
		friend std::istream& operator>>(std::istream& is, PublicKey& self)
		{
			return self.readStream(is, fp::detectIoMode(G1::getIoMode(), is));
		}
		friend std::ostream& operator<<(std::ostream& os, const PublicKey& self)
		{
			return os << self.getStr(fp::detectIoMode(G1::getIoMode(), os));
		}
		bool operator==(const PublicKey& rhs) const
		{
			return xP_ == rhs.xP_ && yQ_ == rhs.yQ_;
		}
		bool operator!=(const PublicKey& rhs) const { return !operator==(rhs); }
		size_t serialize(void *buf, size_t maxBufSize) const
		{
			return mcl::local::serialize2(buf, maxBufSize, xP_, yQ_);
		}
		size_t deserialize(const void *buf, size_t bufSize)
		{
			return mcl::local::deserialize2(xP_, yQ_, buf, bufSize);
		}
	};

	class PrecomputedPublicKey {
		typedef local::InterfaceForHashTable<GT, false> GTasEC;
		typedef mcl::fp::WindowMethod<GTasEC> GTwin;
		GT exPQ_;
		GT eyPQ_;
		GT exyPQ_;
		GTwin exPQwm_;
		GTwin eyPQwm_;
		GTwin exyPQwm_;
		mcl::fp::WindowMethod<G1> xPwm_;
		mcl::fp::WindowMethod<G2> yQwm_;
		template<class T>
		void mulByWindowMethod(GT& x, const GTwin& wm, const T& y) const
		{
			wm.mul(static_cast<GTasEC&>(x), y);
		}
	public:
		void init(const PublicKey& pub)
		{
			BN::pairing(exPQ_, pub.xP_, Q_);
			BN::pairing(eyPQ_, P_, pub.yQ_);
			BN::pairing(exyPQ_, pub.xP_, pub.yQ_);
			const size_t bitSize = Fr::getBitSize();
			exPQwm_.init(static_cast<const GTasEC&>(exPQ_), bitSize, local::winSize);
			eyPQwm_.init(static_cast<const GTasEC&>(eyPQ_), bitSize, local::winSize);
			exyPQwm_.init(static_cast<const GTasEC&>(exyPQ_), bitSize, local::winSize);
			xPwm_.init(pub.xP_, bitSize, local::winSize);
			yQwm_.init(pub.yQ_, bitSize, local::winSize);
		}
		/*
			(S, T) = (m P + r xP, rP)
		*/
		template<class G, class RG, class I>
		void enc1(G& S, G& T, int64_t m, RG& rg, const mcl::fp::WindowMethod<I>& Pwm, const mcl::fp::WindowMethod<G>& xPwm) const
		{
			Fr r;
			r.setRand(rg);
			Pwm.mul(static_cast<I&>(T), r);
			xPwm.mul(S, r);
			if (m == 0) return;
			G C;
			Pwm.mul(static_cast<I&>(C), m);
			S += C;
		}
		template<class RG>
		void enc(CipherTextG1& c, int64_t m, RG& rg) const
		{
			enc1(c.S_, c.T_, m, rg, PhashTbl_.getWM(), xPwm_);
		}
		template<class RG>
		void enc(CipherTextG2& c, int64_t m, RG& rg) const
		{
			enc1(c.S_, c.T_, m, rg, QhashTbl_.getWM(), yQwm_);
		}
		template<class RG>
		void enc(CipherTextGT& c, int64_t m, RG& rg) const
		{
			/*
				(s, t, u, v) = (e^m e^(xya), (e^x)^b, (e^y)^c, e^(b + c - a))
			*/
			Fr ra, rb, rc;
			ra.setRand(rg);
			rb.setRand(rg);
			rc.setRand(rg);
			GT t;
			ePQhashTbl_.mulByWindowMethod(c.g_[0], m); // e^m
			mulByWindowMethod(t, exyPQwm_, ra); // (e^xy)^a
			c.g_[0] *= t;
			mulByWindowMethod(c.g_[1], exPQwm_, rb); // (e^x)^b
			mulByWindowMethod(c.g_[2], eyPQwm_, rc); // (e^y)^c
			rb = rb + rc - ra;
			ePQhashTbl_.mulByWindowMethod(c.g_[3], rb);
		}
		template<class CT, class RG>
		void reRandT(CT& c, RG& rg) const
		{
			CT c0;
			enc(c0, 0, rg);
			CT::add(c, c, c0);
		}
		template<class RG> void reRand(CipherTextG1& c, RG& rg) const { reRandT(c, rg); }
		template<class RG> void reRand(CipherTextG2& c, RG& rg) const { reRandT(c, rg); }
		template<class RG> void reRand(CipherTextGT& c, RG& rg) const { reRandT(c, rg); }
		void enc(CipherTextG1& c, int64_t m) const { return enc(c, m, local::g_rg); }
		void enc(CipherTextG2& c, int64_t m) const { return enc(c, m, local::g_rg); }
		void enc(CipherTextGT& c, int64_t m) const { return enc(c, m, local::g_rg); }
		void reRand(CipherTextG1& c) const { reRand(c, local::g_rg); }
		void reRand(CipherTextG2& c) const { reRand(c, local::g_rg); }
		void reRand(CipherTextGT& c) const { reRand(c, local::g_rg); }
	};

	class CipherTextA {
		CipherTextG1 c1_;
		CipherTextG2 c2_;
		friend class SecretKey;
		friend class PublicKey;
		friend class CipherTextGT;
	public:
		void clear()
		{
			c1_.clear();
			c2_.clear();
		}
		static void add(CipherTextA& z, const CipherTextA& x, const CipherTextA& y)
		{
			CipherTextG1::add(z.c1_, x.c1_, y.c1_);
			CipherTextG2::add(z.c2_, x.c2_, y.c2_);
		}
		static void sub(CipherTextA& z, const CipherTextA& x, const CipherTextA& y)
		{
			CipherTextG1::sub(z.c1_, x.c1_, y.c1_);
			CipherTextG2::sub(z.c2_, x.c2_, y.c2_);
		}
		static void mul(CipherTextA& z, const CipherTextA& x, int64_t y)
		{
			CipherTextG1::mul(z.c1_, x.c1_, y);
			CipherTextG2::mul(z.c2_, x.c2_, y);
		}
		static void neg(CipherTextA& y, const CipherTextA& x)
		{
			CipherTextG1::neg(y.c1_, x.c1_);
			CipherTextG2::neg(y.c2_, x.c2_);
		}
		void add(const CipherTextA& c) { add(*this, *this, c); }
		void sub(const CipherTextA& c) { sub(*this, *this, c); }
		std::istream& readStream(std::istream& is, int ioMode)
		{
			c1_.readStream(is, ioMode);
			c2_.readStream(is, ioMode);
			return is;
		}
		void getStr(std::string& str, int ioMode = 0) const
		{
			const char *sep = fp::getIoSeparator(ioMode);
			str = c1_.getStr(ioMode);
			str += sep;
			str += c2_.getStr(ioMode);
		}
		void setStr(const std::string& str, int ioMode = 0)
		{
			std::istringstream is(str);
			readStream(is, ioMode);
		}
		std::string getStr(int ioMode = 0) const
		{
			std::string str;
			getStr(str, ioMode);
			return str;
		}
		friend std::istream& operator>>(std::istream& is, CipherTextA& self)
		{
			return self.readStream(is, fp::detectIoMode(G1::getIoMode(), is));
		}
		friend std::ostream& operator<<(std::ostream& os, const CipherTextA& self)
		{
			return os << self.getStr(fp::detectIoMode(G1::getIoMode(), os));
		}
		bool operator==(const CipherTextA& rhs) const
		{
			return c1_ == rhs.c1_ && c2_ == rhs.c2_;
		}
		bool operator!=(const CipherTextA& rhs) const { return !operator==(rhs); }
	};

	class CipherTextGT {
		GT g_[4];
		friend class SecretKey;
		friend class PublicKey;
		friend class PrecomputedPublicKey;
		friend class CipherTextA;
	public:
		void clear()
		{
			for (int i = 0; i < 4; i++) {
				g_[i].setOne();
			}
		}
		static void add(CipherTextGT& z, const CipherTextGT& x, const CipherTextGT& y)
		{
			/*
				(g[i]) + (g'[i]) = (g[i] * g'[i])
			*/
			for (int i = 0; i < 4; i++) {
				GT::mul(z.g_[i], x.g_[i], y.g_[i]);
			}
		}
		static void sub(CipherTextGT& z, const CipherTextGT& x, const CipherTextGT& y)
		{
			/*
				(g[i]) - (g'[i]) = (g[i] / g'[i])
			*/
			GT t;
			for (size_t i = 0; i < 4; i++) {
				GT::unitaryInv(t, y.g_[i]);
				GT::mul(z.g_[i], x.g_[i], t);
			}
		}
		static void mulML(CipherTextGT& z, const CipherTextG1& x, const CipherTextG2& y)
		{
			/*
				(S1, T1) * (S2, T2) = (ML(S1, S2), ML(S1, T2), ML(T1, S2), ML(T1, T2))
			*/
			tensorProductML(z.g_, x.S_, x.T_, y.S_, y.T_);
		}
		static void finalExp(CipherTextGT& y, const CipherTextGT& x)
		{
			finalExp4(y.g_, x.g_);
		}
		/*
			mul(x, y) = mulML(x, y) + finalExp
			mul(c11, c12) + mul(c21, c22)
			= finalExp(mulML(c11, c12) + mulML(c21, c22)),
			then one finalExp can be reduced
		*/
		static void mul(CipherTextGT& z, const CipherTextG1& x, const CipherTextG2& y)
		{
			/*
				(S1, T1) * (S2, T2) = (e(S1, S2), e(S1, T2), e(T1, S2), e(T1, T2))
			*/
			mulML(z, x, y);
			finalExp(z, z);
		}
		static void mul(CipherTextGT& z, const CipherTextA& x, const CipherTextA& y)
		{
			mul(z, x.c1_, y.c2_);
		}
		static void mul(CipherTextGT& z, const CipherTextGT& x, int64_t y)
		{
			for (int i = 0; i < 4; i++) {
				GT::pow(z.g_[i], x.g_[i], y);
			}
		}
		void add(const CipherTextGT& c) { add(*this, *this, c); }
		void sub(const CipherTextGT& c) { sub(*this, *this, c); }
		std::istream& readStream(std::istream& is, int ioMode)
		{
			for (int i = 0; i < 4; i++) {
				g_[i].readStream(is, ioMode);
			}
			return is;
		}
		void getStr(std::string& str, int ioMode = 0) const
		{
			const char *sep = fp::getIoSeparator(ioMode);
			str = g_[0].getStr(ioMode);
			for (int i = 1; i < 4; i++) {
				str += sep;
				str += g_[i].getStr(ioMode);
			}
		}
		void setStr(const std::string& str, int ioMode = 0)
		{
			std::istringstream is(str);
			readStream(is, ioMode);
		}
		std::string getStr(int ioMode = 0) const
		{
			std::string str;
			getStr(str, ioMode);
			return str;
		}
		friend std::istream& operator>>(std::istream& is, CipherTextGT& self)
		{
			return self.readStream(is, fp::detectIoMode(G1::getIoMode(), is));
		}
		friend std::ostream& operator<<(std::ostream& os, const CipherTextGT& self)
		{
			return os << self.getStr(fp::detectIoMode(G1::getIoMode(), os));
		}
		bool operator==(const CipherTextGT& rhs) const
		{
			for (int i = 0; i < 4; i++) {
				if (g_[i] != rhs.g_[i]) return false;
			}
			return true;
		}
		bool operator!=(const CipherTextGT& rhs) const { return !operator==(rhs); }
		size_t serialize(void *buf, size_t maxBufSize) const
		{
			char *p = reinterpret_cast<char*>(buf);
			const size_t n1 = mcl::local::serialize2(p, maxBufSize, g_[0], g_[1]);
			if (n1 == 0) return 0;
			p += n1; maxBufSize -= n1;
			const size_t n2 = mcl::local::serialize2(p, maxBufSize, g_[2], g_[3]);
			if (n2 == 0) return 0;
			return n1 + n2;
		}
		size_t deserialize(const void *buf, size_t bufSize)
		{
			const char *p = reinterpret_cast<const char*>(buf);
			const size_t n1 = mcl::local::deserialize2(g_[0], g_[1], p, bufSize);
			if (n1 == 0) return 0;
			p += n1; bufSize -= n1;
			const size_t n2 = mcl::local::deserialize2(g_[2], g_[3], p, bufSize);
			if (n2 == 0) return 0;
			return n1 + n2;
		}
	};

	class CipherText {
		bool isMultiplied_;
		CipherTextA a_;
		CipherTextGT m_;
		friend class SecretKey;
		friend class PublicKey;
	public:
		CipherText() : isMultiplied_(false) {}
		void clearAsAdded()
		{
			isMultiplied_ = false;
			a_.clear();
		}
		void clearAsMultiplied()
		{
			isMultiplied_ = true;
			m_.clear();
		}
		bool isMultiplied() const { return isMultiplied_; }
		static void add(CipherText& z, const CipherText& x, const CipherText& y)
		{
			if (x.isMultiplied() && y.isMultiplied()) {
				z.isMultiplied_ = true;
				CipherTextGT::add(z.m_, x.m_, y.m_);
				return;
			}
			if (!x.isMultiplied() && !y.isMultiplied()) {
				z.isMultiplied_ = false;
				CipherTextA::add(z.a_, x.a_, y.a_);
				return;
			}
			throw cybozu::Exception("she:CipherText:add:mixed CipherText");
		}
		static void sub(CipherText& z, const CipherText& x, const CipherText& y)
		{
			if (x.isMultiplied() && y.isMultiplied()) {
				z.isMultiplied_ = true;
				CipherTextGT::sub(z.m_, x.m_, y.m_);
				return;
			}
			if (!x.isMultiplied() && !y.isMultiplied()) {
				z.isMultiplied_ = false;
				CipherTextA::sub(z.a_, x.a_, y.a_);
				return;
			}
			throw cybozu::Exception("she:CipherText:sub:mixed CipherText");
		}
		static void mul(CipherText& z, const CipherText& x, const CipherText& y)
		{
			if (x.isMultiplied() || y.isMultiplied()) {
				throw cybozu::Exception("she:CipherText:mul:mixed CipherText");
			}
			z.isMultiplied_ = true;
			CipherTextGT::mul(z.m_, x.a_, y.a_);
		}
		static void mul(CipherText& z, const CipherText& x, int64_t y)
		{
			if (x.isMultiplied()) {
				CipherTextGT::mul(z.m_, x.m_, y);
			} else {
				CipherTextA::mul(z.a_, x.a_, y);
			}
		}
		void add(const CipherText& c) { add(*this, *this, c); }
		void sub(const CipherText& c) { sub(*this, *this, c); }
		void mul(const CipherText& c) { mul(*this, *this, c); }
		std::istream& readStream(std::istream& is, int ioMode)
		{
			is >> isMultiplied_;
			if (isMultiplied()) {
				m_.readStream(is, ioMode);
			} else {
				a_.readStream(is, ioMode);
			}
			return is;
		}
		void getStr(std::string& str, int ioMode = 0) const
		{
			const char *sep = fp::getIoSeparator(ioMode);
			str = isMultiplied() ? "1" : "0";
			str += sep;
			if (isMultiplied()) {
				str += m_.getStr(ioMode);
			} else {
				str += a_.getStr(ioMode);
			}
		}
		void setStr(const std::string& str, int ioMode = 0)
		{
			std::istringstream is(str);
			readStream(is, ioMode);
		}
		std::string getStr(int ioMode = 0) const
		{
			std::string str;
			getStr(str, ioMode);
			return str;
		}
		friend std::istream& operator>>(std::istream& is, CipherText& self)
		{
			return self.readStream(is, fp::detectIoMode(G1::getIoMode(), is));
		}
		friend std::ostream& operator<<(std::ostream& os, const CipherText& self)
		{
			return os << self.getStr(fp::detectIoMode(G1::getIoMode(), os));
		}
		bool operator==(const CipherTextGT& rhs) const
		{
			if (isMultiplied() != rhs.isMultiplied()) return false;
			if (isMultiplied()) {
				return m_ == rhs.m_;
			}
			return a_ == rhs.a_;
		}
		bool operator!=(const CipherTextGT& rhs) const { return !operator==(rhs); }
	};
};

template<class BN, class Fr> typename BN::G1 SHET<BN, Fr>::P_;
template<class BN, class Fr> typename BN::G2 SHET<BN, Fr>::Q_;
template<class BN, class Fr> typename BN::Fp12 SHET<BN, Fr>::ePQ_;
template<class BN, class Fr> std::vector<bn_current::Fp6> SHET<BN, Fr>::Qcoeff_;
template<class BN, class Fr> local::HashTable<typename BN::G1> SHET<BN, Fr>::PhashTbl_;
template<class BN, class Fr> local::HashTable<typename BN::G2> SHET<BN, Fr>::QhashTbl_;
template<class BN, class Fr> local::HashTable<typename BN::Fp12, false> SHET<BN, Fr>::ePQhashTbl_;
typedef mcl::she::SHET<bn_current::BN, bn_current::Fr> SHE;
typedef SHE::SecretKey SecretKey;
typedef SHE::PublicKey PublicKey;
typedef SHE::PrecomputedPublicKey PrecomputedPublicKey;
typedef SHE::CipherTextG1 CipherTextG1;
typedef SHE::CipherTextG2 CipherTextG2;
typedef SHE::CipherTextGT CipherTextGT;
typedef SHE::CipherTextA CipherTextA;
typedef CipherTextGT CipherTextGM; // old class
typedef SHE::CipherText CipherText;

} } // mcl::she