[cryptography] Point compression prior art?

Zooko O'Whielacronx zooko at zooko.com
Tue May 3 14:59:35 EDT 2011


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.

Regards,

Zooko



More information about the cryptography mailing list