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.


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.