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

Armando Faz <> Mon, 12 April 2021 22:51 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 298CD3A1366 for <>; Mon, 12 Apr 2021 15:51:14 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id XvDAZbdUdVwu for <>; Mon, 12 Apr 2021 15:51:09 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::132]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 55AB13A1357 for <>; Mon, 12 Apr 2021 15:51:09 -0700 (PDT)
Received: by with SMTP id r8so23935544lfp.10 for <>; Mon, 12 Apr 2021 15:51:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=google; h=mime-version:from:date:message-id:subject:to:cc :content-transfer-encoding; bh=B2ybL/PBSIQdOc4ZwDNKv9SA+Y4EUr8enFZ0kHYufAc=; b=vB/mIQnjD0aP/GtZVin4d85yizkIVvALzNRAUKwuzJRiZunDpaOvR5XRD95Bn57IbT hT29PyHFSG9I5nxZx/vLkZrGYjfvuiIhov8ip8lZsdsbtXl0fJ9g64ROxcBHWDF30QnN E/X5hMkLIjZYm6Mb+E2H7OnACMh/msv+zab/c=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to:cc :content-transfer-encoding; bh=B2ybL/PBSIQdOc4ZwDNKv9SA+Y4EUr8enFZ0kHYufAc=; b=kcDDZHq8zXoeXHvnakwDV9VuO+I6ObXTEnfI3hFSN6UWf7tMvGKtJL52wbxjf+BiRL u4iz1Fo4e+gps2gUBquvFUWp0W3lO2ctkeH+2O+EqCRtRyiXOkrIPjzRkffIvXEpAS50 2aenZxiq8lJsJrkGtFSZYo82u4xWQ7/PsjwlwlXs6v+C8DZCg1M5C17ur4DWDFcEOEtK bEoUQHjtgTc2vEJ94niYrSshusMRTDRxDLdDkJX+CPGd26MZ+gp+bvvqKvSTTy60KC4p 396JzgRMKcQRpq7Mw3Ka6t1pyN4j8ywdgpXbdSHVMhwVXeCPl9I7rcJ2PuRT4prYkM/A phHQ==
X-Gm-Message-State: AOAM532X4pc5araj4QH0BOYnfkIf2s675aYMRGN2C6GTpDMIG10NNDuo fEDzvuEP/gzlCIoxp5x5AOTPLyW5etkzQwrz6gKPsg==
X-Google-Smtp-Source: ABdhPJx6EK7nZtYsuGlkySA99ZEuv8zAG5CAtDReu6Pn4HJA2rB1NuQS6jm/9RoX5Xp26VQq/EV6Z4pqJU1pQW/iEjs=
X-Received: by 2002:a05:6512:21a5:: with SMTP id c5mr20810239lft.534.1618267865988; Mon, 12 Apr 2021 15:51:05 -0700 (PDT)
MIME-Version: 1.0
From: Armando Faz <>
Date: Mon, 12 Apr 2021 15:50:55 -0700
Message-ID: <>
To: "Hao, Feng" <>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
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: Mon, 12 Apr 2021 22:51:14 -0000

> "Hao, Feng" <>
> I asked for clarification on whether the small subgroup points can be removed from map-to-curve by design. The replies from the hash-to-curve authors indicated no: because 1) too much hassle; 2) not worth it for the negligible probability. I think the rationale is clear.

There were several comments about why clear-cofactor helps to map
low-order points to the identity, and why this might or might not be
an issue in higher protocols.
However, few comments addressed the problem of devising a map-to-curve
algorithm that always returns points of a given order. I consider this
is still an open problem in general, (which is another reason why the
draft takes a simpler  approach, namely clear-cofactor).
Also note that a similar function will be useful for CSIDH, which
needs to sample points in a desired torsion group. If I am not wrong,
CSIDH also uses the clear-cofactor technique to achieve this task.
Happy to hear more comments about this specific problem, (which is a
different  discussion from the implications of not having such a map).

Armando Faz
Cloudflare Inc.