Problem: the Tate pairing function does not preserve bilinearity properties

[Aleksandr Lenin <aleksandr.lenin@cyber.ee>]

Hi all,

I've stumbled across the following problem and need an advice - am I
missing something here, or did I understand something wrong?

[Problem description]

Consider a supersingular elliptic curve y^3 = x^2 + 1 defined over an
extension field F_{59^2}. Consider two points P and Q belonging to to
different subgroups of the 5-torsion.

P = (28,51) is the point residing in the base field subgroup
Q = (23*x+45,51) is the point obtained by applying the distortion map to P.

I am checking for bilinearity property: e([2]P,Q) = e(P,Q)^2

First, I tried to make these calculations representing points as vectors
whose elements are t_FFELT-s from F_{59^2}.

    GEN baseFieldSize = stoi(59);
    GEN modulus = FpX_to_mod(mkpoln(3,gen_1,gen_0,gen_1),baseFieldSize);
    GEN q = ffgen(modulus,0);
    GEN ell = ellinit( mkvec2(gen_0,gen_1), q, DEFAULTPREC );
    GEN torder = stoi(5);

    GEN P = mkvec2(stoi(28),stoi(51));           // P
    GEN DP = mkvec2(stoi(18),stoi(13));          // [2]P
    GEN Q = mkvec2(
            FF_Z_add( FF_Z_mul(q,stoi(23)), stoi(45) ),
            FF_Z_add( FF_Z_mul(q,gen_0), stoi(51) )
    );
    GEN ep = FF_elltatepairing(ell,P,Q,torder);      // e(P,Q)
    GEN edp = FF_elltatepairing(ell,DP,Q,torder);    // e([2]P,Q)
    pari_printf("e(%Ps,%Ps) = %Ps\n", P, Q, ep);
    pari_printf("e(%Ps,%Ps) = %Ps\n", DP, Q, edp);
    pari_printf("e(%Ps,%Ps)^2 = %Ps\n", P, Q, FF_pow(ep,gen_2));

This produces the following output:

e([28, 51],[23*x + 45, 51]) = 42*x + 26
e([18, 13],[23*x + 45, 51]) = 18*x + 37
e([28, 51],[23*x + 45, 51])^2 = x + 33    // not equal to 18*x+37


Next, I tried to represent the points as vectors with t_POL elements in
the polynomial ring mod x^2 + 1. The modulus is irreducible in F_59:

    modulus = mkpoln(3,gen_1,gen_0,gen_1);
    P = mkvec2( mkpoln(1,stoi(28)), mkpoln(1,stoi(51)) );
    DP = mkvec2( mkpoln(1,stoi(18)), mkpoln(1,stoi(13)) );
    Q = mkvec2( mkpoln(2,stoi(23),stoi(45)), mkpoln(1,stoi(51)) );
    ep = FpXQE_tatepairing(P,Q,torder,pol_0(0),modulus,baseFieldSize);
    edp = FpXQE_tatepairing(DP,Q,torder,pol_0(0),modulus,baseFieldSize);
    pari_printf("e(%Ps,%Ps) = %Ps\n", P, Q, ep);
    pari_printf("e(%Ps,%Ps) = %Ps\n", DP, Q, edp);
    pari_printf("e(%Ps,%Ps)^2 = %Ps\n", P, Q,
    FpXQ_pow(edp,gen_2,modulus,baseFieldSize));

The output is:

    e([28, 51],[23*x + 45, 51]) = 26*x + 47
    e([18, 13],[23*x + 45, 51]) = 28*x + 51
    e([28, 51],[23*x + 45, 51])^2 = 24*x + 47   // not equal to 28*x+51

For comparison, a similar code in Sage (which uses PARI for these
computations), produces the correct result, the Sage's tate_pairing
function is bilinear:

    baseFieldExtension.<x> = GF(59^2, modulus=x^2+1);
    EE = EllipticCurve(GF(59),[0,1]).base_extend(baseFieldExtension)

    P = EE(28,51)
    DP = EE(18,13)
    Q = EE(23*x+45,51)

    print("e({},{}) = {}".format(P,Q,P.tate_pairing(Q,P.order(),2,59)))
    print("e({},{}) = {}".format(DP,Q,DP.tate_pairing(Q,P.order(),2,59)));
    print("e({},{})^2 = {}".format(P,Q,P.tate_pairing(Q,P.order(),2,59)
** 2))

The output is:

e((28 : 51 : 1),(23*x + 45 : 51 : 1)) = 40*x + 42
e((18 : 13 : 1),(23*x + 45 : 51 : 1)) = 56*x + 46
e((28 : 51 : 1),(23*x + 45 : 51 : 1))^2 = 56*x + 46   // e([2]P,Q) =
e(P,Q)^2

I would greatly appreciate any help and/or pointers to what I might have
missed.

thanks,

--

Aleksandr Lenin

-- 
With kind regards,

Aleksandr Lenin
Researcher
Information Security Research Institute
Cybernetica AS
Mäealuse 2/1, 12618 Tallinn, ESTONIA
www.cybernetica.eu