Ask Your Question
2

distortion map phi(x,y) = (-x, i*y) where i = sqrt(-1)

asked 2022-10-27 05:32:14 +0100

anonymous user

Anonymous

updated 2022-10-29 18:17:09 +0100

[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

edit retag flag offensive close merge delete

Comments

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

user5362 gravatar imageuser5362 ( 2022-10-27 15:10:20 +0100 )edit

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?


   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
user5362 gravatar imageuser5362 ( 2022-10-27 17:08:32 +0100 )edit

Thank you, Max, I have updated the question.

user5362 gravatar imageuser5362 ( 2022-10-28 03:09:23 +0100 )edit

The error is what the message says: p and q are not points of the same curve. Indeed p is a point of E59 and q is a point of E59sq. Convert p to a point of E59sq. And, please, fix the missing parentheses in your code.

Luca gravatar imageLuca ( 2022-10-28 21:59:05 +0100 )edit

Shouldn't it be simply?

F59sq.<u> = GF(59)[i]
E59sq = EllipticCurve(F59sq, [1,0])
def phi(x,y):
    return ( - x, y * u)

p = E59sq(25,30)
q = phi(p[0],p[1])
p.weil_pairing(q, 5)

It produces an error PariError: I already exists with incompatible valence, which may be a real question here.

Max Alekseyev gravatar imageMax Alekseyev ( 2022-10-29 18:23:15 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
2

answered 2022-10-31 01:12:10 +0100

user5362 gravatar image

It could be a problem with the Pari implementation.

The Weil pairing using the 'sage' algorithm provides the expected result:

sage: F59 = GF(59)
....: E59 = EllipticCurve(F59, [1,0])
....: F59sq.<u> = F59[i]
....: E59sq = EllipticCurve(F59sq, [1,0])
....: def phi2(p1):
....:     return E59sq( - p1[0], p1[1] * u)
....: p = E59sq(25,30)
....: q = phi2(p)
....: p.weil_pairing(q,5,'sage')
56*I + 46

It looks like the tate_pairing also returns the expected result:

sage: p.tate_pairing(q,5,2)
40*I + 42
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-10-27 05:32:14 +0100

Seen: 358 times

Last updated: Oct 31 '22