Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

Loup Vaillant-David <> Sat, 10 April 2021 22:04 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 9D0603A1DC5 for <>; Sat, 10 Apr 2021 15:04:18 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id PcinXty_6TXT for <>; Sat, 10 Apr 2021 15:04:13 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 744EC3A1DC0 for <>; Sat, 10 Apr 2021 15:04:12 -0700 (PDT)
Received: from grey-fade (unknown []) (Authenticated sender: by (Postfix) with ESMTPSA id 0EFB6200002; Sat, 10 Apr 2021 22:04:07 +0000 (UTC)
Message-ID: <>
From: Loup Vaillant-David <>
To: "Hao, Feng" <>, Hugo Krawczyk <>
Cc: CFRG <>
Date: Sun, 11 Apr 2021 00:04:07 +0200
In-Reply-To: <>
References: <> <> <> <> <trinity-f323065e-9f30-48fd-9ead-0865e8f877eb-1618002469856@3c-app-webde-bap03> <> <> <> <20210410151254.7ze5pt4lpvblhk3f@muon> , <> <>
Content-Type: text/plain; charset="UTF-8"
X-Mailer: Evolution 3.28.5-0ubuntu0.18.04.2
Mime-Version: 1.0
Content-Transfer-Encoding: 8bit
Archived-At: <>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sat, 10 Apr 2021 22:04:19 -0000

> Therefore, the best one can do is to hope map-to-curve never falls
> into a small subgroup. But in that case, wouldn’t it better to
> preclude small subgroup points from map-to-curve by design?

Only if precluding those points is less risky than just hoping. And by
a very wide margin, it's not. We have to choose between two risks:

1. The map-to-curve generates the identity point. The probability of
   that occurring is less than 2^-250 at each trial. Realistically, the
   probability that it occurs even *once* in the foreseeable future is
   well below 2^-128. Those numbers aren't just very low, they are
   *impossibly* low. I would stake my life and that of my entire family
   for a penny with those odds, and still sleep soundly at night.

2. The preclusion introduces a critical bug. The probability of *that*
   occurring is far from negligible. We can lower it, but we're only
   human. We make mistakes. We write bugs. Heck, I've even recently
   been made aware of a bug in a formally verified system (not telling
   more for obvious reasons).

Ironically, I would perhaps *not* stake lives on the correctness of the
present email, despite what I said above. I'm infinitely more likely to
have made a mistake here than I am to flip 128 coins and having them
all come up heads.

The correct way to minimise risks in this case is to simplify specs and
code as much as we can. Adding a check, especially one that you cannot
test in a black box context, is infinitely riskier than gambling on 2^-
128 probability being close enough to "impossible".

Thus, precluding small subgroup points by design is a bad idea. Don't.