I am trying to understand the Frey-Rück attack and found different ways of a possible implementation. Since I am not yet very familiar with the Tate-Lichtenbaum pairing and the theory of divisors I wanted to ask which one of the different realizations of the FR reductions is the most efficient or ''prettiest'' in your opinion.

In the following let $E/\mathbb{F}_q$ be an elliptic curve and $P$ a point of prime order $l$. Let $Q=n P$ with $n\in\mathbb{Z}$. And $\tau(*,*)$ is the modified Tate-Lichtenbaum pairing.

The FR-Attack as presented in ''The Tate Pairing and the Discrete Logarithm Applied to Elliptic Curve Cryptosystems'':

Suppose that $l^k$ is the exact $l$-power dividing $\#E(\mathbb{F}_q)$ with $k>1$. (The case $k=1$ is ''easy'' since we have in this case that $\tau_l(P,P)$ is a primitive $l$th root of unity.)
Suppose $P'\in E(\mathbb{F}_q)$ is any point of order $l^k$. In this case $\tau_l(P,P')$ is a primitive $l$th root of unity. (*)
Now calculate $\tau_l(P,P')$ and $\tau_l(Q,P')$ with the divisors $D_P=(P)-(\infty)$ , $D_Q=(Q)-(\infty)$ and $D_{T'}=(2P')-(P')$. Here $2P'$ or $P'$ can never be $iP$ or $jQ$, so we can calculate the pairings without any problems and get as above the DLP $\tau_{l}(Q,P') = \tau_l(P,P')^n$ in $\mathbb{F}_q^*$.

My first question is why (*) holds. Why is $\tau_l(P,P')$ a primitive $l$th root of unity if $P'$ has order $l^k$?
And why can $2P'$ and $P'$ never be $iP$ or $jQ$? Because of their order?

And in Steven Galbraith ''Supersingular Curves in Cryptography'' he does not specify this proposition, but rather picks random points $P'\in E(\mathbb{F}_q)$ until $\tau_l(P,P')$ is a primitive $l$th root of unity. I'm asking myself which way is more efficient? Since in Frey's version it seems more costly to look for this specific point $P'$ of order $l^k$ rather than trying random $P'$.

In the paper of Ryuichi Harasawa et al. ''Compairing the MOV and FR Reductions in Elliptic Curve Cryptography'' they work with two random points to calculate the DLP:

  1. Determine the embedding degree $m$, i.e. the smallest integer such that $n|q^m-1$. Define $k:=\mathbb{F}_{q^m}$.

  2. Pick $S,T\in E(k)$ randomly (not equal to $P,Q$ or the point at infinity $\mathscr{O}$).

  3. Compute two rational functions $f_P$ and $f_Q$ such that $div(f_P) = l(P)-l(\infty)$ and $div(f_Q) = l(Q)-l(\infty)$.

  4. Compute $\alpha = \big(\frac{f_Q(S)}{f_Q(T)}\big)^{\frac{q^m-1}{n}}$ If $\alpha=1$ return to Step 2.

  5. Define $\beta := \big(\frac{f_P(S)}{f_P(T)}\big)^{\frac{q^m-1}{l}}$

  6. Solve the DLP $\beta = \alpha^n$ in $k^*$

Thank you and all the best,


Your Answer

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

Browse other questions tagged or ask your own question.