Re: [Cfrg] hash-to-curve updates and suite reduction

Christopher Wood <caw@heapingbits.net> Thu, 07 May 2020 15:36 UTC

Return-Path: <caw@heapingbits.net>
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 69B4C3A0A09 for <cfrg@ietfa.amsl.com>; Thu, 7 May 2020 08:36:39 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 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, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=heapingbits.net header.b=LWux0yjy; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=tamdnyzP
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 K9XPYgcfH1d5 for <cfrg@ietfa.amsl.com>; Thu, 7 May 2020 08:36:37 -0700 (PDT)
Received: from wout5-smtp.messagingengine.com (wout5-smtp.messagingengine.com [64.147.123.21]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 332F63A0A07 for <cfrg@irtf.org>; Thu, 7 May 2020 08:36:37 -0700 (PDT)
Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailout.west.internal (Postfix) with ESMTP id 24BB44A7; Thu, 7 May 2020 11:36:36 -0400 (EDT)
Received: from imap4 ([10.202.2.54]) by compute1.internal (MEProxy); Thu, 07 May 2020 11:36:36 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=heapingbits.net; h=mime-version:message-id:in-reply-to:references:date:from:to :cc:subject:content-type:content-transfer-encoding; s=fm1; bh=3a e5a07VP7aDP+I+aPWId/2OMveb8dB4izJHdUZe52Y=; b=LWux0yjy9OK19qfm/7 /6q++Tuu8b/ZOjPksqHfhf7WH6q9WCLCK0Iyx0cMypCZt8C0G2tYe7jomW1hCluf Yg0vPdVdexBWjkfvNw81q81Jmeq02oSe++BrV5JPmZCgkF0WW6yhRCXJy9xKWJnL zn4AHuX0ZN6zTz/GawBXYlCtE4uEztZE8qTj7KQp1UvmBJqOSafcP+J6W1+s6RuZ O3PzPGzeRIbE4dlJ2x4mlicRF+0zKu39vy/lPgYr+V86VujodnPBPHUbjXSnmS7y g69K4BkKkFwpweNR45w9qkZSR9aQA/4ckjz6zrjlYY99qwNcpnCfz+x68IgLWQAC KMHQ==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm2; bh=3ae5a07VP7aDP+I+aPWId/2OMveb8dB4izJHdUZe5 2Y=; b=tamdnyzPD5ABtsyMED/sBE2tO/wa8gVcTjdmsk0j3loVyFXHNFRl0kKwW Vi/t46PQD1lrC/Xr66qNZ1BADBIrxfBAnoXwqqTa5QaWnXrqbuC/qqf3DpeGEvZ2 k+N4ELXqes5T/s+24wUhbtGT4q1Iq6RTZHKXxKqxm9/8NkSmIIpR/0or4XMNM7IS YxWkBsokm+JeTleMLBd9oTIjZ1LA9OF+t1ku4VXWTNR3J2d9yYA2/XlBV4ZnR3ol ZoUOGYLXD2sXWJKII5CFqncBk25u6FdAYTFdlU/OgTmJPxGs9luCjy5XlvOm8zi7 NyrdNCyDnbDwuTs/k+582Z/VGqyLQ==
X-ME-Sender: <xms:Ayu0Xoxr9NXfTdRTTjW3jOqjAyJcx8vH4v8W7bZ5hW6tdENfAWBbMg>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduhedrkedtgdekkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpefofgggkfgjfhffhffvufgtgfesthhqredtreerjeenucfhrhhomhepfdevhhhr ihhsthhophhhvghrucghohhougdfuceotggrfieshhgvrghpihhnghgsihhtshdrnhgvth eqnecuggftrfgrthhtvghrnhepkeffkeevgefhgfdtffeivedugfeltdehhfefvddvheel iedvgeevgeelfeetjedunecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrg hilhhfrhhomheptggrfieshhgvrghpihhnghgsihhtshdrnhgvth
X-ME-Proxy: <xmx:Ayu0XshHYwm6C2N7bTgbQaz5nR-4crznV067_c172dYR3WG4jxg2oQ> <xmx:Ayu0XjPzUUiqMTmy5_TODO6lDUpfnauXzB2p-kk0W7BlW_3Rz9Udkw> <xmx:Ayu0XqZD1grW0UDYCxhYXTRqSLNodx0GuqdidoYtgS92w66u4lj6Qg> <xmx:Ayu0XrUs9B6qLOdZRoMPALklgjO_zRuXoCRyjyTfonLyNlsqMFxkdg>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 585FF3C00A1; Thu, 7 May 2020 11:36:35 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.3.0-dev0-413-g750b809-fmstable-20200507v1
Mime-Version: 1.0
Message-Id: <8f02c62d-df5d-4cb1-a79a-4aa2c80026b7@www.fastmail.com>
In-Reply-To: <88B1A4A0-4EFB-4094-87DC-EDB13BEE632A@shiftleft.org>
References: <710336c1-b499-4119-a0d8-a1aaa16a0b07@www.fastmail.com> <88B1A4A0-4EFB-4094-87DC-EDB13BEE632A@shiftleft.org>
Date: Thu, 07 May 2020 08:36:15 -0700
From: "Christopher Wood" <caw@heapingbits.net>
To: "Mike Hamburg" <mike@shiftleft.org>
Cc: cfrg@irtf.org
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/TDVq6Qnsn7DQowbbvjRuxPlpBrE>
Subject: Re: [Cfrg] hash-to-curve updates and suite reduction
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: Thu, 07 May 2020 15:36:40 -0000

Hi Mike,

Apologies for the delay, and thanks for raising this point. Please see inline below.

On Fri, May 1, 2020, at 4:52 PM, Mike Hamburg wrote:
> Hello Christopher,
> 
> Sorry to be so late in the game on this, but I have a concern about 
> Elligator 2 as defined in hash-to-curve.
> 
> One of the nice properties of Elligator 2 is that it’s an injective map 
> on [0..(p-1)/2], which is useful for canonically inverting the map.  
> However, the draft version is not injective on this domain.  Wouldn’t 
> it be better to choose sgn(t) according to is_square(gx1) instead of 
> according to sgn(u)?  That would also make it match the paper, except 
> for the different definitions of sgn().

I agree that inverting the map can be quite useful for some applications. However, to the best of my recollection, we haven't heard requests for this injective property in the past. I don't have a particularly strong opinion on this point, so I'm curious to hear what others here think about this proposal. 

Best,
Chris