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

"Björn Haase" <Bjoern.M.Haase@web.de> Tue, 18 June 2019 18:40 UTC

Return-Path: <Bjoern.M.Haase@web.de>
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 C569812041E for <cfrg@ietfa.amsl.com>; Tue, 18 Jun 2019 11:40:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.974
X-Spam-Level:
X-Spam-Status: No, score=-1.974 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, MIME_HTML_ONLY=0.723, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=web.de
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 po389N2u54Pv for <cfrg@ietfa.amsl.com>; Tue, 18 Jun 2019 11:40:17 -0700 (PDT)
Received: from mout.web.de (mout.web.de [212.227.17.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D7EEF120280 for <cfrg@irtf.org>; Tue, 18 Jun 2019 11:40:16 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1560883212; bh=2SeJNNvi1Q3Mi7Znir2wm3sXmEgo/v5rNfpmurbhjzM=; h=X-UI-Sender-Class:From:To:Cc:Subject:Date:In-Reply-To:References; b=qZn92ZOXqymhM0y/kfhoji5Bew1Z7btnwJfR4HhJ6sFL9+6elH/RmMA5jCs1+SWlT TFbtYc6Vy9/I0ZaQHFDPHB8ALlYmMxdUOakmUbgHGL7er99zwHxAplVbTYyLZ3zPvn mOIcH0+wtR8ZFthZs/1P+ScjiU6kUSKjLCdPFfjQ=
X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9
Received: from [178.2.114.231] ([178.2.114.231]) by web-mail.web.de (3c-app-webde-bap22.server.lan [172.19.172.22]) (via HTTP); Tue, 18 Jun 2019 20:40:12 +0200
MIME-Version: 1.0
Message-ID: <trinity-7a6958c3-8eaf-4daf-904f-d682b4802f73-1560883212718@3c-app-webde-bap22>
From: =?UTF-8?Q?=22Bj=C3=B6rn_Haase=22?= <Bjoern.M.Haase@web.de>
To: =?UTF-8?Q?=22Bj=C3=B6rn_Haase=22?= <Bjoern.M.Haase@web.de>
Cc: CFRG <cfrg@irtf.org>
Content-Type: text/html; charset=UTF-8
Date: Tue, 18 Jun 2019 20:40:12 +0200
Importance: normal
Sensitivity: Normal
In-Reply-To: <trinity-6ee830b9-216e-4c37-abd3-3b323c6f9018-1560877773355@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>
X-UI-Message-Type: mail
X-Priority: 3
X-Provags-ID: V03:K1:Wu7lTkogbDEbKx57JSlKvSxo0Lx3zWFj79wzI4p6G8Ry1VlU3BKILuYHkra5UN/0yckou HbsaaedHfycvVJUAofP+HUs+HShjQzSQLyI78e1Y85HAyTI/4FJWw1Ic8QFgOM59TgJr9cb8Q0vQ aXaTu72T8fZOEedDJOZl0b4PKd+jyCuN4HoQtoFESEH6TOg0atVXMIl1V3Lrg68A4QvV6XrdFdi0 YPvViH288Ndvq+wfA4JoeChYYkfx6SrHw7jWiSTn4zfQhwoSmP7dMB/OMYv7Io7QHrNE7lKJFaWz tU=
X-UI-Out-Filterresults: notjunk:1;V03:K0:eF/N5q5+jtw=:7FuxTksTaBxD0BmbrfGBJ2 mDFgBjUtulUwRVZdxRBgsm2mpKEbJ93vCEmVTJa/WRP0mSbhJlv2EABPBUueMdQeIb+7VyLja D/WegIakQFda2OVVMga5/bxosakWyDpnvYdd2SxAT0HSKhcXubg7hVzYH7oh9ovVgcpECuIxA 0dmsFrtjz5+tbgmuKSgt5tLuycaqWzdkLjTZN1gJKc/ohx/7+mEUbmUag1Ln0BZu6hFy9aCmh WSlUrQm7ojsThCXV7rhXwa8fZkYu1uTxNzU38iFAROtKzVO4W8zdE6QlrboYxvO9GSzS+nKvH pji5DQWXCnISoSy9G3pmgnEHD/7cAjyUgwJEImjDnlgkAJ0VClu/GykEM5LP5edtb25ABYtcJ TykI8566vk9ZSfFEfHUUmc8hRjiuDr/OELSBTmX119MU/KF0r/4BGwCGVVtPzxj/fHNqcz/BO CaAhx9+yEaSLcZE8oodk+z4DRTjmu4mR2sqzK1V2jzcTGwIFoNwmC0RIoaKFGj118aWbOnvEB ehpqBGDfySPxqnsxrFuXsNdE/E89GacuslsvFK7uURDsTWV1VsYsn6gR9oJ0oq8oQf+Hd6qub C8A0ENE5gXYxkzFTiPxwf1H4XNA1I0gsexsYHqIwUo2TSidaBHEj20lQ==
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/P5vdXoNPCSflyDRzIEqWKk8GzF8>
Subject: [Cfrg] draft-irtf-cfrg-hash-to-curve // More efficient 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: Tue, 18 Jun 2019 18:40:20 -0000

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
 
 
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
 
 
Yours,
 
Björn