3
$\begingroup$

I tried to implement the Miller's Weil Pairing algorithm in python using the book "An introduction to mathematical cryptography" by Hoffstein, Pipher and Silverman.

I tried my code with the example given in the book and I get the correct response.

enter image description here

I tried with another example but I have problems with it.
It is stated in the book that we must choose a random point S $\notin$ {0, P, -Q, P-Q}. I took the following elliptic curve $E : Y² = X³ + 3X + 8$ over the field $\mathbb{F}_{13}$.

$E(\mathbb{F}_{13}) = \{0, (1,5), (1,8),(2,3),(2,10),(9,6),(9,7),(12,2),(12,11)\}$

I tried to compute $e(P,Q)$ with $P = (1,5)$ and $Q = (12,2)$. As $-Q = (12,11)$ and $P-Q = (9,6)$, I tried with all the other points but I always have an error at some points in the computations because I end up with zeros at both numerator and denominator in this function.

enter image description here

There is probably something that I didn't understand or something wrong with my implementation. Could someone explain to me what is the problem ?
Here is my code with the first example that works and the second that causes the problem : http://tpcg.io/GZNfns

$\endgroup$
1
$\begingroup$

The reason your implementation fails is most likely because the result of the Weil pairing is 1 in this case, which is the most degenerate case and the one most likely to encounter division by zero errors.

Your elliptic curve $y^2 = x^3 + 3x + 8$ over $\mathbb{F}_{13}$ is cyclic. In this case, $P$ is a generator of $E$ (as is $Q$), and $P$ and $Q$ satisfy the relationship $Q = 4P$, so the Weil pairing is trivial: $$ e(P,Q) = e(P,4P) = e(P,P)^4 = 1^4 = 1 $$ (The second-to-last equality above follows from the antisymmetry property of the Weil pairing.)

If you want a non-trivial Weil pairing, you need a non-cyclic elliptic curve group, such as the curve from the first example. In cryptography one usually uses an elliptic curve defined over an extension of a prime field instead of a curve defined over a prime field, in order to guarantee that the group is non-cyclic.

|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.