Shouldn't e(g_1^0, g_2) = e(g_1, g_2^0)?

[alinush]

Hi all,

I believe I found a small bug in libff on the develop and master branches, where e(g_1^0, g_2) != e(g_1, g_2^0), but they should be equal.

I am able to reproduce it with the following test:

diff --git a/libff/algebra/curves/tests/test_bilinearity.cpp b/libff/algebra/curves/tests/test_bilinearity.cpp
index ecfaca8..a9074dd 100755
--- a/libff/algebra/curves/tests/test_bilinearity.cpp
+++ b/libff/algebra/curves/tests/test_bilinearity.cpp
@@ -40,6 +40,11 @@ void pairing_test()
 {
     GT<ppT> GT_one = GT<ppT>::one();

+    printf("Checking e(0*g1, g2) = e(g1, 0*g2)"); // = e(g1, g2)^0
+    GT<ppT> lhs = ppT::reduced_pairing(G1<ppT>::zero(), G2<ppT>::one());
+    GT<ppT> rhs = ppT::reduced_pairing(G1<ppT>::one(), G2<ppT>::zero());
+    EXPECT_EQ(lhs, rhs);
+
     printf("Running bilinearity tests:\n");
     G1<ppT> P = (Fr<ppT>::random_element()) * G1<ppT>::one();
     //G1<ppT> P = Fr<ppT>("2") * G1<ppT>::one();

And then building and running the tests as per the README:

    mkdir build && cd build
        cmake ..
        make
        make test

I discovered this while using BN128 from the master branch in one one of my projects and then reproduced it in the develop branch above.

Specifically, in my project, if I compare e(g_1^0, g_2) with e(g_1, g_2^0), which it should be equal to, I get:

ReducedPairing(G1::zero(), ck.getGen2()) =
([[1,0],
 [0,0],
 [0,0]] [[0,0],
 [0,0],
 [0,0]])

ReducedPairing(ck.getGen1(), G2::zero()) =
 ([[0,0],
 [0,0],
 [0,0]] [[0,0],
 [0,0],
 [0,0]])

As you can see, the LHS begins with a [1,0] while the RHS with a [0,0].

[dtebbs]

Coincidentally I recently hit something similar in a slightly different context.

The precompute functions all appear to assume non-identity elements. They immediately convert to affine form and extract the X and Y coordinates (which does not account for the case Z=0). For example: https://github.com/scipr-lab/libff/blob/develop/libff/algebra/curves/mnt/mnt6/mnt6_pairing.cpp#L479

Unless I'm completely off track (which is perfectly possible), if you work around this with is_zero checks of the G1 and G2 elements, no other cases should be affected.

In terms of fixes (short of alternative implemenations of the pairing), the preecompute functions should probably assert that the input elements are not the identity, and the high level pairing functions could be extended with the workaround to check for identity elements.

[alinush]

Intriguing. The math is a bit above my pay grade, but I guess I can wrap my own pairing function to check for & prevent this bug. Thank you!