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

Daira Hopwood <daira@jacaranda.org> Mon, 03 May 2021 06:23 UTC

Return-Path: <daira@jacaranda.org>
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 D77133A0884 for <cfrg@ietfa.amsl.com>; Sun, 2 May 2021 23:23:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.383
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=jacaranda.org
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 CWnVorHWhNoQ for <cfrg@ietfa.amsl.com>; Sun, 2 May 2021 23:23:09 -0700 (PDT)
Received: from krystal1.wisercloud.co.uk (krystal1.wisercloud.co.uk [185.53.58.188]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 23B2A3A086E for <cfrg@ietf.org>; Sun, 2 May 2021 23:23:08 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=jacaranda.org; 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 host86-179-54-144.range86-179.btcentralplus.com ([86.179.54.144]:52106 helo=[192.168.1.85]) by krystal1.wisercloud.co.uk with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94) (envelope-from <daira@jacaranda.org>) id 1ldRz1-00EYNa-FY; Mon, 03 May 2021 07:23:07 +0100
To: Rene Struik <rstruik.ext@gmail.com>, "Riad S. Wahby" <rsw@cs.stanford.edu>
Cc: cfrg@ietf.org
References: <e270e62d-941d-0a87-7dc9-cf80f73b5aeb@jacaranda.org> <108aae2c-576d-ba68-34b8-c539d3fb945d@jacaranda.org> <d2f89438-faeb-47db-97f9-c7ebb394f348@www.fastmail.com> <8c736a71-8ef0-dd8e-1b5a-47cccf1af410@jacaranda.org> <20210422164424.5qwe5msxueqz6rrk@muon> <3360a3c2-9afc-332b-c3c7-6c8c512f8c1b@jacaranda.org> <20210423193036.szrrpvg7zbtplkor@muon> <bd249275-09aa-9432-6052-602a832c542f@gmail.com>
From: Daira Hopwood <daira@jacaranda.org>
Message-ID: <e5a4286f-d751-a35e-5ce6-349641a8602b@jacaranda.org>
Date: Mon, 03 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: <bd249275-09aa-9432-6052-602a832c542f@gmail.com>
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 - krystal1.wisercloud.co.uk
X-AntiAbuse: Original Domain - ietf.org
X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12]
X-AntiAbuse: Sender Address Domain - jacaranda.org
X-Get-Message-Sender-Via: krystal1.wisercloud.co.uk: authenticated_id: daira@jacaranda.org
X-Authenticated-Sender: krystal1.wisercloud.co.uk: daira@jacaranda.org
X-Source:
X-Source-Args:
X-Source-Dir:
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/O1PBcjQE5b3ysYJqIDs1w8467wc>
Subject: Re: [CFRG] (suggested language re mixing square roots and inversions) Re: 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, 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