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) //
- [Cfrg] patent situation regarding hash2curve as u… Björn Haase
- Re: [Cfrg] patent situation regarding hash2curve … Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] patent situation regarding hash2curve … Björn Haase
- Re: [Cfrg] patent situation regarding hash2curve … Riad S. Wahby
- Re: [Cfrg] patent situation regarding hash2curve … Björn Haase
- Re: [Cfrg] patent situation regarding hash2curve … Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] patent situation regarding hash2curve … Riad S. Wahby
- Re: [Cfrg] patent situation regarding hash2curve … Björn Haase
- Re: [Cfrg] patent situation regarding hash2curve … Riad S. Wahby
- Re: [Cfrg] patent situation regarding hash2curve … Björn Haase