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

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Tue, 13 April 2021 08:50 UTC

Return-Path: <Feng.Hao@warwick.ac.uk>
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 4E5A13A0C4C for <cfrg@ietfa.amsl.com>; Tue, 13 Apr 2021 01:50:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_BLOCKED=0.001, RCVD_IN_MSPIKE_H2=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham 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 wDRCoZOuZEQh for <cfrg@ietfa.amsl.com>; Tue, 13 Apr 2021 01:50:25 -0700 (PDT)
Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-eopbgr60046.outbound.protection.outlook.com [40.107.6.46]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 32DE03A0C64 for <cfrg@irtf.org>; Tue, 13 Apr 2021 01:50:25 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=eDPqSeaK8TNY8+pdpjsTwxukNBKgUdoYWWi8slPp/zAeIgOY0EyrKTBG5XeWfdM0bAZ13fnT16oJMLUATG4+3QiVfkLesPOF2AVPqGhqExGm36aFwxFoXxuKv/rF+P/qvd1UXxx2wfhM/5ApEyRxE7QIl7bf+H6moXgYW5IO1zgqZrbBMneJs+7UI9criq5W58VTDY+ssQIhT8ehO19RPYRdXkh8qRP2EgzaDa35jCByYtEvogD6PUwuvZPrqj+c849tTVR34AhBnRQ+387rIwbnlRJWZ71aiAlFCWN+MK1NRra1SY4NHILB39ZmUHn8/oCw/4hZ55G7tWcgSK0Akw==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=n7xvKGWDWk9UdRCDoRSrIMmDpSHT4xqzyzbne0yIoR8=; b=VddY1pxjPiz3OIReN6YDTS7cznZNn1VdH9kn/GgRVNn9+x7LE5qHCm6R0r/DSp2/5NSIkIzJ6mt/pnXLx1wIOrgwft+eNEZaGp8JNX29DzlzVp9sq0OaNb9rk/va0xwnXkbs6cAHbnR3Dxvt4h5ig7jkVo444BZxrbIpnspK2YzXD5z/paDMaK/HS+/mojRY6mNAWr6a066D0zN+hiTEFm/aLkpjbYtLO5f1UcpnWMnRdbVgT+HHLPb2QTd46kp46Rw7Kv++QSHHmk4U3FWQPgg4NN9lotywixuoxA61fqvGpz9f5J8raMrcvciezfwgUNIwIE3evAdxOA/w9OuNGQ==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=warwick.ac.uk; dmarc=pass action=none header.from=warwick.ac.uk; dkim=pass header.d=warwick.ac.uk; arc=none
Received: from AM6PR01MB4278.eurprd01.prod.exchangelabs.com (2603:10a6:20b:23::18) by AM6PR0102MB3494.eurprd01.prod.exchangelabs.com (2603:10a6:209:26::26) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4020.21; Tue, 13 Apr 2021 08:50:18 +0000
Received: from AM6PR01MB4278.eurprd01.prod.exchangelabs.com ([fe80::44c0:8247:69aa:bcd3]) by AM6PR01MB4278.eurprd01.prod.exchangelabs.com ([fe80::44c0:8247:69aa:bcd3%5]) with mapi id 15.20.4020.018; Tue, 13 Apr 2021 08:50:18 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: Armando Faz <armfazh@cloudflare.com>
CC: IRTF CFRG <cfrg@irtf.org>
Thread-Topic: [CFRG] Closure (was Re: Small subgroup question for draft-irtf-cfrg-hash-to-curve)
Thread-Index: AQHXL+5TtjPV+Ah/kU+0aoIFOve35KqyDySH
Date: Tue, 13 Apr 2021 08:50:18 +0000
Message-ID: <AM6PR01MB42789718B0838E9C305562A5D64F9@AM6PR01MB4278.eurprd01.prod.exchangelabs.com>
References: <CABZxKYnTxM_es9tkDHd+cN4X0dT3WeOuaR2zki7LqFWzp17dgA@mail.gmail.com>
In-Reply-To: <CABZxKYnTxM_es9tkDHd+cN4X0dT3WeOuaR2zki7LqFWzp17dgA@mail.gmail.com>
Accept-Language: en-GB, en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: cloudflare.com; dkim=none (message not signed) header.d=none;cloudflare.com; dmarc=none action=none header.from=warwick.ac.uk;
x-originating-ip: [86.1.162.194]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 4ff52f33-99bb-41c9-ddf5-08d8fe592a24
x-ms-traffictypediagnostic: AM6PR0102MB3494:
x-microsoft-antispam-prvs: <AM6PR0102MB349443534FA04182043D1172D64F9@AM6PR0102MB3494.eurprd01.prod.exchangelabs.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: cc39z0mV3/TbqLN4igrM2Ul/PGueVZ9pfEH+C4zkwjxf8gUCO7Tg6GpAElDsyI8/dTgsM3Z1WUGcXp58OKvxbThsdTxGRZBdOre6keSzCAeyAmFW686bvFLb8sH7qWj7OtblrFim6jIadHX2Hj6gyJk92UyLJTN1S5gfVetVXkI3Zi0PYY2WHOwJTbjKonwUPEzrslGcaiBvafHandxqgzqcjERxsEJTwDr/+dQ1fcc21ZIQodPu4VlEm3ATFPDDE5ipEQXmrDyY7fZ2Ywloy1pfe308rkH0G8m/b2u5P5HihoG1vRXQs9ykBYbXBpab27CmjdfYXct39hNYP+USTagBHpDu7RvX4Q5uwrqxrjfBVTpksawsLsDBdqLfNj0732at8EgQxxkgM4GI3QYbaP9veOvmq7bAhbY9qQr6A57QyhLPiiW4P6FBWwul5s6sZLPXnRaJwUqLj52+Q3+FJ7qqnvCsp7CFdkBr9Vv7438d6+baNuE/1xx0u92KdwC5fgyUJ2yIKg68ilAINyiQVnGx1QTh0azZ9WjPQrHUrng57dLtUWjHTk1OnV2ubNCzfzcOXXhJbqfafi5fQOgVmyHKGC4/1IHqOeKSD9YUl0Q=
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:AM6PR01MB4278.eurprd01.prod.exchangelabs.com; PTR:; CAT:NONE; SFS:(4636009)(396003)(376002)(136003)(346002)(39860400002)(366004)(52536014)(4326008)(122000001)(9686003)(5660300002)(2906002)(66446008)(66556008)(66476007)(64756008)(786003)(66946007)(91956017)(55016002)(316002)(33656002)(76116006)(38100700002)(478600001)(6916009)(6506007)(86362001)(26005)(71200400001)(83380400001)(186003)(7696005)(9326002)(8676002)(53546011)(8936002); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: zKjhdtIcGVMILLRepiWBNlod/mRyGFq6te6ddwzmxw+8Gns0XfozM5SYZ33Un56g8fgcmYeyGjjTYj81IiZKzR63dePvWnaf/V10di5nNiVxcnanLVBHvKqWCKe+RKnNp0lRxTL5n63JM6DG/ZxcDgxhyjzsPEHPtBBv3uXFKPh9JAnb+dAP1Fo0UqwqYZXrhix61BC1BIFm0J76z5lz6Vl42tcms/yQA3JfoV65V3VanmjQlQ0apviPjeWfteVQY+9MVprkx0MWf1AV0O3IRhshJ+M8CvbaFV8LgnXiOBDuYT0pz+e2VCMouYJ13i5ce3otKV0iz6hLEXx5VMSVritWXlQITa//xeitEM/R3c7K4gMxXkooR649xzT7ZNzFtUAiRUf8V7+wuhKj8U/nBpY9eA+ht7+IQPyIt+YPc3gaoEDrS51pvils/ENhi9fVuNpsODabyJMkUUBTFZP3MJcCZ9Xb00r50yy3TvJNYXHvWy0TN4ssClr1y4EsiIQnkJaSqL4U4VQlZzoIBKlwvJvbScUQOT6zLPYVB2E+2Mzb7FAeAUbA4WVBraRXYoppAYjA8PMentgPS53yNNYRLnG3BuGWczmuHWdoJULyCsBx02N0/r3KWbAqtyg0WMRgU+lDwu+rUHAuaaYSYxwfPl7LKeqS4vF2estQ9b+dy2NAIGgsIdg3oL5OC1sA9kTXVfEOFPZTw3gG2UewEPhwlAVotH3v0z7Nz1OwA05neQ7NrvONkQkkcKWasfYL10+Xv4SNw0+HEEuZCFwFzOvlC7zThm0J/mih74HnI0APBckUGzq+DZfgPKtXnX0g0TMd8JKwdtgVjoyoLo9VXRL9o+qvUryIXx9qGJWdSXBd3d8Zb+NB0RQWbagbbs09dCLkmaYEPD5HcT9J6PUfFyuwiAU1wBHSiAkLLRYHf1wV/By8XuN3KxeJwl3nFlrYANWflwIU6MdteI5a/VaI5CxtLAC/bFfWY9RMroY5K5/NOINbYpxAHkNYmzvD3RCXg1JGMwI5b71BphLUUS/fGi8HfxaGg3rc+UTW2SnfIVU170X+q0NkLLmg6PkgoQ1kCfDpIfWdoHXZwtjXtPXr+kd6ntA/BEIDXmWKkSfcYr05LUEZrqJ94vik3yl9z/6nI5dxZ8Bx3NF6okYT3JvydvHC40yVWDPq4Fh/lryoGsPUjFMdhp7lEg0GEEKKdG8n4VhPdQnDt30jaxuGIcJdjwvd5BB3AsjVCjp1LOUjBeb6HphflKGecoUG2jIGzyZuFGCksp/ou8VWAiZRHFnXFB+Hds00jNeZbSJ2dPr1oDoVK/Le8JJ3O+xlK01+BoDp2/lC4tlYFjnd4MwGB5EXbdYwdw==
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_AM6PR01MB42789718B0838E9C305562A5D64F9AM6PR01MB4278eurp_"
MIME-Version: 1.0
X-OriginatorOrg: warwick.ac.uk
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: AM6PR01MB4278.eurprd01.prod.exchangelabs.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 4ff52f33-99bb-41c9-ddf5-08d8fe592a24
X-MS-Exchange-CrossTenant-originalarrivaltime: 13 Apr 2021 08:50:18.4169 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 09bacfbd-47ef-4465-9265-3546f2eaf6bc
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: a+8s6Y5/qdkBqXX3WaqD3B5mwWB/xvmRX6jO68Sk4E2/ky+2hOhteKpwydtoU+PVwWmsPgceaGf0Y3rd3ELIIwjy3zLY2UPsPUVLPWCO+QI=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR0102MB3494
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ThYeYwgOunjcVgiGySNZ3XSSoAI>
Subject: Re: [CFRG] Closure (was Re: Small subgroup question for draft-irtf-cfrg-hash-to-curve)
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: Tue, 13 Apr 2021 08:50:30 -0000

Hi Armando,

Thanks for the good questions.

I think for all practical purposes, clear-cofactor is good enough, and should be safe to use.

There is a theoretical probability of failure, but that’s really negligible. If you treat the mapping function as a random oracle, then the probability is 1/q where q is the size for the prime order group. Of course, a random oracle is just a theoretical abstraction. In the real construction, depending on what encoding/mapping methods are used, the function only covers a fraction of points on the curve. Hence, you may end up with an upper bound probability h/q where h is the size of the small subgroup. Still even with h considered in the worst case and for the curve settings considered in the draft, the probability remains really negligible and there is nothing to worry about in practice.

On the other hand, is it still worthwhile to consider a map-to-curve algorithm that always returns points of a given prime order?

I think so, for the following two reasons.

>From a theoretical point, that will match exactly the assumption made in some PAKE use cases. What is precisely needed from hash-to-curve is a generator point, which by definition is a point that has a given prime order (i.e., a non-identity point in a prime-order subgroup).

>From the user’s perspective, there is also a perceived benefit to reduce a negligible probability to zero if you can. Given two systems which are basically the same except that A has a theoretical failure probability 1/2^{256}, while B has 0 under the same condition. Which system to choose? A rational mind will say it doesn’t really matter. It’s perfectly fine to use System A (indeed that’s very correct). However, if you ask ordinary users, given that there is also a choice of B, I bet many of them will opt for B without the slightest hesitation.

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.

Cheers,
Feng

From: Armando Faz <armfazh@cloudflare.com>
Date: Monday, 12 April 2021 at 23:51
To: Hao, Feng <Feng.Hao@warwick.ac.uk>
Cc: IRTF CFRG <cfrg@irtf.org>
Subject: Re: [CFRG] Closure (was Re: Small subgroup question for draft-irtf-cfrg-hash-to-curve)
> "Hao, Feng" <Feng.Hao@warwick.ac.uk>
> 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.