Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-curve-10

Daira Hopwood <daira@jacaranda.org> Mon, 04 January 2021 13:52 UTC

Return-Path: <djhopwood@googlemail.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 9E2C53A0D3E for <cfrg@ietfa.amsl.com>; Mon, 4 Jan 2021 05:52:52 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.138
X-Spam-Level:
X-Spam-Status: No, score=0.138 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.249, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.248, NICE_REPLY_A=-0.262, RCVD_IN_DNSWL_BLOCKED=0.001, 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 (2048-bit key) header.d=googlemail.com
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 y7OHGoXv-SF8 for <cfrg@ietfa.amsl.com>; Mon, 4 Jan 2021 05:52:50 -0800 (PST)
Received: from mail-wr1-x432.google.com (mail-wr1-x432.google.com [IPv6:2a00:1450:4864:20::432]) (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 6569D3A0CC5 for <cfrg@ietf.org>; Mon, 4 Jan 2021 05:52:50 -0800 (PST)
Received: by mail-wr1-x432.google.com with SMTP id m5so32193615wrx.9 for <cfrg@ietf.org>; Mon, 04 Jan 2021 05:52:50 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20161025; h=sender:subject:from:to:references:cc:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=MnMEkDIUh0raII+XHGw1q3U3lVIuyP9ki+Yn9sxXkb8=; b=HPpA7ii42xkIkFe4qAaXzjW4/Giy8JNRQWJ32vX+avtsqmL9BZZIzZ59rkR0k1K7ep Ra6MxeSue9/5lFSL1oJQecgRzqTt1hy23Q/zj0bfFDBEGq2u77YoXidLj899f9ozWPR7 9yLENN/OtzHNy+pfzn2mWtx0daNutHsX5HphD578R+omqn/cGjYBjLzn3Yw5akZbEzUD 5AXBQ5oLcRXj6PIxzohiQo790EoppKVYjkOq4N0vLCc0LLNe9/IlX8wVGotwsLogslh9 r2QmZsaUUoSU9EBF9meDGons9D+JIewGofhZ4yXy0G7v5UxmfnGb53YYwdfWXgtCcq1b YzOQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:subject:from:to:references:cc:message-id :date:user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=MnMEkDIUh0raII+XHGw1q3U3lVIuyP9ki+Yn9sxXkb8=; b=os6YODs67na/l0qQZHVIdT/vrTsX4OMygySnWbJN6s+k81v+RHDc/kBenV4zWs3AkT gty28jrZ3gb6hN55tQ8Wfrk1XaSGArxE7x9gZcXSOhp11xDJ+8EnKei5MIfJzOu5tqB+ nQCd7w8k0Jt1ARS6Ylib8++2aSsZYq7me261jcyDYm5JiYgvO9LsCyQbeQihz8ts/nmi spaLws8NBDjPHib36GqdF98/fBFqnEMpDw3WC5jcQH0Gbc6S1A7eC1/6TqIYLWgOTjNm ixSjAya629QRucpGFXEU2RwJ+MbH6gMBSyOKDba6265DEpcJxfE5UO38c2AeGBLQrF4k GgQw==
X-Gm-Message-State: AOAM530rkuwp0CnBY6ileNFMuGAku5SiHatH4IlUV/RYcRA8U9PeVAwO rJ277IifDcauFT+j9grT52dpXRLVwvY=
X-Google-Smtp-Source: ABdhPJymD30ZKF/3imek/GF0R4Ok/brHS9s6+nAAPnWEpCNXOxP944RW6H3ANY6n4jgPYxkRA+miqg==
X-Received: by 2002:a5d:6607:: with SMTP id n7mr77408810wru.206.1609768368867; Mon, 04 Jan 2021 05:52:48 -0800 (PST)
Received: from ?IPv6:2a00:23c5:1203:ce01:4883:54d2:fa08:b19f? ([2a00:23c5:1203:ce01:4883:54d2:fa08:b19f]) by smtp.gmail.com with ESMTPSA id y6sm33568584wmg.39.2021.01.04.05.52.47 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 04 Jan 2021 05:52:48 -0800 (PST)
Sender: Daira Hopwood <djhopwood@googlemail.com>
From: Daira Hopwood <daira@jacaranda.org>
To: cfrg@ietf.org
References: <e270e62d-941d-0a87-7dc9-cf80f73b5aeb@jacaranda.org>
Cc: Sean Bowe <sean@electriccoin.co>, str4d@electriccoin.co
Message-ID: <108aae2c-576d-ba68-34b8-c539d3fb945d@jacaranda.org>
Date: Mon, 4 Jan 2021 13:52:47 +0000
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <e270e62d-941d-0a87-7dc9-cf80f73b5aeb@jacaranda.org>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/jVlyTyQLMT05skb38t9XTW4IVHk>
Subject: Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-curve-10
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: Mon, 04 Jan 2021 13:52:53 -0000

On 04/01/2021 13:40, Daira Hopwood wrote:
> A prototype specialized for n = 32 and the
> [Pallas/Vesta](https://electriccoin.co/blog/the-pasta-curves-for-halo-2-and-beyond/) 
> 
> curves is at https://github.com/zcash/pasta/squareroottab.sage .

Corrected URL:
https://github.com/zcash/pasta/blob/master/squareroottab.sage

> Now given divsqrt, we can apply another optimization in section 4.2
> of [WB2019] that avoids needing to test whether gx1 (using the notation
> of the Internet Draft) is square. In brief: we first compute the
> numerators and denominators for x1 = N/D and gx1 = U/V as in the
> paper. If gx1 is not square, then we have sqrt(h * gx1); using a
> precomputed square root of Z/h, we can calculate the numerators and
> denominators of x2 and y2, without ever needing to calculate gx2.
> The detail is explained in comments at
> https://github.com/zcash/pasta/hashtocurve.sage .

Corrected URL:
https://github.com/zcash/pasta/blob/master/hashtocurve.sage

-- 
Daira Hopwood