Subject: [lamps] Potential IPR on accelerated ECDSA verification

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 12 Mar 2021 18:57:19 +0000

During the working group meeting, I brought up the possibility of an existing Certicom patent that may partially cover this idea.  In the chat, I listed one patent number (which I found during a quick search while the presentation was going on); I now suspect that patent number was incorrect.

Taking the time for a fuller search, I found the patent US20110194694A1, which appears to be similar to René's ideas.  In particular, it has the verifier

  *   Recovering both R (the ephemeral public key point) and the s value
  *   Using Shamir's trick to accelerate the verification (which I believe is what René is doing as well)
  *   They also consider the idea of encoding the "compression bit" in s (see paragraph 0086)

Now, there are differences:

  *   They don't note the idea that someone without the private key could convert an ECDSA signature to an ECDSA* signature
  *   They don't address batch verification.

I am not stating an opinion whether this patent covers René's idea (and I am not affiliated with Certicom); I am just bringing it to the working group's attention.

If the working group decides that the IPR concerns are moot, I am strongly in favor of making this a work item.

---

From: Rene Struik <[email-masked]>
Date: Fri, 12 Mar 2021 14:43:01 -0500

Hi Scott:

During my presentation, you apparently referred to US #8738912, which 
colloquially is referred to as "point compression". This patent is  
continuation of applications with original filing date Oct 17, 1997 
(almost 22 1/2 years ago).

Intent with my draft is to "promote good, altruistic behavior" (i.e., 
have everyone produce signatures so that those verifiers who wish to 
capture performance rewards are facilitated to do so), where - with 
ECDSA - the "malleability" feature (which was once considered a bug, but 
is really a feature now) makes this easy. To my knowledge, there is no 
intellectual property reason (real or perceived) that would dissuade 
implementors to switch this on on the signing side; what implementors do 
on the verification side is up to them (nobody has to implement 
speed-ups, if they do not want to).

The generic batch verification ideas are quite old and have appeared in 
various guises well before the year 2000.

 From a quick glance, I don't think your reference below refers to 
ECDSA. Most relevant ideas on ECDSA speed-ups have been presented early 
2005 (16+ years ago).

Best regards, Rene

On 2021-03-12 1:57 p.m., Scott Fluhrer (sfluhrer) wrote:
>
> During the working group meeting, I brought up the possibility of an 
> existing Certicom patent that may partially cover this idea.  In the 
> chat, I listed one patent number (which I found during a quick search 
> while the presentation was going on); I now suspect that patent number 
> was incorrect.
>
> Taking the time for a fuller search, I found the patent 
> US20110194694A1, which appears to be similar to René’s ideas.  In 
> particular, it has the verifier
>
>   * Using Shamir’s trick to accelerate the verification (which I
>     believe is what René is doing as well)
>   * They also consider the idea of encoding the “compression bit” in s
>     (see paragraph 0086)
>
>   * They don’t note the idea that someone without the private key
>     could convert an ECDSA signature to an ECDSA* signature
>   * They don’t address batch verification.
>
> I am not stating an opinion whether this patent covers René’s idea 
> (and I am not affiliated with Certicom); I am just bringing it to the 
> working group’s attention.
>
> If the working group decides that the IPR concerns are moot, I am 
> strongly in favor of making this a work item.
>
>
> _______________________________________________
> Spasm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/spasm

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867