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