[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
EC over F2**m, m composite
Hi Hilarie,
> The groups provide both hardware and software benefits.
I think efficiency is a secondary issue in this debate
since obviously efficiency is no good without security.
But it seems like the added efficiency offered by curves
over F2m, m composite, is questionable. We spent years
trying to find significant benefits and eventually gave
up. Which software programs or hardware devices implementing
m composite do you have in mind? I'd like to compare them
with our implementations in software toolkits and smart
cards.
> The issue of their security is something that will be discussed
> at SAC next week, and no motivation for a hasty change to the
> standard is indicated based on information provided to date.
It seems to me like enough people have expressed strong
fears about these curves to warrant removing them. The
ATM forum recently reached the same conclusion and
removed these curves. At the very least surely we shouldn't
facilitate only the use of suspect curves?
We are ready to propose alternative curves over F2**163
and F2**191 as well as Fp for 160 and 192-bit prime.
I'm forwarding a note I received from Simon Blake-Wilson,
one of our math junkies, which goes into more details on
the problem.
Best regards,
Yuri
___________________forwarded note_______________________
We don't supply curves over F2m, m composite, because all
the theory experts we speak to seem very concerned about
these curves. Many have made concrete statements in the
literature to this effect:
Gerhard Frey - THE big man of this stuff - mentioned the
issue in his invited talk at EuroCrypt 97. He strongly
recommended avoiding the curves because he believes there
is a subexponential time algorithm for the ECDLP over F2m
m composite. In particular he stated his belief that the
following approach would prove successful: exploit the Weil
descent to embed the curves in a high genus hyperelliptic
curve over the subfield, then use the Adleman-Huang
algorithm to solve the log problem on this curve.
(He's talking about Weil descent again at the Waterloo
workshop in September.)
These fears were also expressed by Claus Schnorr in his
rump session talk at Crypto 97. He exploited analogous
subfield structures to break the Chor-Rivest knapsack
and conjectured that these structures could well give
rise to similar weaknesses in the ECDLP over F2m m
composite.
Other experts who have publicly expressed their concerns
include:
Volker Mueller and Sachar Paulus in their paper "On the
generation of cryptographically strong elliptic curves"
available from
http://www.informatik.th-darmstadt.de/TI/Mitarbeiter/vmueller.html
Erik De Win, Serge Mister, Bart Preneel, and Mike Weiner
in their paper at ANTS 98 "On the performance of signature
schemes based on elliptic curves".
Although none of these references actually break the ECDLP
on curves over F2m m composite, it seems like we'd be
pretty stupid to ignore the advice of all these clever
people!
(The only concrete results on these curves so far are
minor improvements due to Gallant/Lambert/Vanstone
and Wiener/Zuccherato. These results were presented
at EuroCrypt 98 and will be presented again this week
at SAC. They're elegant results but in no way fatal to
security.)
References: