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 _______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE