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

Adam Langley <agl@imperialviolet.org> Thu, 27 June 2019 16:01 UTC

Return-Path: <alangley@gmail.com>
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 C0B881201E5 for <cfrg@ietfa.amsl.com>; Thu, 27 Jun 2019 09:01:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.398
X-Spam-Level:
X-Spam-Status: No, score=-1.398 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.249, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.25, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] 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 3KE6LzpxCAWe for <cfrg@ietfa.amsl.com>; Thu, 27 Jun 2019 09:01:56 -0700 (PDT)
Received: from mail-qt1-f172.google.com (mail-qt1-f172.google.com [209.85.160.172]) (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 52C7712013B for <cfrg@irtf.org>; Thu, 27 Jun 2019 09:01:56 -0700 (PDT)
Received: by mail-qt1-f172.google.com with SMTP id d17so2986476qtj.8 for <cfrg@irtf.org>; Thu, 27 Jun 2019 09:01:56 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=P6jLcPplNgWuZV9czdXTyY1J86mUfhoUpQRb6+WY40U=; b=cJLYcYeX4otUJ359vjkc17+SJkm1eyOMUKR4B8LHsqm8pZ4W8YM/tJ4ZLhUkTmaDo3 6NLIt2P1qWzayfpg9FnTpQgB9VGzD16BcK8dFQ1EuxVOsOr2LNa4b6JS+iBPQVs4BR80 oBHOCIVBhkvbRa+k3Nj26UdsjYZX8BNhloZqynoduguAEKmx6J5KDcdtAuSjKGGoz7xP ANjsbUtFnd3jswDtLzx6kcNVsCh/aXBoiOvcxAuzh5wNs8yCD+mr5yu5NsOv/JFzzLnx vD7zJOQ9alLPvt2J7fguKEVhlv4Of03I2qXgal3B1eBt8EK2fqSD6emXzMvRQ9UEGKb+ Vsug==
X-Gm-Message-State: APjAAAVZpQT/Ea/ol3c5FV4A0Fu4Ofm37NQ3uvemhBqS5BmoZ6KzehZr GBvNu7IHxJ8eswLsQAMin8QCG69LFRyNPSOflwk=
X-Google-Smtp-Source: APXvYqyY99zVW9UfrCLBBPKGfq5GOVm3emwYJalFVDvN/2To4aTfu8znyGtv//J5trP4bC3ZYExpJAmQL2b3BNprUcE=
X-Received: by 2002:ac8:3908:: with SMTP id s8mr3809124qtb.224.1561651315129; Thu, 27 Jun 2019 09:01:55 -0700 (PDT)
MIME-Version: 1.0
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>
In-Reply-To: <trinity-7a6958c3-8eaf-4daf-904f-d682b4802f73-1560883212718@3c-app-webde-bap22>
From: Adam Langley <agl@imperialviolet.org>
Date: Thu, 27 Jun 2019 09:01:44 -0700
Message-ID: <CAMfhd9W9bPkWZUmK9MvjNV6n6wW33m2u8MJGN4XGoG4Gg-om=Q@mail.gmail.com>
To: =?UTF-8?B?QmrDtnJuIEhhYXNl?= <Bjoern.M.Haase@web.de>
Cc: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000e6c3be058c504747"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/f7V0Em_kVshO2ww7AAgTRDFuh8k>
Subject: Re: [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: Thu, 27 Jun 2019 16:01:59 -0000

On Tue, Jun 18, 2019 at 11:40 AM "Björn Haase" <Bjoern.M.Haase@web.de>
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
>

(I think I wrote out something similar in
https://www.imperialviolet.org/2013/12/25/elligator.html . I'm not very
good at these things so the steps are smaller and more numerous, but that
might be helpful for some.)