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

Mike Hamburg <> Sun, 11 April 2021 14:19 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 84AEE3A0C03 for <>; Sun, 11 Apr 2021 07:19:36 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.305
X-Spam-Status: No, score=-1.305 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RDNS_NONE=0.793, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id YcYJ5cAAVBE2 for <>; Sun, 11 Apr 2021 07:19:31 -0700 (PDT)
Received: from (unknown []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id B25B13A0C04 for <>; Sun, 11 Apr 2021 07:19:31 -0700 (PDT)
Received: from [] (unknown []) (Authenticated sender: mike) by (Postfix) with ESMTPSA id 0B325BB80C; Sun, 11 Apr 2021 14:19:27 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=sldo; t=1618150769; bh=ZZ9hDZqhNt/wj9l1hgQsNA5JHMyRs0kW4fodqntXbc0=; h=From:Subject:Date:In-Reply-To:Cc:To:References:From; b=Q4zVndrGFGkRZ2W9bC4C+qoWIQkmd8XjkTM5zfGLsVpGUkIkc5gzGCwmtUbPgE6ZB oOBlgdjsvadJUqdZxsP1oyHMPFc+Ne9Ap3SuKRHxTi5AAxtQChZvd7Wggi1sFmxhpP t0TMYsY6RaXnV9nECqffbzZmBSAeenbLiA8qe75U=
From: Mike Hamburg <>
Message-Id: <>
Content-Type: multipart/alternative; boundary="Apple-Mail=_CF2516C0-6C41-4639-B341-2938DEB7DA79"
Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.\))
Date: Sun, 11 Apr 2021 11:19:25 -0300
In-Reply-To: <>
Cc: Hugo Krawczyk <>, CFRG <>
To: "Hao, Feng" <>
References: <> <> <> <> <trinity-f323065e-9f30-48fd-9ead-0865e8f877eb-1618002469856@3c-app-webde-bap03> <> <> <> <20210410151254.7ze5pt4lpvblhk3f@muon> <> <> <> <>
X-Mailer: Apple Mail (2.3654.
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: Sun, 11 Apr 2021 14:19:37 -0000

> On Apr 11, 2021, at 7:36 AM, Hao, Feng <> wrote:
> What this though experiment shows is an idiosyncrasy in the system. It seems the small subgroup confinement issue hasn’t been considered in CPace and OPAQUE. This is understandable given that both protocols have been assuming hash-to-curve as an idealized function. Fortunately, for the curve settings considered in the hash-to-curve draft, the size of the small subgroups is so small that the practical effect is negligible. But the effect can be dramatically different when CPace and OPAQUE are implemented in a different group where the size of the small subgroup is not small, e.g., DSA, Schnoor.

Hello Feng,

CPace and OPAQUE require prime-order groups.  Prime-order groups do not have small subgroups, other than {Id}.  CPace and OPAQUE make security assumptions on their groups, but those assumptions plausibly hold for DSA-style groups.

If you start with a uniformly random distribution on an abelian group G of order pq (where p,q are coprime) and then multiply by an appropriate factor (typically q) to get down to a subgroup H of order p, then you will have a uniformly random distribution on H.  The probability of hitting the identity in H is then 1/p, which must be negligible or else rho attacks break your scheme.  It doesn’t matter in the slightest whether q is large or small.

Or, to pull the analysis back to the full group G: the probability of landing in the small subgroup doesn’t depend on its absolute size q.  It depends on its size relative to G, which is q/(pq) = 1/p, i.e. it depends only on the size of the large group.

In sum, no, this isn’t a bigger effect for larger groups.  The only thing it really changes is the difficulty of tweaking the map before the homomorphism in order to guarantee that the identity can’t show up.  If the group is prime-order in the first place, your tweak only has to avoid one element.  But of course, if you tweak after the homomorphism, then you are only avoiding one element regardless.

— Mike