IP: more on : Elliptic Curve 97-bit Challenge Broken

[David Farber <farber () cis upenn edu>]

> Date: Tue, 28 Sep 1999 21:18:49 -0700
> From: Seth David Schoen <schoen () loyalty org>
> To: David Farber <farber () cis upenn edu>
> Subject: Re: IP: Elliptic Curve 97-bit Challenge Broken
>
> The INRIA release (forwarded by Dorothy Denning) says:
>
> > Led by Robert Harley, a member of the Cristal project at INRIA, France's
> > National Institute for Research in Computer Science and Control, the 195
> > researchers involved showed that a 97-bit encryption system based on
> > elliptic curves is more difficult to crack than a 512-bit system based
> > on integers such as RSA-155.
>
> Actually, they did not "show" this in the most important sense, which is
> the mathematical sense.  They showed that, using generally available
> techniques, they found it more difficult; they did not show that the
> problem is inherently more difficult.
>
> This distinction is important because powerful organizations trying to
> decrypt a message might have access to mathematical techniques which are
> not known to the general public.  (Public-key cryptography itself was
> discovered in the classified world years before Diffie and Hellman
> independently developed it.)   So relying on how long different public
> cracking attempts took is not a reliable way to compare the strengths of
> two cryptosystems.
>
> The release itself notes this later on:
>
> > "Ideally we would like new theoretical advances to
> > further reinforce these practical results, although such advances appear
> > out of reach for the moment." (A. Lenstra)
>
> These "theoretical advances" are what ultimately matter, because the real
> strength of any crypto algorithm depends largely on its mathematical
> properties.  These mathematical properties can be determined only through
> theoretical research, not by experiment.  It's still not known whether various
> classes of problems used for public-key crypto are inherently easier than,
> harder than, or just as hard as other such classes.
>
> > The aim of the
> > challenge is to encourage research in the field of elliptic curves and
> > their applications in encryption, and to strengthen arguments in favor
> > of using elliptic curve cryptography instead of systems based on integer
> > factorization.
>
> It's worth noting that the US patent on the most widely used "system based
> on integer factorization" expires next year.  ECC algorithms are not, to
> my knowledge, patented here.
>
> --
> Seth David Schoen <schoen () loyalty org>  | And do not say, I will study when I
>     http://www.loyalty.org/~schoen/    | have leisure; for perhaps you will
>     http://www.loyalty.org/   (CAF)    | not have leisure.  -- Pirke Avot 2:5