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

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Sat, 10 April 2021 19:20 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 1A6FE3A1855 for <cfrg@ietfa.amsl.com>; Sat, 10 Apr 2021 12:20:16 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.62
X-Spam-Level:
X-Spam-Status: No, score=-1.62 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, URI_DOTEDU=0.28] autolearn=no 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 ZcHgtTXSt1H7 for <cfrg@ietfa.amsl.com>; Sat, 10 Apr 2021 12:20:11 -0700 (PDT)
Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-eopbgr60063.outbound.protection.outlook.com [40.107.6.63]) (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 C02253A1854 for <cfrg@irtf.org>; Sat, 10 Apr 2021 12:20:10 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=LbT27IsTX5aJqV+VRUCaAmzGZ8+mgLTUczgfn/T7U5ghJTRK5A2F0c3mIS9BhEUeww88v0xw61OhHDqdFT5GzlQB+4dglZMvi100YP5Bcmyq5dhMAPPxiWwLlSEW2c7xvUiKwY5B9hKGLoAxsoAQP486ZWOax9OM1HyOzXRASn2e1AE/AN0GKugNBa+3b61BGDS/uC6ufMROrpDsiBclkX8hWYBEYyGKgCj2wQrtKskoVo2DgjjMUCB/nlOls0zrT9MPBQAjGAR17GSoum4uK8G0hFxNR46cNBmlxeg6oU3UsuZnpv+IeNy5oaXDn717pjNonqleSyB/dnnFhrYYpA==
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=d/RDcTvZpwWqT4Q17BxTf5QZL+z1+W3YDK+E/SYqb+c=; b=TtDjCTG5qMHK0XT1QUyAfLcHx+ku685QoIkn/obCjqOnbhOZUpz4EyeBL/P+xrUARsqedwQiVAckWhZdrwEJlZeqSIRYVXqqiDG+6bCcDnaDpXsh5h4oNvfC/VucrKGUL0TZyRAwf6cAq9CjWflJ8Afkl9tRjvCtNNs7yK8y/JBobl4qWUE3RcGMeTv+7Uda7kKBJ9mNoYrc05N48E+Sh5WQ40mZCLKxTvA2nFg1P9m4mJTthTt3ZuhxLhSyACOR0sA1tdb4XHrE8G+OV6k9ykXgmUAmoEeuLrBBLrdb5ofs4r9CbhFVDt+yKq8gE9sH6pmwMtqDIHkIKy2w6bgTLw==
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 VI1SPR01MB0357.eurprd01.prod.exchangelabs.com (2603:10a6:803:8d::12) by VI1PR01MB4526.eurprd01.prod.exchangelabs.com (2603:10a6:803:a4::27) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3999.32; Sat, 10 Apr 2021 19:20:07 +0000
Received: from VI1SPR01MB0357.eurprd01.prod.exchangelabs.com ([fe80::5865:9e5a:626f:8953]) by VI1SPR01MB0357.eurprd01.prod.exchangelabs.com ([fe80::5865:9e5a:626f:8953%4]) with mapi id 15.20.3999.032; Sat, 10 Apr 2021 19:20:07 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: Mike Hamburg <mike@shiftleft.org>
CC: CFRG <cfrg@irtf.org>
Thread-Topic: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Thread-Index: AQHXLUZyltFEkNrErU2XoZAaYPSJsKqsrj2AgAANMx6AACTDAIAAhZzVgABx0ICAAD9g3w==
Date: Sat, 10 Apr 2021 19:20:07 +0000
Message-ID: <VI1SPR01MB0357E0F2D567D0C8B81EE31AD6729@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>
References: <e270e62d-941d-0a87-7dc9-cf80f73b5aeb@jacaranda.org> <d0778523-5f5d-4327-b795-279918c1899c@www.fastmail.com> <CAMr0u6=PBX1W5zQFmpxKQ=ViUXN9QK00BREL4M0=2HOkaXaiZw@mail.gmail.com> <VI1SPR01MB03573585C37B871D200ECC23D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <trinity-f323065e-9f30-48fd-9ead-0865e8f877eb-1618002469856@3c-app-webde-bap03> <VI1SPR01MB035772443E4DA3206E4CD4D3D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <7944D4F1-81F8-44FC-95D1-45D47733B385@shiftleft.org> <VI1SPR01MB03574E592790FD59C1ACEB84D6729@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>, <A1BFD5D1-00E2-4ACB-B55A-D18033229FF6@shiftleft.org>
In-Reply-To: <A1BFD5D1-00E2-4ACB-B55A-D18033229FF6@shiftleft.org>
Accept-Language: en-GB, en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: shiftleft.org; dkim=none (message not signed) header.d=none;shiftleft.org; 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: baa695c9-2986-4e01-278a-08d8fc55a6fc
x-ms-traffictypediagnostic: VI1PR01MB4526:
x-microsoft-antispam-prvs: <VI1PR01MB452609B84B40E1C530F7ECB4D6729@VI1PR01MB4526.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: pzWaIt7sX9SNxeUtEm84szJ51qezJy0Yi+4cArStPM1n5xXaQLpZT7H2Ox0yufkxySfRuUnne5CH0sdYD+TazUrHdwgr82hteoE7AcF38N3/mEkEbI3re/MPmMtBE3cJq1L8ga8DSemOMLob1yxjBJzwz0XwcbY3UF1Yq7xM29XdeTpzIPXcKkWwTVQtldhazzj3xCFpM+OlWm1XGbGau314PVjsHjeNuqc9apty7mpl0OISFcF+l0lP7raX1XEhwjb/s9bsoG1BWO2WFpubsn//mqTV1aO2pX2aJiXLa9Wc5Ju0YpN0hPZ1CrzRhB0mtXKRlBQp1e3ck9CSWkTCXPXnFXspZgVqF227M3lhCcRiuujIsfIRxPvJ3FVpJWT9UB1WZ8nHThBaDsPkmYDiylDaAb6ZSO1bHDNmgaBRnP/kutmk6/Kgu5vjJjYRaKH2cUWDvswIaCShZC9FesLFbgBA5/IZfBxz9f3sXVkZxKPn0+kJ8kZQZWx9LnodS8VYPNSJ6W5/yzChUYamjoA0ZtyHPYVPo1+92MbgD9LULXFLmfCaUhW4i4gpuX6R9WXZU/A1eeVAtrJGazwEF9uvjYRILgl+q9Z31/4AMmkIY1FdsqlI/UirHh9+AgKZy8k9bgxF2sGuQgTG/7SjjCcIpNCmygyyvALQIbK6c2II2H9sWEieeCoHeGipsGk4LGv1
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:VI1SPR01MB0357.eurprd01.prod.exchangelabs.com; PTR:; CAT:NONE; SFS:(4636009)(366004)(39850400004)(396003)(136003)(376002)(346002)(26005)(33656002)(55016002)(966005)(4326008)(66446008)(38100700002)(83380400001)(166002)(478600001)(6916009)(8676002)(66556008)(64756008)(52536014)(66476007)(71200400001)(86362001)(786003)(5660300002)(316002)(8936002)(9686003)(2906002)(7696005)(66946007)(6506007)(91956017)(76116006)(186003); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: HTg/84VgBsSUHv7ICNcWnX070R2BpcjU/erQ1+tEASnCWxnLFOr0DRSBFyqrSiXC6Tde7RNLL5gDrSbYRnprZ4Onn6jl23SHSFEL6sZGtkJDBLTNU42f3ez6pWfIGffh8qz9C/XX+yxXliTSq5m966SzubZQPb+o2zeIpcThjD3fdiu6DTeqwvcyfqtatkMPmaWQwnO4GTQIHFl7Y5ocHwHMPaJ1zxmHIyKGLacHm7Z3iSJvbiurWBFHFln9usPtiI/D5WrnIWj/NEFtaTCUe4fU0bUwtivbqlCBY6F0c+ZIj5jrUy0ft91HsRsFKDoKtt5+aRmmMklVhdzLrtP/jLBEEOxd6zeFHn8h0Yl788Bdw/u0y5ic0cZeAFRr/vydD0U2yV1iwbPhVuxlBDU/zVRkLQ9el6nR2zISgb5V9PvSM2nomhnTB4UFGZX1X2IaeRlXgWZjgb1yV7Ne7a0DZ5nPI7P80X8kEsKjkdqVKibGQR14qupwv3LQgwp/L6akj00rpVL/wMoI5lzanV4IYCkb4sENm17YyTrfBHqdwMply+AtFkQ+IwMHESAqiDl6dq3UVwq+5magIXLgJxKgs2vLVTODv9/zLFQ94SZsi+IcMS37bbQrGIl5t5wDdM1wwQWj3m3vwZt+SW9vzho6K9qqCoZZJByL6f16gs44HG9XhKoAjVN4ozdPkXxd56PGoQ36TeLysYEZRsCfV3G5kI+KIs++Q6s6iG0wkW9EDyMTL7OVmen072hTicIYJ+NlLgvCzr0sP0oJiF+e05AWGSzgwBdru0NNMRsOJIOAl2SY7Bjw2b3JwMTVrsQm1m17bR95Ha4resVJtR68pTEZ3BhuHgRQJX5VT9poKwR355ZLnpDYft23oLga40AoU5o/xydlb3uNjwmp2WLxlws2XrZcUEnV8W4xkG1JH71FnMQs79YP3ft146QbVTkgari20eLFdadoicT9SUdl9DtBMtVZ3qszW9VTG0P8CuDIfxAdgGqH460GvXEhsaL3rq6niV05GLDA9VEJoDoUwGqeEcbDqSqQEDdfZmQ71G7o2PnRrSo+7jtOtEkQ5+OEKTan+8KrduJu2EdSR6JV2xtnB1K1/LYYg4OM9K3lMWkXa7p07KrQnHObfuxiEnSHjTUc3DKxCR0flbmlS6IV7TBhJkYUStJGEAooiT60onTkPtPfSHXqINgFO49kpOWURyPUekOnkOKIcFdtN8/FLKbSxHVmveFFcb3Ezp3BpucI4kUgGUi4S0xIsYnNKbPqmBt7iYLkiFWfGugNpnhV33KbVVkcDj9FdjdNHXo1qCixzf3TLPXvUU6dLlvuE8oimgYVfAT4gPxq5MjZwli9o/FpOA==
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_VI1SPR01MB0357E0F2D567D0C8B81EE31AD6729VI1SPR01MB0357eu_"
MIME-Version: 1.0
X-OriginatorOrg: warwick.ac.uk
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: VI1SPR01MB0357.eurprd01.prod.exchangelabs.com
X-MS-Exchange-CrossTenant-Network-Message-Id: baa695c9-2986-4e01-278a-08d8fc55a6fc
X-MS-Exchange-CrossTenant-originalarrivaltime: 10 Apr 2021 19:20:07.6038 (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: HS6M746oMl+/HZgCc7RRbHfb0VCnqXBEtXCdDtaFBnueGmIGSZjZOMSxpWg/VjR6+R4PTFbXhmgOsKjYsfxua2M2zDWed6HZkS7B/0+gAKY=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR01MB4526
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/9y4OfKFOLQZ50Em3p13jxdcO0bQ>
Subject: Re: [CFRG] 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: Sat, 10 Apr 2021 19:20:16 -0000

  *   hash_to_curve is (epsilon-close to) uniformly distributed within its range, which is the prime-order group of points on the curve, which is also the range specified by these schemes in the literature.
Please kindly note that I explicitly refer to map_to_curve, which can return low-order points. This function is followed by clearing-the-co-factor step, but as explained this step does no help to resolve the real issue.


  *   No, not PAK.  PAK uses the hash output as an additive blinding factor, so it ideally wants the value to be uniform in the group, non uniform among non-identity elements.  Of course, removing the identity won’t harm it, since again, that’s a negligible change.
Please See Figure 1 on p. 11 in [1]. PAK uses the result from H1 as a base generator before being raised to the power of r. The follows the same idea as SPEKE.


  *   No, it’s pretty much the exact opposite of that.

  *   DDH is usually written as distinguishing (G, aG, bG, abG) from (G, aG, bG, cG) where g is a generator and (a,b,c) are uniformly random mod the group order.  See eg http://theory.stanford.edu/~dabo/papers/DDH.pdf (which uses exponential notation but is otherwise the same), though variants (such as c != ab) are sometimes used instead.  Here aG, bG and cG can be the identity.  In this formulation, G cannot be the identity: it’s defined as a generator.  But if it were the identity then the two distributions would be identical — they would each be 4 copies of the identity — so DDH would still hold.
Sorry, that can’t be right. if you want uniform distribution of values in Gq, the items in DDH can’t be identity elements. They should have the prime order q. Please see the explicit definition of Decision Diffie-Hellman (Problem 6.4 in Section 6.7.3) In Stinson’s book [2]. The definition in Stinson’s book makes perfect sense to me, and matches what I observe by experiments (just try toy examples yourself, and see actual distributions of values).

  *   If you’re using my library, libdecaf, then you can use decaf_point_eq and decaf_point_cond_sel to remove the identity in constant time.  Similar functions are likely available in other libraries.
That’s interesting. Why not integrate it into the hash-to-curve draft?

  *   No, hash_to_curve on curves with cofactor = 1 can also return the identity point, because it adds two map_to_curve results together.  That case is arguably harder, because there are very simple complete addition laws for Edwards curves with cofactor 4, but the complete addition laws for Short Weierstrass curves with cofactor 1 are more complex.
Yes, you’re right. I was thinking of the Icart’s method and SWU. But if you add two results, then it’s possible to give an identity. My point is that it’s possible to remove the identity and low-order points by design (easier if you work with co-factor =1 and a bit harder for co-factor > 1).

[1] https://eprint.iacr.org/2000/044.pdf
[2] Doug Stinson, “Cryptography: theory and practice: third edition”, 2006.