[cryptography] Point compression prior art?
zooko at zooko.com
Tue May 3 14:59:35 EDT 2011
Have you seen DJB's "Irrelevant patents on elliptic-curve cryptography"
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:
Contrary to the "filed 1994.07.29" above, the patent was actually
filed January 29, 1997:
Which means it expires January 29, 2017.
More information about the cryptography