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

Mike Hamburg <> Tue, 13 April 2021 13:06 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 053DB3A15BB for <>; Tue, 13 Apr 2021 06:06:05 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.205
X-Spam-Status: No, score=-1.205 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, TRACKER_ID=0.1, 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 sXgM4bp9QTdx for <>; Tue, 13 Apr 2021 06:06:00 -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 5DF9F3A15AC for <>; Tue, 13 Apr 2021 06:06:00 -0700 (PDT)
Received: from [] (unknown []) (Authenticated sender: mike) by (Postfix) with ESMTPSA id E84F1BB80B; Tue, 13 Apr 2021 13:05:57 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=sldo; t=1618319158; bh=0z0PcLkzJh+v3anG25L20KBBeeAsMQ65nOMbdjjhr9A=; h=From:Subject:Date:In-Reply-To:Cc:To:References:From; b=J4yiCI7e5c6OHytlk8c6BfWC8trPQq+htFrc444F6e4J0PFYWXSUdHbbK14hnql1t N/W4xxefC+4GE3Q9Tb8Z27tpwnmiaGE3SV4NHHk/TfRKomOsPwRcP4UfugNtpl8cc+ vrCeIQakC40uS2sO0wpro1ncRcEvYKvIrMswenGM=
From: Mike Hamburg <>
Message-Id: <>
Content-Type: multipart/alternative; boundary="Apple-Mail=_F60C6815-E55A-4782-A328-9FE98E9095BC"
Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.\))
Date: Tue, 13 Apr 2021 10:05:55 -0300
In-Reply-To: <>
Cc: Armando Faz <>, IRTF CFRG <>
To: "Hao, Feng" <>
References: <> <>
X-Mailer: Apple Mail (2.3654.
Archived-At: <>
Subject: Re: [CFRG] Closure (was Re: 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: Tue, 13 Apr 2021 13:06:05 -0000

> On Apr 13, 2021, at 5:50 AM, Hao, Feng <> wrote:
> Therefore, precluding low-order points from map-to-curve by design is still a relevant research question. Can it be possibly done? If so, can it be done efficiently? I am curious to learn.

I suggested a way to do this earlier in the thread, which works for typical Edwards curves like Ed25519 and Ed448: just precompute the least (lexicographically or whatever) point Q such that map_to_curve(anything) + Q doesn’t hit any low-order points, and call that function map_to_large_order_point_on_curve or whatever.  Then clear the cofactor if you want, to get to the large-prime-order subgroup.  The point Q is easy to compute if the small subgroup is small enough (e.g. at most 24 elements), because SWU and Elligator are easy to invert.  For Ristretto and Decaf, I believe the byte serializations of these points are




respectively.  You could alternatively make Q the least possible multiple of G, which would be (if I’m calculating correctly) 16*G or 47*G, respectively.  The least positive and least negative values are the same, because Q is in image of Elligator iff -Q is; this also means that you can’t take Q to be map_to_curve(the least possible input).

If you want a uniform map to the large-prime-order subgroup, you can scalarmul by (1 + (second input % (p-1))).  That’s expensive, but in many cases you’re going to scalarmul the output of map-to-curve anyway, so you can just combine the two scalars.

Obviously this calculation is slightly more annoying than a single map_to_curve, but it’s entirely feasible.

— Mike