Re: What's the code for doing the reverse of this code over the altbn128 curve

[Laël Cellier <lael.cellier@gmail.com>]

Thank you. I suppose there’s no way to preserve the discrete logarithm 
if the point contains elements not in F_p(w) ?

This is because I need to use the algorithm 4.1 in 
https://eprint.iacr.org/2019/385.pdf page 8. And in needs a specific 
input point which mean either I can select the right F_p² that will be 
mapped to the expected F_p¹² or I select the right F_p¹² direct but in 
way that it can be mapped back to F_p²

Anyway, here’s the algorithm in Pari/ɢᴘ to try if a point is valid :

miller_function_eval(E, Q, m, P)={
local(bb, T, f, i, lambda, x2T, y2T, xTQ, yTQ, x, y);
    bb = binary(m);
    [x, y] = P;
    T = Q;
    f = 1;
    for(i = 2, #bb,
        lambda = (3*T[1]^2 + E.a4) / (2*T[2]);
        x2T = lambda^2 - 2*T[1];
        y2T = -T[2] - lambda * (x2T - T[1]);
        f = f^2 * (y - T[2] - lambda * (x - T[1])) / (x + 2*T[1] - lambda^2);
        T = [x2T, y2T];
        if (bb[i] == 1,
            lambda = (T[2] - Q[2]) / (T[1] - Q[1]);
            xTQ = lambda^2 - T[1] - Q[1];
            yTQ = -T[2] - lambda * (xTQ - T[1]);
            f = f * (y - T[2] - lambda * (x - T[1])) / (x + (Q[1] + T[1]) - lambda^2);
            T = [xTQ, yTQ];
        );
    );
    f = f * (x - T[1]);
    return(f);
}
pairing_invert(E,q,k,ell,d,x,v,A)={
local(r,s,u,x1,x2,y2,L,i);
    r = q^k;
    if (k % 2 != 0, print("embedding degree must be even!"); return; );
    s = q^(k/2);
    if (ellcard(E) % ell != 0, print("ell must divide #E(Fq)."); return; );
    if (d % ell != 0 || (s+1) % d != 0, print("Require ell|d and d|(q^k/2+1)."); return; );
    u = (v^((s+1)/d))^((s+1)/2);
    if (u^s != u, print("u not in F_{q^k/2}, there is no inversion."); return; );
    x1 = A[1] + u; x2 = A[1] - u;
    L = List();
    y2 = x1^3 + E.a4*x1 + E.a6;
    if (y2^((s-1)/2) == 1, listput(L,[x1,sqrt(y2)]); listput(L,[x1,-sqrt(y2)]); );
    y2 = x2^3 + E.a4*x2 + E.a6;
    if (y2^((s-1)/2) == 1, listput(L,[x2,sqrt(y2)]); listput(L,[x2,-sqrt(y2)]); );
    for(i = 1, #L,
        Q = L[i];
        if (ellorder(E,Q) == ell && miller_function_eval(E, A, d, Q) == v, return (Q); );
    );
    print("there is no inversion.");
    return;
}

Even if the implementation is incorrect miller inversion can work with 
the result of Weil pairing on this curve.





> This has nothing to do with the order of points, it simply identifies 
elements of F_p(w) that are in fact in F_p(i), and applies this to the 
coordinates of the points.
>
> Aurel