[Cfrg] Repost as non-html-mail: draft-irtf-cfrg-hash-to-curve // More efficient method available for elligator2

"Björn Haase" <Bjoern.M.Haase@web.de> Tue, 18 June 2019 20:03 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 7CF2012023C for <cfrg@ietfa.amsl.com>; Tue, 18 Jun 2019 13:03:21 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
X-Spam-Status: No, score=-1.998 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, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham 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 lJiehjew0JEF for <cfrg@ietfa.amsl.com>; Tue, 18 Jun 2019 13:03:19 -0700 (PDT)
Received: from mout.web.de (mout.web.de [212.227.15.3]) (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 44B16120301 for <cfrg@irtf.org>; Tue, 18 Jun 2019 13:03:18 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1560888195; bh=xfJYQrsDQvKHQmT3cBPjPA8/1aVHhHlrNzJcQA2VqU0=; h=X-UI-Sender-Class:From:To:Subject:Date:References; b=rtEUGpk2KzRM80wpwuRQ2x93F7y6kU4Lt8kSRtYuPLaqXVjMOHkglIc71z2JYyQHI k6sUbtz1KOM8Llkbrx6R7ic7IMoRbb2GFvBtqMwPyQHlkrMFlTdMDQb+0heEzJhM5S FQqQysPc1LfcALAXJJM7TasVoI/wlv4sTcMgzgMQ=
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-bs39.server.lan [172.19.170.39]) (via HTTP); Tue, 18 Jun 2019 22:03:15 +0200
MIME-Version: 1.0
Message-ID: <trinity-286f9103-fdb9-4e36-8a32-2f00453eaf22-1560888195787@3c-app-webde-bs39>
From: =?UTF-8?Q?=22Bj=C3=B6rn_Haase=22?= <Bjoern.M.Haase@web.de>
To: CFRG <cfrg@irtf.org>
Content-Type: text/plain; charset=UTF-8
Date: Tue, 18 Jun 2019 22:03:15 +0200
Importance: normal
Sensitivity: Normal
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>
Content-Transfer-Encoding: quoted-printable
X-UI-Message-Type: mail
X-Priority: 3
X-Provags-ID: V03:K1:thiFfSluVGU9NKs0aLD98xKI6KLwKWEQLMfVQWvDzmeZra6v2BAUSbFEzawx8HtjMk1/g oUQ3RyjaM56oL/HnXK0pRUfybKd90h+c70YGhh43l1eaP0wqS+jadb+0+g2U7z4NFJBY3EJ6up0F rAjON/HDbF7nxaT7Eom0eUE+jLT2v18KEhELaPThqd9iCvIZITMnHP2cPwUgPyyciwJ9/ZXX00io 9w/r+l1fjchf72NSqSWqVZUTHYGJaHPYETAtDBtRs0xpFM4VivbkgN/7udxyw8WG2rc/uKqK01jl yQ=
X-UI-Out-Filterresults: notjunk:1;V03:K0:JUEONgxeT4Y=:E7EGZDzP6Dk8SZOUro0LqF Pk8CjZkWL5x+LhNi16X498uv9n31DunEjXYmCrj8qEaIo2AbPnWB155ySeP4WOOOJTkEv6PLQ HaDUhVEKGMJMCU9fEWTG2415eabzIKVOb3dolVNWIutQY8NF54tWjPu2GZj+kLS7luqHgKgfT 7mCntSvLAxZF39BhRRqC4sPJsvXT2xQPLN94+V5Lalj2Ej2UgDwBUw00Yfnzj/CN2ssU8VlJq rVrRsmlXIlODdmgemO+ADJyeuobPkTp1ZeE9GnG1/Yb46HvSK1eo9Feg3czGNLhpZqf7YWggh YVmME0CkImRpNno2fZn3jZ+G4Ll/dbCMhwlPU6wdKgvGnKlJI7RUMLDJpmoXOlP9YwKrYe+9j NMxeclAg3r6t0Rqwba3wqFXaNQol43h+V1/juqWov+5YG/n8Ou1Y543Bf1yRYL8B0RWJ+3PqV gviBhWowxJEZPgM8S1NMxnGejre5xVC1Os6/cBIEIGCki5UB8+tda//eFRs5oRhEQdgkS7iRA Mlq+m5EDynoIfozUiqZrLSjXv8BJboWkT4RUZsz6wBmvh8B7esgoXw30AETOVs6vli+vlVE4H dhF7+fFcDvB0HVHl1bXnOR62dElX2/ZhNtzHu97ghah4yUMft8ZZutRw==
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/DgdhwPfks13_smihRhb4-U6GkzA>
Subject: [Cfrg] Repost as non-html-mail: 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 20:03:22 -0000

This is a re-post: Eric Crocket informed me that my posts today did not get through.
 

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
.
 
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[https://tches.iacr.org/index.php/TCHES/article/view/7384]
 
Yours,
 
Björn