[cryptography] Point compression prior art?

Thierry Moreau thierry.moreau at connotech.com
Mon May 16 23:37:56 EDT 2011

Zooko O'Whielacronx wrote:
> Have you seen DJB's "Irrelevant patents on elliptic-curve cryptography"
> http://cr.yp.to/ecdh/patents.html
> The section on "Point Compression" says:
> """
> Miller in 1986, in the paper that introduced elliptic-curve
> cryptography, suggested compressing a public key (x,y) to simply x:
> ``Finally, it should be remarked, that even though we have phrased
> everything in terms of points on an elliptic curve, that, for the key
> exchange protocol (and other uses as one-way functions), that only the
> x-coordinate needs to be transmitted. The formulas for multiples of a
> point cited in the first section make it clear that the x-coordinate
> of a multiple depends only on the x-coordinate of the original
> point.'' This is exactly the compression method that I use.
> Popular rumor states that point compression is covered by a subsequent
> Vanstone-Mullin-Agnew patent: US patent 6141420, filed 1994.07.29,
> granted 2000.10.31. What the patent actually claims are (1--28)
> encryption using an elliptic curve over a finite field of
> characteristic 2 with elements represented on a normal basis; (29, 36)
> communicating (x,y) on a curve by communicating x and having the
> receiver somehow compute y; (30--35, 37--41) communicating x and
> ``identifying information'' of y, such as one bit; and (42--52) some
> secret-key encryption mechanisms.
> My Curve25519 software never computes y, so it is not covered by the
> patent. It should, in any case, be obvious to the reader that a patent
> cannot cover compression mechanisms published seven years before the
> patent was filed.
> """
> DJB also has this page, which goes into more detail about 6141420:
> http://cr.yp.to/patents/us/6141420.html
> Contrary to the "filed 1994.07.29" above, the patent was actually
> filed January 29, 1997:
> http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=6,141,420.PN.&OS=PN/6,141,420&RS=PN/6,141,420
> Which means it expires January 29, 2017.

The 1994.07.29 filing was followed by the PCT/CA95/00452 filed on 
1995.07.31 which starts the 20 years patent term for the US patent 
6141420. This is what I infer from looking at the first page of the 
patent image.

> Regards,


- Thierry Moreau

CONNOTECH Experts-conseils inc.
9130 Place de Montgolfier
Montreal, QC, Canada H2M 2A1

Tel. +1-514-385-5691

More information about the cryptography mailing list