ECC patents?

[Bodo Moeller]

On Sun, Oct 16, 2005 at 12:41:46AM +0200, Alexander Klimov wrote:

>   US 6,141,420 "Elliptic Curve Encryption Systems" pertains to
>   point compression
[...]
> From my POV point compression in the EC(GF_p) case is absolutely
> trivial, but the case of EC(GF_{2^p}) probably is less so. In any
> case, there is no problem to implement ECDSA and ECDH without
> point compression.
> 
> Any pointers to prior art about at least point compression in
> EC(GF_p)?]

US patent 6,141,420 (Vanstone - Mullin - Agnew) was filed on
January 29, 1997, but

    This is a continuation of PCT/CA95/00452, filed on Jul. 31, 1995,
    which is a continuation-in-part of Ser. No. 08/282,263, filed on
    Jul. 29, 1994, now abandoned.

so possibly the July 1994 filing date is the one that counts.  By the
US one-year grace period for filing patents after publication, this
means that relevant publications before July 1993 can serve as prior
art to invalidate the patent claim.

The idea that you can do ECDH with x-coordinates only already appears
in one of the two original papers first suggesting elliptic curve
cryptosystems (Victor Miller, CRYPTO '85).  The idea to use one bit to
compress a specific y-coordinate is newer -- it appears in Harper,
Menezes, Vanstone, "Public-Key Cryptosystems with Very Small Key
Lengths", EUROCRYPT '92 (LNCS 658).  The technique for the GF(p) case
is described here.  The printed proceedings for this conference (held
in May 1992) were published by Springer-Verlag in February 1993, so
this case is quite clear.

For the GF(2^m) case, however, I am not aware of prior art.  Hence,
point compression for binary curves is not available in standard
compilations of OpenSSL.


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com