# Frey-Rück Attack (FR-Reduction) - Tate Pairing

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,
Luca