Bilinearity of the BN Pairing function

[baz1]

Hello,

I am having the following strange behavior when using the BN pairing function :

#include <iostream>

#define MR_PAIRING_BN
#include "pairing_3.h"

#ifndef AES_SECURITY
#define AES_SECURITY 128
#endif

using namespace std;

int main() {
    PFC pfc(AES_SECURITY);
    G1 g1;
    G2 g2;
    GT gt;

    pfc.hash_and_map(g1, "Hello");
    g2 = pfc.mult(g2, 0);
    cout << "e(" << (g1.g.iszero() ? "O" : "?") << ", " << (g2.g.iszero() ? "O" : "?") << ") = " << (pfc.pairing(g2, g1).g.isunity() ? "1" : "?") << endl;

    pfc.hash_and_map(g2, "Hello");
    g1 = pfc.mult(g1, 0);
    cout << "e(" << (g1.g.iszero() ? "O" : "?") << ", " << (g2.g.iszero() ? "O" : "?") << ") = " << (pfc.pairing(g2, g1).g.isunity() ? "1" : "?") << endl;

    return 0;
}

Compiled with g++ -m64 -O2 main.cpp bn_pair.cpp zzn12a.cpp ecn2.cpp zzn4.cpp zzn2.cpp big.cpp zzn.cpp ecn.cpp miracl.a -o test.

This program outputs "e(?, O) = 1" on the first line (which is to be expected), but it prints "e(O, ?) = ?" on the second line ; isn't that supposed to be breaking the bilinearity of the pairing map? Thank you for your explanation.

Also, I would like to point out that some compilation files are not up-to-date and do not permit the compilation of some of the examples because of some missing mr*.c files (for instance, the linux64_cpp script does not compile mrzzn4.c).

[mcarrickscott]

Hello Remi,

The case where e(Q,P) and P is the point-at-infinity really needs to be treated as a special case, as the point at infinity does not have representable x and y coordinates that can be used in Miller's algorithm.

A simple and quick fix is to add a few lines to this function in bn_pair.cpp

void extract(ECn& A,ZZn& x,ZZn& y) { // (x,y) <- A // add these lines from here.. if (A.iszero()) { x=0; y=0; return; } // to here x=(A.get_point())->X; y=(A.get_point())->Y; }

You are right about mrzzn4.c - any other missing files you noticed?

Mike

On Fri, Jul 1, 2016 at 3:18 AM, Rémi Bazin notifications@github.com wrote:

Hello,

I am having the following strange behavior when using the BN pairing function :

include

define MR_PAIRING_BN

include "pairing_3.h"

ifndef AES_SECURITY

define AES_SECURITY 128

endif

using namespace std;

int main() { PFC pfc(AES_SECURITY); G1 g1; G2 g2; GT gt;

pfc.hash_and_map(g1, "Hello");
g2 = pfc.mult(g2, 0);
cout << "e(" << (g1.g.iszero() ? "O" : "?") << ", " << (g2.g.iszero() ? "O" : "?") << ") = " << (pfc.pairing(g2, g1).g.isunity() ? "1" : "?") << endl;

pfc.hash_and_map(g2, "Hello");
g1 = pfc.mult(g1, 0);
cout << "e(" << (g1.g.iszero() ? "O" : "?") << ", " << (g2.g.iszero() ? "O" : "?") << ") = " << (pfc.pairing(g2, g1).g.isunity() ? "1" : "?") << endl;

return 0;

}

Compiled with g++ -m64 -O2 main.cpp bn_pair.cpp zzn12a.cpp ecn2.cpp zzn4.cpp zzn2.cpp big.cpp zzn.cpp ecn.cpp miracl.a -o test.

This program outputs "e(?, O) = 1" on the first line (which is to be expected), but it prints "e(O, ?) = ?" on the second line ; isn't that supposed to be breaking the bilinearity of the pairing map?

Also, I would like to point out that some compilation files are not up-to-date and do not permit, for instance, the compilation of some of the examples because of some missing mr*.c files (for instance, the linux64_cpp script does not compile mrzzn4.c).

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/miracl/MIRACL/issues/24, or mute the thread https://github.com/notifications/unsubscribe/ACm8jtTlzxXeowiAhV_xT95GbBfwRALGks5qRHkJgaJpZM4JCwqj .

[baz1]

Hello Mike,

Thank you very much for your quick answer, which is very helpful! Shouldn't this fix be committed to the main branch of this repository? (as well as the equivalent for other pairings if applicable) For the compilation script, I did not notice any other missing files - but since I compiled all the mr*.c as a workaround, I wouldn't have known. Now that I look at it, it seems like this was the only missing file; sorry for my generalization. Best,

Rémi