Re: [Cfrg] Patents and the new elliptic curves

[Watson Ladd <[e-mail]>]

On Sep 16, 2014 2:56 PM, "Michael Hamburg" <[e-mail]> wrote:
>
> 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.

I am not a lawyer. I am not a patent lawyer. The slimiest schyster on
late night TV promising to get rid of your DUI is more of a lawyer
than I am. If you consider making any decision on the basis of what I
write, you are an idiot.

Most of this is due to DJB.

Now that we have said that, let me explain the patent situation as I
see it, regarding Montgomery ECC. The invention of ECC was in 1985:
the use of the x-coordinate only representation was mentioned in the
original paper. The use of Montgomery form to calculate on elliptic
curves was introduced in 1985 as well. It's possible someone files a
patent on the combination, but I cannot imagine that being a very
viable claim.

The efficiency gains from use of a special prime of the form 2^x-s
with s small were mentioned in a paper of Bender and Castagnoli in
1990, who didn't bother to mention how the this happened. Any claims
on particular algorithms are going to be difficult to make,
particularly if the algorithm is a specialization of Barrett reduction
because of this paper. It's not as clear as I would like.

When it comes to Edwards form, the formulas were published in 2007.
However, DJB didn't patent them in the US and is the inventor. I don't
know about other faster formulas. The situation for the primes is the
same as for Montgomery form. As for the exponentiation algorithms,
they are all in Knuth.

The signatures in Ed25519 are variants of Schnorr signatures, and the
patent expired in 2008.

In conclusion I am not worried about the patent issue for tweetnacl.c

>
> 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.

Aren't the good algorithms in  Knuth, volume 2, due to Pippenger in
1976? In particular with complete addition laws there is no need to
worry about adding the identity, so many of the modifications in
things like signed wNAF are not needed. Of course, they may not be the
world's most efficient, but that's likely to be fine to get fast
enough.

Sincerely,
Watson Ladd

>
> Thanks,
> — Mike Hamburg
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg