4
$\begingroup$

I'm currently using the BouncyCastle implementation in uncompressed mode, and considering releasing an optimized version of EC code that uses point compression.

It appears the only thing limiting me is licensing for EC point compression, since the math seems straightforward.

I'm waiting for a response from the BouncyCastle mailing lists, but would like to solicit feedback from anyone who is more knowledgable and experienced in this area.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Patents affect all implementations; if an algorithm is patented, you cannot get around that by writing your own implementation. $\endgroup$
    – cpast
    Commented Apr 20, 2015 at 17:37
  • $\begingroup$ (Twisted) Edwards form point compression shouldn't be covered by a patent, but you can't use it for the NIST curves. $\endgroup$
    – CodesInChaos
    Commented Apr 20, 2015 at 18:36
  • 1
    $\begingroup$ Related to this subject: When do ECC patents end? $\endgroup$
    – e-sushi
    Commented May 20, 2017 at 3:07

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.