Subject: [Cfrg] Elliptic Curve patents

From: Michael Scott <[email-masked]>
Date: Fri, 7 Oct 2016 10:57:03 +0100

I was just doing some checking on the status of patents as applicable to
Elliptic Curve Cryptography, and I came across the very impressive patent
portfolio of one Bernd Meyer.

http://patents.justia.com/inventor/bernd-meyer?page=2

See for example this one..

Cryptographic method with elliptical curves
<http://patents.justia.com/patent/8582761>
Patent number: 8582761
Abstract: A method determines an elliptical curve, suitable for a
cryptographic method. An elliptical curve to be tested is prepared. The
order of a twisted elliptical curve associated with the elliptical curve to
be tested is determined. It is automatically checked whether the order of
the twisted elliptical curve is a strong prime number. If the order of the
twisted elliptical curve is a strong prime number, the elliptical curve to
be tested is selected as an elliptical curve suitable for cryptographical
methods.
Type: Grant
Filed: March 6, 2007
Date of Patent: November 12, 2013
Assignee: Siemens Aktiengesellschaft
Inventors: Jean Georgiades, Anton Kargl, Bernd Meyer

Now I know that no-one here is a lawyer. But I would read this as
suggesting that Siemens holds a patent on twist secure curves (like
GoldiLocks).

Tell me it ain't so. And not just that, if you look at the full portfolio,
many other commonly used techniques for ECC are also covered.

Mike Scott

---

From: Kyle Rose <[email-masked]>
Date: Fri, 7 Oct 2016 08:20:39 -0400

> many other commonly used techniques for ECC are also covered.

There's prior art for curve25519 from as late as 2005:

https://cr.yp.to/talks.html#2005.05.19

No idea how this affects the other claims in the patent, but at least
generation of that curve predates the filing of this patent.

Kyle

---

From: Dan Brown <[email-masked]>
Date: Fri, 7 Oct 2016 12:32:25 +0000

how are "strong" primes defined here?

From: Michael Scott
Sent: Friday, October 7, 2016 5:57 AM
To: [email-masked]
Subject: [Cfrg] Elliptic Curve patents

I was just doing some checking on the status of patents as applicable to Elliptic Curve Cryptography, and I came across the very impressive patent portfolio of one Bernd Meyer.

Cryptographic method with elliptical curves<http://patents.justia.com/patent/8582761>
Patent number: 8582761
Abstract: A method determines an elliptical curve, suitable for a cryptographic method. An elliptical curve to be tested is prepared. The order of a twisted elliptical curve associated with the elliptical curve to be tested is determined. It is automatically checked whether the order of the twisted elliptical curve is a strong prime number. If the order of the twisted elliptical curve is a strong prime number, the elliptical curve to be tested is selected as an elliptical curve suitable for cryptographical methods.
Type: Grant
Filed: March 6, 2007
Date of Patent: November 12, 2013
Assignee: Siemens Aktiengesellschaft
Inventors: Jean Georgiades, Anton Kargl, Bernd Meyer

Now I know that no-one here is a lawyer. But I would read this as suggesting that Siemens holds a patent on twist secure curves (like GoldiLocks).

Tell me it ain't so. And not just that, if you look at the full portfolio, many other commonly used techniques for ECC are also covered.

Mike Scott

---

From: Michael Scott <[email-masked]>
Date: Fri, 7 Oct 2016 13:57:26 +0100

Hello Dan,

Here is another of Meyer's patents, that I think may cause a problem for a
method of multiplicative masking recommended by yourself and others (Scott
Fluhrer?) in the past, and commonly used for modular inversion in the
context of ECDSA signature

https://www.google.com/patents/US20080201398

Mike

On Fri, Oct 7, 2016 at 1:32 PM, Dan Brown <[email-masked]> wrote:

> *From: *Michael Scott
> *Sent: *Friday, October 7, 2016 5:57 AM
> *To: [email-masked]
> *Subject: *[Cfrg] Elliptic Curve patents
>

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 7 Oct 2016 15:53:34 +0200

"Michael Scott" <[email-masked]>:

> Here is another of Meyer's patents, that I think may cause a problem for
a method of multiplicative masking recommended by yourself and others
(Scott Fluhrer?) in the past, and commonly used for modular inversion in
the context of ECDSA signature
> https://www.google.com/patents/US20080201398

That idea certainly wasn't new in 2005.

Bodo

---

From: "D. J. Bernstein" <[email-masked]>
Date: 7 Oct 2016 23:13:38 -0000

Michael Scott writes:
> But I would read this as suggesting that Siemens holds a patent on
> twist secure curves (like GoldiLocks).

https://cr.yp.to/talks/2001.10.29/slides.ps gives an example of a curve
for ECC selected with 16*prime order. It summarizes the performance of
the Montgomery ladder and says "Twist has order 8*prime, so don't need
to check whether compressed input K_b is on curve."

https://groups.google.com/forum/message/raw?msg=sci.crypt/mu_paShEU3w/m491pYxHbtAJ
has a similar comment.

As far as I know, the first attempt to patent twist security was
http://www.freepatentsonline.com/DE10161138A1.html, but this was filed
in Germany after my slides were posted, so the slides automatically
count as prior art even if the "inventors" claim that they were first.

In the US, back then, there was a 1-year period after publication when
other people were free to file a patent on the same idea, as long as
they claimed that they had invented it earlier. For some reason this
1-year period was called a "grace period" rather than a "fraud period".
Anyway, Germany never had any similar rule, and as far as I know these
"inventors" didn't start filing for ECC patents in the US until many
years later.

---Dan