Re: [Cfrg] draft-irtf-cfrg-hash-to-curve // More efficient method available for elligator2

"Christopher Wood" <caw@heapingbits.net> Thu, 27 June 2019 15:43 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 3F1C912011F for <cfrg@ietfa.amsl.com>; Thu, 27 Jun 2019 08:43:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.7
X-Spam-Level:
X-Spam-Status: No, score=-2.7 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_LOW=-0.7, 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=mBkTRz+A; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=Agyv12OI
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 e_3XVZGhiTHH for <cfrg@ietfa.amsl.com>; Thu, 27 Jun 2019 08:43:23 -0700 (PDT)
Received: from out1-smtp.messagingengine.com (out1-smtp.messagingengine.com [66.111.4.25]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EB99B120045 for <cfrg@irtf.org>; Thu, 27 Jun 2019 08:43:22 -0700 (PDT)
Received: from compute6.internal (compute6.nyi.internal [10.202.2.46]) by mailout.nyi.internal (Postfix) with ESMTP id E78A121F14 for <cfrg@irtf.org>; Thu, 27 Jun 2019 11:43:21 -0400 (EDT)
Received: from imap4 ([10.202.2.54]) by compute6.internal (MEProxy); Thu, 27 Jun 2019 11:43:21 -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 :subject:content-type:content-transfer-encoding; s=fm1; bh=9kFOn y2W7H+myrqxOOIpS+msS/L/ZZLDYn8FeOQ73sc=; b=mBkTRz+AogUsZszMdIDuq BZamPqGG5dvKbwOxG+0G5snC5fPIT+CK1fcVU2C4zcGZ5qGXwib4VK1gqgdaQqJG ptUh7+z126D8HOkPAjg2k/ZAvAeEFeAtsNK+L1UMWc7qOgz9yF/JsO65+RjJ8MyM eqySsYWTiMtbXuIpHEMjC4PUX2sG/8xuC/eEfSp2zG9wLF8DoIQEuLZ5sgps764d iJ+7tkrWGdlEuYXTRVbEqMyIUV2MXrtTdU+YG57HelSP7gUM2UEbREvyvJCoO5qm BtA2EjojBa3jxK5UiZKtnN2+Z3jEp1KJCHQwvwQOPeXFsXYq2uldLbjwEos3fNgt g==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=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=fm3; bh=9kFOny2W7H+myrqxOOIpS+msS/L/ZZLDYn8FeOQ73 sc=; b=Agyv12OIeV7r+Bx+ruUPowXpzxzwA9H3tdDRDnMVWMOqFSviTvvFuLOt7 rfPO0V9+Briu8IeGafvtfNqN8hwI73pjLzRee6d4BhnqfekLW7b1HXtqHmuogXl6 QzkNDvFAj13DtsDPodQCzTVPCzCctqEjTwcBeesoIFEqpNyQaOmz/5DkkZHB5WDB 1YB7NEIBaiIHrpcHxa6ZQfuy2dqBbbIMnz2VODvysReYXuZOvn25Y9Pb+QgVeK6/ g/ElhYihBwAY+cfnBt7HvhY46ODqdm380IJDzKfU1paXp2PDlI3zxPUtgoArlnQE gXXsf6f/lS3bF3Vv5qDKSPcAZI9Ow==
X-ME-Sender: <xms:GeQUXdPL0TCOx-VJyql3Rrh2ECymz5SGX301UP_aFE03s9jWNSGz4A>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduvddrudekgdelgecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkjghffffhvffutgfgsehtqh ertderreejnecuhfhrohhmpedfvehhrhhishhtohhphhgvrhcuhghoohgufdcuoegtrgif sehhvggrphhinhhgsghithhsrdhnvghtqeenucffohhmrghinhepihhrthhfrdhorhhgpd hgihhthhhusgdrtghomhdpihgrtghrrdhorhhgnecurfgrrhgrmhepmhgrihhlfhhrohhm pegtrgifsehhvggrphhinhhgsghithhsrdhnvghtnecuvehluhhsthgvrhfuihiivgeptd
X-ME-Proxy: <xmx:GeQUXaF4_D33GN_a7k2u_3i0VBo3jPDiVOQoJbsXB1Vj4jaMaeN1CQ> <xmx:GeQUXd-LJd9ADcuAM62Ujia4gK2le_eYEooSxtHhXhfpOmE81TQm5A> <xmx:GeQUXYa5dpQo2q-BUy_yl7wGREQMl4alspcveXD0_T7D5jB4rqR_ew> <xmx:GeQUXTJMMRTOsNCy1HfvlpaRMHO2-eFxQUvEJ-U2RyDuFJgZwVXJUw>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 73BDE3C00A1; Thu, 27 Jun 2019 11:43:21 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.1.6-730-g63f2c3b-fmstable-20190622v1
Mime-Version: 1.0
Message-Id: <9122d91a-6dea-46a1-84ce-1bcd11b5dafe@www.fastmail.com>
In-Reply-To: <trinity-7a6958c3-8eaf-4daf-904f-d682b4802f73-1560883212718@3c-app-webde-bap22>
References: <249D87DF-0448-4BD1-A3A6-E9E88B0A4E87@live.warwick.ac.uk> <trinity-6ee830b9-216e-4c37-abd3-3b323c6f9018-1560877773355@3c-app-webde-bap22> <trinity-7a6958c3-8eaf-4daf-904f-d682b4802f73-1560883212718@3c-app-webde-bap22>
Date: Thu, 27 Jun 2019 08:43:21 -0700
From: "Christopher Wood" <caw@heapingbits.net>
To: cfrg@irtf.org
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/YzYxDZBH-mkqJXggbc9BcATB_dE>
Subject: Re: [Cfrg] =?utf-8?q?draft-irtf-cfrg-hash-to-curve_//_More_efficient?= =?utf-8?q?_method_available_for_elligator2?=
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, 27 Jun 2019 15:43:25 -0000

Thanks for the pointer, Björn! I filed [1] to track this issue.

Best,
Chris

[1] https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/issues/133

On Tue, Jun 18, 2019, at 11:40 AM, "Björn Haase" wrote:
> Hello to all, I hope that via this list I might be able also to reach 
> the contributors of the
> draft-irtf-cfrg-hash-to-curve draft at github
> https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/blob/master/draft-irtf-cfrg-hash-to-curve.md
> over this list.
> Regarding the Elligator 2 map, the algorithm shown in the github 
> version of the draft is actually slower than necessary. It requires two 
> exponentiations (for one inverse and one square root).
> Some time ago Mike Hamburg did point me to a solution on how to 
> implement this with one single exponentiation. The algorithm is found 
> also somewhere hidden within the Ed25519 paper of Bernstein, Duif, 
> Lange, Schwabe and Yang. Still Benoît and me did consider it helpful to 
> write down the faster algorithm explicitly in our last paper, because 
> we thought that there might be others that missed this optimization 
> opportunity :-).
> You'll find the explicit write-down in section 8.2 on page 33 of
> https://tches.iacr.org/index.php/TCHES/article/view/7384
> Yours, 
> Björn
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>