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

"Riad S. Wahby" <rsw@jfet.org> Sun, 20 October 2019 21:46 UTC

Return-Path: <rswatjfet.org@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 5D3E212006A for <cfrg@ietfa.amsl.com>; Sun, 20 Oct 2019 14:46:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.055
X-Spam-Level: *
X-Spam-Status: No, score=1.055 tagged_above=-999 required=5 tests=[BAYES_50=0.8, FREEMAIL_FORGED_FROMDOMAIN=0.001, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, LOTS_OF_MONEY=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
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 Rt46V7mjI_8P for <cfrg@ietfa.amsl.com>; Sun, 20 Oct 2019 14:46:06 -0700 (PDT)
Received: from mail-pg1-f182.google.com (mail-pg1-f182.google.com [209.85.215.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EF9C612001E for <cfrg@irtf.org>; Sun, 20 Oct 2019 14:46:05 -0700 (PDT)
Received: by mail-pg1-f182.google.com with SMTP id p12so6462111pgn.6 for <cfrg@irtf.org>; Sun, 20 Oct 2019 14:46:05 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:content-transfer-encoding :in-reply-to; bh=vXmgEcaqOXOx6qars9OVM3R1HA19FdF2WaODwBA7q4c=; b=fsWlxsLi3etAXTLLSyYytR9YEwUZvUkSmek6SscPtDVcSTzOoT5hSmAu3HPmUu3aJe PTDuDj7gch8fxOFX6DSfAumerehJSSqBsCNxmVgOClkAXlPeX9KRN35hz/zCC/h+TgcK umcA0V6osO4CqLZGR7OXqgdX2rdN7E8rkpHZfKS+Wq9P0+PgKWuvlVOE986rS7Ev0rso jmmkfsjnGPum49KUYLRWGPfw4XD5RcZg1bYZDJCb/qlCDJcSGFqe6wnwAJ4WEuhYR+ZH /ur+HLWfhoTwjwlfuIO0percOJT0UVvV1QgLe/E3pbblskRI3rDbGMOpcpItZ9gM9L36 sGnw==
X-Gm-Message-State: APjAAAXvuPkZO4Y0ZHddGMF8Zr8dH63O6QVMkYy+nAe/9WgVKvdou4De W8pzUZSjbImcboWzG5Zo2wNfLknA
X-Google-Smtp-Source: APXvYqwQGZshcU94ZBKMAKtf38C+FMxJL+p+1AcTtWHnZ6A3OBhevkp+AzrFl3k13Ph4mB2NZVs8Hg==
X-Received: by 2002:a62:1b43:: with SMTP id b64mr18463886pfb.56.1571607965363; Sun, 20 Oct 2019 14:46:05 -0700 (PDT)
Received: from localhost (positron.stanford.edu. [171.67.76.114]) by smtp.gmail.com with ESMTPSA id b3sm11420423pjp.13.2019.10.20.14.46.03 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sun, 20 Oct 2019 14:46:04 -0700 (PDT)
Date: Sun, 20 Oct 2019 14:46:03 -0700
From: "Riad S. Wahby" <rsw@jfet.org>
To: =?iso-8859-1?Q?Bj=F6rn?= Haase <bjoern.haase@endress.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Message-ID: <20191020214602.veecj2ft2v6czjye@positron.jfet.org>
References: <5e1610c6-2038-31ce-6bb8-a6e18f40434d@web.de> <ac0ed5bf-cc4b-14e6-59c6-f24c7cb43f1a@web.de> <20191016202223.lbuavuery4yj6qib@positron.jfet.org> <trinity-77782fb3-2939-452c-85d8-95592c7829b8-1571301291317@3c-app-webde-bs25> <VI1PR0501MB22556D3FA849989AAFFFD1FA836D0@VI1PR0501MB2255.eurprd05.prod.outlook.com> <VI1PR0501MB22555DA1CD400E64259EA39D836D0@VI1PR0501MB2255.eurprd05.prod.outlook.com> <VI1PR0501MB2255C90CDB1AA88516A1CFDC836D0@VI1PR0501MB2255.eurprd05.prod.outlook.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <VI1PR0501MB2255C90CDB1AA88516A1CFDC836D0@VI1PR0501MB2255.eurprd05.prod.outlook.com>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/jV4Wr4fbMKkd4vzsbEhKbous16Y>
Subject: Re: [Cfrg] patent situation regarding hash2curve as used in some PAKE nominations
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sun, 20 Oct 2019 21:46:07 -0000

Hi folks,

In thinking about this a bit more, I believe there is a relatively
easy way to totally avoid Claim 13 of US Patent 8718276, which may
otherwise present IPR issues for use of the Simplified SWU map.

Let y^2 = f(x) = x^3 + A * x + B be the target curve over field F.

The text of the claim is reproduced below. The important part here
is that the method requires choosing polynomials Xi(t), 0 < i < 4,
for which the following hold:

1. f(X1(t)) * f(X2(t)) * f(X3(t)) is square in F for all t in F.

2. f(X3(t)) is a nonsquare in F for all t in F.

We can instead choose polynomials Xi(t), 0 < i < 3, and Z in F, for
which the following hold:

1. Z is non-square in F.

2. f(X1(t)) * f(X2(t)) * Z is square in F for all t in F.

3. x^3 + A * x + B - Z is an irreducible polynomial in F.

This still gives a usable map. Crucially, though, there is no X3(t)
such that f(X3(t)) = Z for all (any!) t in F. This is because when
    x^3 + A * x + B - Z
is an irreducible polynomial in F, this implies that it has no roots
in F and thus that x^3 + A * x + B != Z for all x in F---so Z cannot
be written as f(X3(t)) for any polynomial X3(t), and Claim 13 is not
applicable (to my non-lawyerly eyes, anyhow).

By combining the above modified criteria with the requirement that
Z is not -1, we have a method that is covered by neither US8718276
nor US8712038, regardless of how the map is evaluated (again, from
my perspective as a non-lawyer).

One might also worry that no suitable Z exists for curves of interest.
So far I've checked the NIST curves, BLS12-381, and secp256k1 and have
found suitable Z's without trouble (so at least heuristically it seems
like we shouldn't have that problem). I have not thought about whether
there is an easy proof that Z likely exists for any curve, but that is
not entirely implausible.

Thoughts on the above would be very much appreciated!

-=rsw

Björn Haase <bjoern.haase@endress.com> wrote:
> 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) //