[Cfrg] patent situation regarding hash2curve as used in some PAKE nominations

[Björn Haase <[e-mail]>]

Dear Riad,

I think that it’s best to continue our private discussion on the list.

> Riad Wahby wrote:
>
>I agree with you that the generic description in Section 6.5.2 of
>the 04 draft is similar to what's in the patent. I was
>thinking of the version for p = 3 mod 4 that's described in Appx.
>D.2 (which is based on WB19, and can be generalized to other p.)
>
>- Compute x1 = X1(t), x2 = X2(t), and g(x1) in the usual way
>- Compute tmp = g(x1) ^ ((p + 1) / 4)
>- If tmp**2 == g(x1), return (x1, tmp)
>- Else return (x2, t^3 * tmp)
>
>In other words, there's no explicit square test or sqrt(g(x2))
>computation. Instead, we compute a value that's either the sqrt
>of x1 or close to the sqrt of x2, and choose the correct one by
>computing a square and checking for equality.

Yes. This seems very reasonable. When re-reading the claim 13 of US 8.718.276 B2 (copied below), I see three points, where a significant difference will be generated when using D.2 from WB19.
1.)	If we only use the X coordinate, we are safely out of the scope of the patent.
2.)	If the case distinction is not based on a square test for f(X1) but based on another condition.
3.)	If there is no square-root calculation taking f(X2) or f(X1) as input.
In addition as fourth distinction to the patent, the sign of the y-coordinate will also be changed depending on the parameter t. This is not what is claimed in the patent. All of these differences are significant in my opinion.

With this approach for curves with p = 3 mod 4, with the method of D.2 I conclude that we are safely out of the scope of the patent.
The algorithm from appendix D.2 of your paper for p = 3 mod 4 is also more efficient than the claimed method.
Also for p != 3 mod 4  (e.g. P-384) when using generic simplified SWU we have differences between the patent and draft 04, but it’s still somewhat similar. We probably might be better off with avoid simplified SWU for P-384.

In any case choosing “-1” as non -square value must be avoided due to US 8,712,038 B2.

All of this together might mean that for choosing the mapping algorithm for a curve while safely keeping out of the patent scope, we might need a decision tree and could not use a “one-size-fits-it-all” approach:

-	If Edwards or Montgomery curve: Use Elligator2
-	If p mod 4 == 3: Use accelerated SWU based on D.2 of WB19
-	Otherwise for short Weierstrass with p mod 4 != 3, use generic SWU
-	… special treatement of paring-friendly-curves ...

In order to avoid problems on the protocol-level, we should probably not recommend using P-384 in conjunction with protocols requiring mappings.

Regarding the PAKE protocol candidates, in my opinion a safe approach might be the following to avoid the patent pitfalls:
-	In OPRF constructions as used for salt blinding, specify use of an x-coordinate-only Diffie-Hellman algorithm on all curves.
This keeps “OPAQUE”, “B-SPEKE” and “strong AuCPace” safely out of the scope.
-	Don’t specify cipher-suites using P-384 for PAKE algorithms requiring mapping algorithms but recommend only Edwards/Montgomery curves or Short-Weierstrass curves with p = 3 mod 4, such as BrainPool, P-256 and P-521.
-	If possible, specify the protocols only for x-coordinate-only variants of EC Diffie-Hellman (applies to SPEKE, CPace, AuCPace). (Doing so also will restrict possible invalid-curve attacks to the quadratic twists and possibly allow for faster point verification.)

Here again for reference the claims of the Icart/Coron patent with highlighting (//  highlighted text //) for points that would make the difference:

13.) A method for obtaining, with an electronic component, a point P(X // ,Y //) on an elliptical curve satisfying the equation Y^2 = f(X) and starting from polynomials X_1(t), X_2(t), X_3(t) and U(t) satisfying the Skalba equality: f(X_1(t)) * f(X_2(t)) * f(X_3(t)) = U(t)^2
In the finite field F_q for any value of t, the method comprising choosing the polynomials that satisfy Skalba’s equality such that the value of X_3(t) for any value of t is such that f(X_3(t)) is never a squared term in F_q, the method further comprising:
(a)	Selecting a parameter t;
(b)	Calculating X_1=X_1(t) and X_2 = X_2(t);
(c)	// Determining if the term f(X_1) is a squared term in the finite field F_q, // 
// If  (c) is true, then: //
   (d1) // calculating the square root of the term f(X_1) , and //
   (d2) assigning point P with an abscissa equal to X_q  // and an ordinate equal to the square root of the term f(X_1) //
// If (c) is not true, then: //
   (d3)  // calculating the square root of the term f(X_2) , and // 
   (d4) assigning point P with an abscissa equal to X_q // and an ordinate equal to the square root of the term f(X_2) //




Mit freundlichen Grüßen I Best Regards 

Dr. Björn Haase 

Senior Expert Electronics | TGREH Electronics Hardware
Endress+Hauser Conducta GmbH+Co.KG | Dieselstrasse 24 | 70839 Gerlingen | Germany
Phone: [phone] | Fax: [phone]
[e-mail] |  www.conducta.endress.com 



Endress+Hauser Conducta GmbH+Co.KG
Amtsgericht Stuttgart HRA 201908
Sitz der Gesellschaft: Gerlingen
Persönlich haftende Gesellschafterin:
Endress+Hauser Conducta Verwaltungsgesellschaft mbH
Sitz der Gesellschaft: Gerlingen
Amtsgericht Stuttgart HRA 201929
Geschäftsführer: Dr. Manfred Jagiella

 
Gemäss Datenschutzgrundverordnung sind wir verpflichtet, Sie zu informieren, wenn wir personenbezogene Daten von Ihnen erheben.
Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis (https://www.endress.com/de/cookies-endress+hauser-website) nach.

 

Disclaimer: 

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you receive this in error, please contact the sender and delete the material from any computer. This e-mail does not constitute a contract offer, a contract amendment, or an acceptance of a contract offer unless explicitly and conspicuously designated or stated as such.