[Cfrg] Patents and the new elliptic curves

[Michael Hamburg <[e-mail]>]

Hello CFRG,

I’m concerned about patent issues which may affect the new elliptic curve standards.

There has been a side discussion involving several members of this list, including some Microsoft researchers, on the subject of what patents may apply to proposed curves and their implementations and in particular to the NUMS curves.

Microsoft has a policy of avoiding patent searches, not reading patents, not commenting on patents etc, so they have not been particularly helpful.  However, I am concerned that the Microsoft-held US7602907 (and possibly foreign equivalents) may apply to their implementation, covering the mLSB combs algorithm.  Benjamin Black has refused to confirm or deny this.  The NUMS code itself is still usable under the Apache2 license, but it has a "mutually assured destruction” clause, and other implementations might infringe.

So I have a few questions for the list.  First, am I right to be concerned that US7602907 reads against the NUMS code?  How does this interact with the BCP, since the curve’s spec does not require the patent, but the reference implementation does?

Second, is anyone aware of other patents that may read on SafeCurves-style Montgomery or (twisted) Edwards implementations, especially of the proposed curves (\w+)25519, Curve41417, MS NUMS, Ed448-Goldilocks or E-521?  It is required that new curves be efficiently and securely implementable without stepping on such patents, so it is critical to know what they are.

Third, given that mLSB combs may be encumbered, does anyone have information on the patent status of other state-of-the-art comb algorithms?  I’m particularly hoping that the signed all bits set (SABS) combs algorithm used in Goldilocks is patent-free, but I have only conducted a limited search.

Thanks,
— Mike Hamburg