[curves] Second day NIST workshop notes

[Ben Smith]

Hi All,

2015-06-12 21:08 GMT+02:00 Michael Hamburg <mike at shiftleft.org>:
> FourQ: Four-dimensional decompositions on a Q-curve
>
> Want to apply all existing tricks to get a fast curve without compromising security.  Uses GF((p^127-1)^2).  Cofactor is 392 = 2^3 * 7^2.  Complete formulas.  Discriminant -40.  Two endomorphisms: CM and Frobenius (I think?) gives 4-dimensional decomposition.  Roughly 122-bit generic security.  Claim is that unlike GLV and GLS, the endomorphisms don’t help rho, because they’re slightly slower.  Extension field is only quadratic so no Weil descent.  Recoding in constant time.

...so it's not my work, of course, but I think I can clarify something
here on the endomorphisms, and on the claim that the endomorphisms
don't help rho.

TL;DR: they don't help rho, but not because they're slower.

First, the endomorphisms in question: The curve has CM by
ZZ[\sqrt{-10}] (so discriminant -40).  The cute thing is that the
\sqrt{10} factors into a 2-isogeny followed by a 5-isogeny (and also
as a 5-isogeny followed by a 2-isogeny).  So if E/FF_{p^2} is their
curve, then there is
* a 2-isogeny \phi_2: E \to E_1, and
* a 5-isogeny \phi_5: E \to E_1;
...and E_1 is the Galois conjugate of E over FF_p, so you also have
* a p-power Frobenius E_1 \to E.
(I like to see this as the reduction mod p of the intersection of two
families of QQ-curves, but there's no need to look at things that
way.)

Composing that p-powering with \phi_2 and \phi_5 yields endomorphisms
\psi_2 and \psi_5, respectively.  If you compose them then you get (up
to sign) \sqrt{10}\pi, where \pi is the p^2-power Frobenius---which
acts trivially on the rational points.

So the natural collection of fast endomorphisms to use for the
4-dimensional decomposition is [ 1, \psi_2, \psi_5, \sqrt{-10} ].
Computing \psi_2 is only as hard as computing a 2-isogeny, \psi_5 as
hard as computing a 5-isogeny, and \sqrt{-10} you can do by recycling
the 5-isogeny and computing another 2-isogeny, as Craig noted during
his talk.


Now, about endomorphisms+Pollard: In his talk Craig said (IIRC)
"typical GLV" and GLS help rho.  The idea being that typical GLV
usually means using an automorphism of order 3 or 4 (ie, j-invariant 0
or 1728) for the accelerating endomorphism, and then that automorphism
can be used for something like Duursma--Gaudry--Morain, where you run
your dlog algorithm using equivalence classes mod the automorphism (in
much the same way as you would normally use the negation map).  This
can give you a small speedup.

When it comes to GLS you don't have an automorphism, but the GLS
endomorphism psi acts like an order-4 automorphism on the group of
rational points (ie, psi^4 = (-Frobenius)^2 which acts as 1), so you
should be able to use it in the same way to speed up Pollard rho or
BSGS.

When you go to GLV endomorphisms of higher degree, or the
endomorphisms that appear in QQ-curve reductions, then the analogous
technique doesn't work.  Suppose we have an elliptic curve E/FF_q,
with a subgroup G of E(FF_q) of prime order r, say, and a fast
endomorphism phi on E with eigenvalue lambda on G.  You still get
obvious equivalence classes (like {P, \phi(P), ..., \phi^{n-1}(P)}
where n is the order of lambda in (ZZ/rZZ)^*), but
1) they can be ridiculously large (worst case: lambda is a generator
of (ZZ/rZZ)^*, in which case the equivalence class of P is G - 0,
which doesn't help at all), and
2) it's important to be able to be able to compute a canonical
representative for the equivalence class (for checking if you've hit
distinguished points) or to be able to test equality mod the
equivalence---and this problem gets painful as the classes get larger
and the endomorphisms get trickier.

This is a question we've had to deal with for RM endomorphisms in
genus 2, and the original QQ-curve reductions, and the answer is the
same.  Automorphisms are bad, fast endomorphisms of higher separable
degree are ok.


Cheers,

ben

-- 
You know we all became mathematicians for the same reason: we were lazy.
  --Max Rosenlicht