# Frey-Rück Attack - Tate-Lichtenbaum 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^*$

I can answer your very first question on why $$\tau_\ell(P,P')$$ is an $$\ell$$th root of unity. If I'm not mistaken, they are assuming in the paper that $$E(\mathbb F_q)[\ell]$$ (the $$\ell$$-torsion points in $$E(\mathbb F_q)$$) is a cyclic group.
(In general, if $$\ell$$ and $$q$$ are coprime, $$E[\ell]\cong (\mathbb Z/\ell\mathbb Z)^2$$ has order $$\ell^2$$, and all its proper subgroups have order $$\ell$$.)
Therefore if $$P$$ has order $$\ell$$ and $$E(\mathbb F_q)[\ell]$$ is cyclic, then $$P$$ is a generator of this group. This is important, because of the domain of the Tate-Lichtenbaum pairing: $$\tau_\ell\colon E(\mathbb F_q)[\ell] \times E(\mathbb F_q)/\ell E(\mathbb F_q)\to \mu_\ell.$$
(this is also why every output of $$\tau_\ell$$ is an $$\ell$$th root of unity. To get an $$\ell^k$$th root, we'd have to use $$\tau_{\ell^k}$$.)
So assume $$\tau_\ell(P,P')=1$$ (if not, it is automatically a primitive $$\ell$$th root of unity). Then for every $$u=1,\dots,\ell$$, $$\tau_\ell(uP,P')=\tau_\ell(P,P')^u=1$$. But the non-degeneracy of $$\tau_\ell$$ implies $$P'\in\ell E(\mathbb F_q)$$, say $$P'=\ell P_1$$, $$P_1\in E(\mathbb F_q)$$. It follows that $$\ell^{k+1}P_1=\ell^k P'=\infty$$. This is a contradiction, because $$\ell^{k+1}$$ cannot be the order of a point (because it does not divide $$\#E(\mathbb F_q)$$), and then $$\ell^kP_1=\ell^{k-1}P'=\infty$$! Therefore $$\tau_\ell(P,P')\neq 1$$.
Finally, $$P'$$ can never be $$iP$$ or $$jQ$$ (because the first has order $$\ell^k$$, and the others have orders dividing $$\ell$$). The paper specifies that $$\ell\neq 2$$, and then $$2P'$$ also has order $$\ell^k$$, and the same argument holds.