Re: [Cfrg] Patents and the new elliptic curves

Watson Ladd <watsonbladd@gmail.com> Wed, 17 September 2014 02:07 UTC

Return-Path: <watsonbladd@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C453D1A04A2 for <cfrg@ietfa.amsl.com>; Tue, 16 Sep 2014 19:07:12 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, LOTS_OF_MONEY=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id XAaQDCkaVeOg for <cfrg@ietfa.amsl.com>; Tue, 16 Sep 2014 19:07:10 -0700 (PDT)
Received: from mail-qg0-x22b.google.com (mail-qg0-x22b.google.com [IPv6:2607:f8b0:400d:c04::22b]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 993101A006F for <cfrg@irtf.org>; Tue, 16 Sep 2014 19:07:10 -0700 (PDT)
Received: by mail-qg0-f43.google.com with SMTP id a108so1005070qge.2 for <cfrg@irtf.org>; Tue, 16 Sep 2014 19:07:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=pvQofn8xCr2Z7sDUcfTJgFuiE0ORIpXTd8CAE2fJX44=; b=h8U3/n5xdHddnjRYnNu8NIoLTWEV/Rg/GInGtcSSQ8524jyZn8/j8aM6UX8cJ6Bywv jztl8lGP6oEWoAorsy41bEzEfFjDeHL4O9p+PPKu5LFmKnus8+exqTgFZ+vls4SIglw7 Fq5cc+5V0UJRIQdFG+GQqtF2GfuizU15KPYJYO/jJVPksXNjiR9uSbbl8bbp6OHYyqVB 7S8B4oAEnAHyUbQydKdcNpv3TEUt2QT1SZBlXJ2r/dFeKxM8cYl35ySOQiRVwVVpG84F 45JLiSkADDmsNghAKJVeqWmvn7cFsl7VxWfNhBOV7eLg/Woh4LqHWNQNIw1EdiueYr8G jDNQ==
MIME-Version: 1.0
X-Received: by 10.236.133.65 with SMTP id p41mr16128940yhi.73.1410919629821; Tue, 16 Sep 2014 19:07:09 -0700 (PDT)
Received: by 10.170.207.216 with HTTP; Tue, 16 Sep 2014 19:07:09 -0700 (PDT)
In-Reply-To: <2145381D-E1C4-4CFC-A26F-879D775E6558@shiftleft.org>
References: <2145381D-E1C4-4CFC-A26F-879D775E6558@shiftleft.org>
Date: Tue, 16 Sep 2014 19:07:09 -0700
Message-ID: <CACsn0cm9OUHc20S7K+m1M=fRYoY0=emD6thBziMZuNEJquP9-Q@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Michael Hamburg <mike@shiftleft.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/8EVlqilCKcAb8YvS6nrqLj9b54I
Cc: IRTF Crypto Forum Research Group <cfrg@irtf.org>
Subject: Re: [Cfrg] Patents and the new elliptic curves
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 17 Sep 2014 02:07:13 -0000

On Sep 16, 2014 2:56 PM, "Michael Hamburg" <mike@shiftleft.org> 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
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg