distortion map phi(x,y) = (-x, i*y) where i = sqrt(-1)
[Question updated to reflect progress]
This question relates to implementing a distortion map between a finite field and an extension field in the context of bilinear pairings on super singular curves.
The numerical example comes from Ben Lynn's thesis[1], from p. 38-49, and involves subject matter discussed on p. 54.
The math context is as follows:
Given:
E: Y^2 = X^3 + X over F59
G = {(25, 30), (35,31), (35, 28), (25, 29), 0 }, the 5-torsion group in F59
phi(x,y) = (-x, y * i ), where i = sqrt(-1)
the pairing function f(...) can be called on p, q, in G by applying the distortion map on q, thus
m = f(p, phi(q))
For example:
if p = G(25, 50),
let : q = phi(25,30) = (-25, 30 *i)
m = f(p,q) = f((25,30), (-25, 30*i)) = 46 + 56 * i
The distortion map can be verified to work:
LHS: Y^2 = (30*i)^2 = 30^2 * i^2 = 900 * (-1) mod 59 = 44
RHS = (-25)^3 -25 = -15625 - 25 (mod 59) = 44
LHS == RHS.
I'd like to implement and extend this example in sagemath, including performing point conversion and invoking the weil pairing.
I have attempted variations on the following simple approach (discussion of background appears in comments, below):
F59 = GF(59)
E59 = EllipticCurve(F59, [1,0])
F59sq.<u> = GF(59)[i]
E59sq = EllipticCurve(F59sq, [1,0])
def phi(x,y):
return ( - x, y * u)
p = E59(25,30)
q = phi(p[0],p[1])
#conversion problem:
q = E59sq(F59sq(q[0]), F59sq(q[1]))
p.weil_pairing(q, 5)
The problem appears in the pairing function, with the point created on E59sq.
I receive the following error:
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-3-1d9ffe6c337c> in <cell line: 12>()
10
11 q = E59sq(F59sq(q[Integer(0)]), F59sq(q[Integer(1)]))
---> 12 p.weil_pairing(q, Integer(5))
~/mambaforge/envs/sage/lib/python3.9/site-packages/sage/schemes/elliptic_curves/ell_point.py in weil_pairing(self, Q, n, algorithm)
1621
1622 if Q.curve() is not E:
-> 1623 raise ValueError("points must both be on the same curve")
1624
1625 if algorithm is None:
ValueError: points must both be on the same curve
Question 1: Can someone explain the error, and assist in making the demonstration work ?
Question 2: The sagemath documentation [2] uses an approach such as:
phi=Hom(F,Fx)(F.gen().minpoly().roots(Fx)[0][0])
Px=Ex(phi(P.xy()[0]),phi(P.xy()[1]))
I am not sure how this works, but somehow it seems to have potential. Can someone explain this construction, and perhaps how it can be applied to the example above?
Question 3: If you were approaching this problem and sought a balance of "communicative code", and idomatic sagemath", how would you approach it?
Thanks in advance.
[1] crypto.stanford.edu/pbc/thesis.pdf
[2]doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/ell_point.html
Thanks Max. I have edited the code above to fix it, and add your suggestion. When I run it now it has a new error ("points must be on the same curve"). Running it a second time results in a different error ("PariError: I already exists with incompatible valence")
I wonder, would it be best to keep away from
i
and perhaps use a different label? As well, if I may ask -- how would the code best be implemented for goals of being clear as well as idiomatic in sagemath?Thanks again
Thanks I changed the label. It makes the 'valence' error go away. Still now, there is the "points must be on the same curve" error. Why is this occuring, and what should I do to fix it?
Thank you, Max, I have updated the question.
The error is what the message says:
p
andq
are not points of the same curve. Indeedp
is a point ofE59
andq
is a point ofE59sq
. Convertp
to a point ofE59sq
. And, please, fix the missing parentheses in your code.Shouldn't it be simply?
It produces an error
PariError: I already exists with incompatible valence
, which may be a real question here.