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

Rene Struik <rstruik.ext@gmail.com> Fri, 23 April 2021 20:47 UTC

Return-Path: <rstruik.ext@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 DF8F63A0ADA for <cfrg@ietfa.amsl.com>; Fri, 23 Apr 2021 13:47:18 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level:
X-Spam-Status: No, score=-2.099 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, FREEMAIL_FROM=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.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 VX4xr1Lofx_3 for <cfrg@ietfa.amsl.com>; Fri, 23 Apr 2021 13:47:14 -0700 (PDT)
Received: from mail-qk1-x72e.google.com (mail-qk1-x72e.google.com [IPv6:2607:f8b0:4864:20::72e]) (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 806113A0ADD for <cfrg@ietf.org>; Fri, 23 Apr 2021 13:47:14 -0700 (PDT)
Received: by mail-qk1-x72e.google.com with SMTP id y136so18861629qkb.1 for <cfrg@ietf.org>; Fri, 23 Apr 2021 13:47:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=to:cc:references:from:subject:message-id:date:user-agent :mime-version:in-reply-to:content-transfer-encoding:content-language; bh=PLTMzh+jVe0mtjo2vorgWGzoN5OlOrZJXRb8USYU3kQ=; b=Wv7BZvt169AqxAs4oXqx0fB1hBxX82x8XWH3qwOeBvw/IR0AcdgxE3H7lnVhCBr9Ec YfiKFyIL0No2nVVOpYPu80GAdUKrAoEHcfuzq2cqdSbE+kVMn8cAa6qzZvNl7ZG9tDfR 8hdgOklKFZka/y+M0ub5BDRtSMZdMurdyipfeM/5fwOGL4R+y2H0mEWIYib/0GMYiXEe S4MliCSP9BY1rj7uH7S9aRbTo0IPJu77JHwrvgIrX0lJWhrd/Q8lU/ksYnW/Vl5iBEu/ TCXk+fIlh0DVlcBSt2cdgM5ccKYDHi6kvwaQdutVGA6OEeCQHKn7nHargEZhC6oy3tVg HW6A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:cc:references:from:subject:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=PLTMzh+jVe0mtjo2vorgWGzoN5OlOrZJXRb8USYU3kQ=; b=RghhIgDl18IfRx6TcFWohPLmw2ltMNJrOTo0j5k5kWcBJywC2CDolSnbiL45mKbuJE CLKjrCWAa758rjhpaTlDQqDK1ailL3dqi05wGc2Nd+gPT2EUhaPN49zqA5v+bCMsLEkY J5/AU3jOraX+gNYoUGagRYCLBVEmrOZrX9OPX5MJrPTPOt33xov68bhZx59ltgYOGHbq GQ8wZjeYNOeIR+pmFkpVChiPXftLHf/rHmdUe67vqh3I7tYySIdlJQ2NzHWwIiikVES6 I/FMY+jnsaO0fSI7BoANH53KCmsBI6OoD3AEZ6ek2AItBtzNfiFKQiCxzb/ceNH5AIum s9yQ==
X-Gm-Message-State: AOAM533+7vTayRQaGoOAWMc1M44Hs0CQTRNcTQPgWs8IfbjkpHbTrT8t rbLwSnUQoKZZpZv5hd0xFrAy/665YWI=
X-Google-Smtp-Source: ABdhPJy2CTjkXCgp+zGOEMd6Z7R7dyjFooUqftkTi+tPZhB0SKhv8hxLIG8AbIjOTV2xjsbJ7myVcg==
X-Received: by 2002:a05:620a:11bc:: with SMTP id c28mr5935999qkk.385.1619210832479; Fri, 23 Apr 2021 13:47:12 -0700 (PDT)
Received: from ?IPv6:2607:fea8:8a0:1397:3400:4119:2f4b:1cce? ([2607:fea8:8a0:1397:3400:4119:2f4b:1cce]) by smtp.gmail.com with ESMTPSA id o125sm5122606qkf.87.2021.04.23.13.47.11 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 23 Apr 2021 13:47:11 -0700 (PDT)
To: "Riad S. Wahby" <rsw@cs.stanford.edu>, Daira Hopwood <daira@jacaranda.org>
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>
From: Rene Struik <rstruik.ext@gmail.com>
Message-ID: <bd249275-09aa-9432-6052-602a832c542f@gmail.com>
Date: Fri, 23 Apr 2021 16:47:09 -0400
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.10.0
MIME-Version: 1.0
In-Reply-To: <20210423193036.szrrpvg7zbtplkor@muon>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: quoted-printable
Content-Language: en-US
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/wVJi47Ox_AkoXg1QK7BWDpZtlDo>
Subject: [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: Fri, 23 Apr 2021 20:47:19 -0000

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.

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

(In the case q = 3 (mod 4), if y is a nonzero element of GF(q) and 
z:=y^{(q-3)/4}, then y is a square in GF(q) only if y*z^2=1. One can 
generalize this to q = 5 (mod 8), q = 9 (mod 16), etc., where the 
general procedure is to compute z:=y^{(q-2^s-1)/2^{s+1}} in GF(q) where 

q:=2^s+1 (mod 2^{s+1}) and where y is a square in GF(q) only if 
(y*z^2)=w, where w^{2^{s-1}}=1. For s large, one gets Daira Hopwood's 

case with higher s, but the principle remains the same (and one could 
refer to a paper for computational tricks or simply declare this out of 
scope).)

Rene

On 2021-04-23 3:30 p.m., Riad S. Wahby wrote:
> Hello Daira,
>
> Thanks for clarifying your feedback.
>
> I remain concerned about mixing implementation detail with high-level
> description. Here I am referring to using divsqrt in place of natural
> field arithmetic operations (sqrt, inversion, etc.) in the body text.
> Describing the algorithm independent of the implementation details is
> a way of specifying the mathematical properties of the algorithm, and
> having this specification explicit in the document has value, from my
> perspective.
>
> But as I said in my prior email, it seems like refactoring Appx. G to
> use divsqrt and adding a few implementations of that function for the
> relevant cases (3 mod 4, 5 mod 8, 9 mod 16, and general, perhaps?) is
> a nice way of cleaning things up. And it seems like the same refactor
> applied to SvdW and Elligator in Appx. G would help, too.
>
> This isn't something I can do in the near term, but I'm very happy to
> spend time on this once I've got some! I'm hopeful that's about three
> weeks from now, but I've been called an optimist before.
>
> Thanks again for the feedback and best regards,
>
> -=rsw
>
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg


-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867