Classic affine point compression, storing only the x-coordinate and a single bit of the y-coordinate, is claimed in two different U.S. patents:
- US 6,141,420: “The inventors have also recognized that the bandwidth and storage requirements of a cryptographic system utilizing elliptic curves can be significantly reduced where for any point P(x,y) on the curve, only the x coordinate and one bit of the y coordinate need be stored and transmitted, since the one bit will indicate which of the two possible solutions is the second coordinate.” The patent expired in 2014.
- US 6,252,960: claiming “1. A method of compressing elliptic curve data which includes X and Y coordinate data, the X coordinate data consisting of N bits and the Y coordinate data consisting of at least 1 bit, using (a) a generator polynomial, and (b) a digital processing computer with at least first and second registers, said method comprising:” The patent expired in 2018 and may have been invalid all along because of the patent above already outlining the idea.
The patents have all expired by now; there is no need to live in fear of point compression any longer.
Daniel J. Bernstein convincingly argued that there was prior art for point compression all along so that we wouldn't have needed to live in fear of the patents in the first place. But considering the patents are all expired now, this is all but irrelevant history. Ed25519, when introduced in 2011, had point compression (recovering the x-coordinate from a y-coordinate), and evidently no lawsuit followed.
Other, more elaborate forms of point compression for Edwards and Montgomery curves have been proposed as well, namely Decaf and Ristretto. They are not only more efficient (a compressed point takes one bit less than the bit length of a full coordinate to represent because only non-negative points are considered valid when decoding), but also guarantee landing on the prime-order subgroup when decoding. They have each been out there for over a year now and no patents applicable to them seem to exist. For the Decaf case, it seemingly spawned from a series of threads on the public moderncrypto curves mailing list in 2014 and the final paper in 2015, so that if a patent were filed, it'd have to take that prior art and discovery process into account; Ristretto itself builds on the ideas in Decaf.