[she] add CipherTextGT::mulML, finalExp

4 files changed, 106 insertions, 9 deletions

diff --git a/include/mcl/she.h b/include/mcl/she.h
index 9b6866a..75135ab 100644
--- a/include/mcl/she.h
+++ b/include/mcl/she.h
@@ -142,6 +142,13 @@ MCLSHE_DLL_API int sheMulGT(sheCipherTextGT *z, const sheCipherTextGT *x, mclInt
 // return 0 if success
 // z = x * y
 MCLSHE_DLL_API int sheMul(sheCipherTextGT *z, const sheCipherTextG1 *x, const sheCipherTextG2 *y);
+/*
+	sheMul(z, x, y) = sheMulML(z, x, y) + sheFinalExpGT(z)
+	@note
+	Mul(x1, y1) + ... + Mul(xn, yn) = finalExp(MulML(x1, y1) + ... + MulML(xn, yn))
+*/
+MCLSHE_DLL_API int sheMulML(sheCipherTextGT *z, const sheCipherTextG1 *x, const sheCipherTextG2 *y);
+MCLSHE_DLL_API int sheFinalExpGT(sheCipherTextGT *y, const sheCipherTextGT *x);
 
 // return 0 if success
 // rerandomize(c)
diff --git a/include/mcl/she.hpp b/include/mcl/she.hpp
index 3f45dc7..917838c 100644
--- a/include/mcl/she.hpp
+++ b/include/mcl/she.hpp
@@ -444,27 +444,39 @@ private:
 		g1 = millerLoop(P1, Q)
 		g2 = millerLoop(P2, Q)
 	*/
-	static void doublePairing(GT& g1, GT& g2, const G1& P1, const G1& P2, const G2& 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::finalExp(g1, g1);
 		BN::precomputedMillerLoop(g2, P2, Qcoeff);
-		BN::finalExp(g2, g2);
 #else
-		BN::pairing(g1, P1, Q);
-		BN::pairing(g2, P2, Q);
+		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))
 		*/
-		doublePairing(g[0], g[2], S1, T1, S2);
-		doublePairing(g[1], g[3], S1, T1, T2);
+		tensorProductML(g,S1, T1, S2,T2);
+		finalExp4(g, g);
 	}
 public:
 
@@ -788,7 +800,6 @@ public:
 				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)
 			*/
-//			doublePairing(cm.g_[0], cm.g_[2], c1.S, c1.T, Q);
 			BN::precomputedMillerLoop(cm.g_[0], c1.S_, Qcoeff_);
 			BN::finalExp(cm.g_[0], cm.g_[0]);
 			BN::precomputedMillerLoop(cm.g_[2], c1.T_, Qcoeff_);
@@ -1128,12 +1139,30 @@ public:
 				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))
 			*/
-			tensorProduct(z.g_, x.S_, x.T_, y.S_, y.T_);
+			mulML(z, x, y);
+			finalExp(z, z);
 		}
 		static void mul(CipherTextGT& z, const CipherTextA& x, const CipherTextA& y)
 		{
diff --git a/src/she_c_impl.hpp b/src/she_c_impl.hpp
index db87659..22b25d2 100644
--- a/src/she_c_impl.hpp
+++ b/src/she_c_impl.hpp
@@ -353,6 +353,26 @@ int sheMul(sheCipherTextGT *z, const sheCipherTextG1 *x, const sheCipherTextG2 *
 	return mulT(*cast(z), *cast(x), *cast(y));
 }
 
+int sheMulML(sheCipherTextGT *z, const sheCipherTextG1 *x, const sheCipherTextG2 *y)
+	try
+{
+	CipherTextGT::mulML(*cast(z), *cast(x), *cast(y));
+	return 0;
+} catch (std::exception& e) {
+	fprintf(stderr, "err %s\n", e.what());
+	return -1;
+}
+
+int sheFinalExpGT(sheCipherTextGT *y, const sheCipherTextGT *x)
+	try
+{
+	CipherTextGT::finalExp(*cast(y), *cast(x));
+	return 0;
+} catch (std::exception& e) {
+	fprintf(stderr, "err %s\n", e.what());
+	return -1;
+}
+
 template<class CT>
 int reRandT(CT& c, const shePublicKey *pub)
 	try
diff --git a/test/she_c_test.hpp b/test/she_c_test.hpp
index 7bc3256..421819d 100644
--- a/test/she_c_test.hpp
+++ b/test/she_c_test.hpp
@@ -262,3 +262,44 @@ CYBOZU_TEST_AUTO(precomputed)
 
 	shePrecomputedPublicKeyDestroy(ppub);
 }
+
+CYBOZU_TEST_AUTO(finalExp)
+{
+	sheSecretKey sec;
+	sheSecretKeySetByCSPRNG(&sec);
+	shePublicKey pub;
+	sheGetPublicKey(&pub, &sec);
+	const int64_t m11 = 5;
+	const int64_t m12 = 7;
+	const int64_t m21 = -3;
+	const int64_t m22 = 9;
+	sheCipherTextG1 c11, c12;
+	sheCipherTextG2 c21, c22;
+	sheCipherTextGT ct1, ct2;
+	sheCipherTextGT ct;
+	sheEncG1(&c11, &pub, m11);
+	sheEncG1(&c12, &pub, m12);
+	sheEncG2(&c21, &pub, m21);
+	sheEncG2(&c22, &pub, m22);
+
+	int64_t dec;
+	// sheMul = sheMulML + sheFinalExpGT
+	sheMulML(&ct1, &c11, &c21);
+	sheFinalExpGT(&ct, &ct1);
+	CYBOZU_TEST_EQUAL(sheDecGT(&dec, &sec, &ct), 0);
+	CYBOZU_TEST_EQUAL(dec, m11 * m21);
+
+	sheMulML(&ct2, &c12, &c22);
+	sheFinalExpGT(&ct, &ct2);
+	CYBOZU_TEST_EQUAL(sheDecGT(&dec, &sec, &ct), 0);
+	CYBOZU_TEST_EQUAL(dec, m12 * m22);
+
+	/*
+		Mul(c11, c21) + Mul(c21, c22)
+		= finalExp(ML(c11, c21) + ML(c21, c22))
+	*/
+	sheAddGT(&ct, &ct1, &ct2);
+	sheFinalExpGT(&ct, &ct);
+	CYBOZU_TEST_EQUAL(sheDecGT(&dec, &sec, &ct), 0);
+	CYBOZU_TEST_EQUAL(dec, (m11 * m21) + (m12 * m22));
+}