Re: [CFRG] (suggested language re mixing square roots and inversions) Re: Comment on draft-irtf-cfrg-hash-to-curve-10

Daira Hopwood <> Mon, 03 May 2021 06:23 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id D77133A0884 for <>; Sun, 2 May 2021 23:23:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 0.383
X-Spam-Status: No, score=0.383 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HAS_X_OUTGOING_SPAM_STAT=2.484, NICE_REPLY_A=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id CWnVorHWhNoQ for <>; Sun, 2 May 2021 23:23:09 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 23B2A3A086E for <>; Sun, 2 May 2021 23:23:08 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed;; s=default; h=Content-Transfer-Encoding:Content-Type: In-Reply-To:MIME-Version:Date:Message-ID:From:References:Cc:To:Subject:Sender :Reply-To:Content-ID:Content-Description:Resent-Date:Resent-From: Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id:List-Help: List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=4BY333nzx45XB4W9zZybs43h0x/6JtaHgm4+5oYpik4=; b=YHdTPyWu4psdLnSJU5/B1Kw8Tu Y6fJOhOdWqEzFEUgGcuYW1IOfa8wxytLinNzA3UmGZsK5rUQvVzDu0MaiqcXC6uv0saIw/RArd1gz 1E7hBGcZZldA8harKdDQrKqx7xdXrX45y2FwfQF7PLhpvTLSRMtV1fV35oy04kLYp9PyuUGtdJm5T cMYOQJLzJuQAG+KRnLYOpkuOKqW8WKBQxmzMEmi6+kzNABADxLtC1KFLDV4GvyVOH6Wdr6I2qK46B 7gUWABeJSf8KdEn9aryfQa0ak9pq3NATBs4UA4z1Epjr3pA+BiqJMoxf2LlbshJQHk4rzmq7IcAOP ci165d2w==;
Received: from ([]:52106 helo=[]) by with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94) (envelope-from <>) id 1ldRz1-00EYNa-FY; Mon, 03 May 2021 07:23:07 +0100
To: Rene Struik <>, "Riad S. Wahby" <>
References: <> <> <> <> <20210422164424.5qwe5msxueqz6rrk@muon> <> <20210423193036.szrrpvg7zbtplkor@muon> <>
From: Daira Hopwood <>
Message-ID: <>
Date: Mon, 3 May 2021 07:23:06 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.9.0
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
X-OutGoing-Spam-Status: No, score=-0.5
X-AntiAbuse: This header was added to track abuse, please include it with any abuse report
X-AntiAbuse: Primary Hostname -
X-AntiAbuse: Original Domain -
X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12]
X-AntiAbuse: Sender Address Domain -
X-Get-Message-Sender-Via: authenticated_id:
Archived-At: <>
Subject: Re: [CFRG] (suggested language re mixing square roots and inversions) Re: Comment on draft-irtf-cfrg-hash-to-curve-10
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 03 May 2021 06:23:14 -0000

On 23/04/2021 21:47, Rene Struik wrote:
> Hi Riad:
> Text along the following lines would avoid implementation detail, but 
> would illustrate how one could "mix" inversions and square roots:
> The inverses of two nonzero elements y1 and y2 of GF(q) can be computed 
> by first computing the inverse z of y1*y2 and by subsequently computing 
> y2*z=:1/y1 and y1*z=:1/y2.
> This method can be used to compute the inverse and a square root, 
> respectively, of two nonzero elements x and y of GF(q) (where y is a 
> square in GF(q)) by first computing a square root z of 1/(y*x^2) and by 
> subsequently computing a square root of y as x*y*z and the inverse of x 
> as x*y*z^2.

But computing the inverse and the square root in parallel isn't what
we're doing. The combined inverse-and-sqrt method we're referring to
here isn't rocket science, it will be familiar to anyone who has
implemented Ed25519.

> I think this would be easier to read than any "div" verbiage and avoids 
> having to deal with divisions by zero.

Just to be clear, there are no divisions by zero in the specification
I gave in my previous post:

  Let h be some fixed nonsquare in Fq. Define sqrt_ratio for
  u ∊ Fq and v ∊ Fq* as:

    sqrt_ratio(u, v) = (true, sqrt(u/v)),    if u/v is square in Fq
                     = (false, sqrt(h*u/v)), otherwise.

Notice that sqrt_ratio is not defined for v = 0, and it is easily proven
that it is never applied with v = 0.

Daira Hopwood