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
- [CFRG] Comment on draft-irtf-cfrg-hash-to-curve-10 Daira Hopwood
- Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-cur… Daira Hopwood