From nobody Sun Feb 13 15:39:11 2022 Return-Path: X-Original-To: crypto-panel@ietfa.amsl.com Delivered-To: crypto-panel@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 4A1F43A0A29 for ; Sun, 13 Feb 2022 15:39:09 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.097 X-Spam-Level: X-Spam-Status: No, score=-2.097 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, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=unavailable 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 lBRwffOxnFxJ for ; Sun, 13 Feb 2022 15:39:04 -0800 (PST) Received: from mail-yb1-xb33.google.com (mail-yb1-xb33.google.com [IPv6:2607:f8b0:4864:20::b33]) (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 4ED7D3A0A30 for ; Sun, 13 Feb 2022 15:39:04 -0800 (PST) Received: by mail-yb1-xb33.google.com with SMTP id p5so41059973ybd.13 for ; Sun, 13 Feb 2022 15:39:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=Jz7qdCmM4KWq4oe0EX1AuUgVVUHzihA5kA2GCOho1Ds=; b=hhELzJYYATGMVOplfJnG2Dnol+EekfLvN9TohbnOySu5uWSwWDoJCs9/D8LIu3trbU cHRPqBNnmtBeUyuxpXYD3Hk4cjH4AOqesdsa12WSTvEfPMYeJYWSCUmwpzwDtcRC/m7z jCx5JPJEyXdbEj1laWi58pUSZHLXRYIdcwMjJQeYQ+2QQuyfAWi3NwlHVW+5fNLugYay tRxw+VhmvPUatyZWqlAEA/CfDMs+BRZFKmEyBAxg1aTzhoptR+Q9SPdIFvD+TkW9IJ7o GZeBy3i+6TRsyNayp6+yE4yzrssYESdua3A1FztHu1nXW6nwTbJ5bL5u2Y7Tm1k+/qLK e36A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=Jz7qdCmM4KWq4oe0EX1AuUgVVUHzihA5kA2GCOho1Ds=; b=thi6RzXGaRwi9h0id9tQj1j8eer0I7Dgzl0OZ8//Xhk/Qzsw2ejNfoX8zZli4XZkTR U8PSEifQZCwX3a5UlmLBosiPj9Y1uXp6H75PKKM+GdhSs7znC4OsIZ0+TKpOMwOz+uP3 ihsSzJSruVrAf9kBZuVTq7uzCLMGsx6LJ0sN6TrrwWYWMaAIkkfS3pxUcM42G3VFEu4P Sj6W4cq2txfy3nFK/aECoB3f48sTa6AFArgtHdDlNr3dtbNQA3UjpXREXxBKhNoXrQPG gFqqI8HrqyMNbwPaz715V1dRL9dVRPiQP9pmL45pEcuN+8PgDiYXJIco1b5M9RT2rpcJ tUoA== X-Gm-Message-State: AOAM533mIogoik58GWcyx3s3eBHkVMYgoAxx9E3Qv4Ohthx02XSqcTUU 95aUrX25x6sy6ZzSwBKyGM0aTXgv0KZ7ZPCT9yM= X-Google-Smtp-Source: ABdhPJy9oGvaXN+xvm+m/yylNsBN2hjwSHBPtYEAOX6ikV7VATDZEqfBq5nPfdQIWcwC0G8dCosd4V7UKrj6EIfGehM= X-Received: by 2002:a25:8186:: with SMTP id p6mr10033541ybk.168.1644795542043; Sun, 13 Feb 2022 15:39:02 -0800 (PST) MIME-Version: 1.0 References: <83FC3CEC-7742-4356-9471-34826B05ACC7@nccgroup.com> In-Reply-To: <83FC3CEC-7742-4356-9471-34826B05ACC7@nccgroup.com> From: Chloe Martindale Date: Sun, 13 Feb 2022 23:38:51 +0000 Message-ID: To: Thomas Pornin Cc: Thomas Pornin , "Stanislav V. Smyshlyaev" , "crypto-panel@irtf.org" , "cfrg-chairs@ietf.org" Content-Type: multipart/alternative; boundary="00000000000003001e05d7eece25" Archived-At: Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review of two erratas opened against RFC 8032 (EdDSA) X-BeenThere: crypto-panel@irtf.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 13 Feb 2022 23:39:10 -0000 --00000000000003001e05d7eece25 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi all, sorry for being a bit slow. I agree with Thomas that both errata are correct. One extra detail: the original formulas are true in more general situations (for example, in the first case, I believe this holds if p =3D 5 mod 8). The proposed errata are correct, as Thomas proved above, but only hold for these specific choices of p; the second one even relies on u and v being constructed from d and y rather than just random field elements. (These are things I just checked experimentally in Sage). They are slightly faster, so maybe worth having, but perhaps with this caveat added in case people erroneously try to use these formulae for computing square roots in other situations. All the best, Chloe On Fri, 28 Jan 2022 at 13:48, Thomas Pornin wrote: > As for efficiency, the gain is slight. The modular exponentiation (with > exponent (p-5)/8) costs at least 250 squarings, and an extra dozen > multiplications. The proposed formula saves two squarings and three > multiplications, i.e. we are talking about an improvement of less than 2%= . > Nothing ground-breaking here. > > Thomas > > =EF=BB=BFOn 2022-01-28, 08:44, "Crypto-panel on behalf of Thomas Pornin" = < > crypto-panel-bounces@irtf.org on behalf of thomas.pornin=3D > 40nccgroup.com@dmarc.ietf.org> wrote: > > OK, the proposed formulas are correct. The original formulas were > correct, too. > > For p =3D 2^255-19: given u and v in the field, then: > v*x^2 =3D v*(u*(u*v)^((p-5)/8))^2 =3D v*(u^2)*(u^((p-5)/4))*(v^((p-5)= /4)) > =3D u * (u^((p-1)/4) * v^((p-1)/4)) > If u/v is a square (and u !=3D 0, v !=3D 0) then u^((p-1)/2) * v^((p-= 1)/2) > =3D 1 (i.e. both u and v are squares, or both u and v are non-squares). > (u^((p-1)/4) * v^((p-1)/4)) is a square root of (u^((p-1)/2) * > v^((p-1)/2)), so its value can only be 1 or -1, therefore v*x^2 =3D u or = -u. > In both cases, this leads to a square root of (u/v) by applying step 3 of > RFC 8032 section 5.1.3: if we got x such that v*x^2 =3D u, then x is a sq= uare > root of u/v; if x is such that v*x^2 =3D -u, then x*i is a square root of > u/v, using i =3D sqrt(-1) (in the RFC, it's given as 2^((p-1)/4), and it = is > indeed a square root of -1). > Thus, the proposed formula, inserted in the RFC text, indeed yields a > square root of u/v if it exists. It does not necessarily yield the same > square root as the original formula, but that does not matter since step = 4 > of the decoding process normalizes the solution using the least significa= nt > bit. > Note that step 3 of section 5.1.3 includes explicitly checking that > v*x^2 =3D u or -u, and if u/v is not a square then there cannot be a x va= lue > that matches that test; thus, the new formula does not incorrectly return= a > value for a non-square u/v. > > For p =3D 2^448 - 2^224 - 1, it is slightly simpler: > v*x^2 =3D v*(u*(u*v)^((p-3)/4))^2 =3D u * (u^((p-1)/2) * v^((p-1)/2) > If u/v is a square then u^((p-1)/2) * v^((p-1)/2) =3D 1 (see above), > hence v*x^2 =3D u and x is necessarily a solution. Again, this is tested > explicitly (step 3 of section 5.2.3) so there is no risk of incorrectly > accepting a non-square. > > As noted above, the normalizing step means that it makes no differenc= e > which of the two square roots you get, at least in the context of RFC 803= 2. > I think it has some slight impact in another context, where the exact > choice of the square root can help simplify a formula, but my memory is a > bit hazy here. This may be related to the fact that, with p =3D 2^448 - 2= ^224 > - 1, exactly one of the two square roots of u/v is itself a square, and t= he > original RFC formula always returns that one, while the proposed formula > may return the square root which is a non-square; again, this does not > matter in the case of RFC 8032. > > Thomas > > From: Crypto-panel on behalf of > "Stanislav V. Smyshlyaev" > Date: Friday, January 28, 2022 at 07:45 > To: Thomas Pornin > Cc: Chloe Martindale , " > crypto-panel@irtf.org" , "cfrg-chairs@ietf.org" < > cfrg-chairs@ietf.org> > Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review of two > erratas opened against RFC 8032 (EdDSA) > > Thank you, Thomas! > > Regards, > Stanislav > > On Fri, 28 Jan 2022 at 15:43, Thomas Pornin 40nccgroup.com@dmarc.ietf.org> wrote: > I will have a look too. This looks weird. > > Thomas > > From: Crypto-panel on behalf of Chloe > Martindale > Date: Friday, January 28, 2022 at 06:24 > To: "Stanislav V. Smyshlyaev" > Cc: "crypto-panel@irtf.org" , " > cfrg-chairs@ietf.org" > Subject: EXTERNAL: Re: [Crypto-panel] Request for review of two > erratas opened against RFC 8032 (EdDSA) > > Hi all, > > I can take a look at this. > > All the best, > Chloe > > On Fri, 28 Jan 2022 at 06:20, Stanislav V. Smyshlyaev < > smyshsv@gmail.com> wrote: > Dear Crypto Review Panel experts, > > We've received a request to have a closer look at two errata opened > against RFC 8032: > https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.r= fc-editor.org%2Ferrata%2Feid5758&data=3D04%7C01%7Cthomas.pornin%40nccgr= oup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f36= 8e%7C0%7C0%7C637789742687386303%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDA= iLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3Dk49Gr2Wu= YIRmJtbPMkL8y8uhUztvAgtHOgZNWo9yOUw%3D&reserved=3D0, > > https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.r= fc-editor.org%2Ferrata%2Feid5759&data=3D04%7C01%7Cthomas.pornin%40nccgr= oup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f36= 8e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDA= iLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DB6QR5Z50= rB0Vz3XkgFEtteBSLLL7iV1qFjiRWu8LyfE%3D&reserved=3D0. > > > Previously these two errata were rejected since no mistakes in the > current text of the draft had been found. At the same time, the two errat= a > might provide more effective ways for square-roots-mod-p. > > We would like to ask a Crypto Panel expert (or two experts) to check > the proposed formulas, i.e., to verify that they are correct and more > effective (always or in a vast majority of cases). > > Any volunteers? > > Best regards, > Stanislav (for chairs) > _______________________________________________ > Crypto-panel mailing list > Crypto-panel@irtf.org > > https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.i= rtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=3D04%7C01%7Cthomas.por= nin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd= 0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoi= MC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata= =3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&reserved=3D0 > _______________________________________________ > Crypto-panel mailing list > Crypto-panel@irtf.org > > https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.i= rtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=3D04%7C01%7Cthomas.por= nin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd= 0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoi= MC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata= =3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&reserved=3D0 > > _______________________________________________ > Crypto-panel mailing list > Crypto-panel@irtf.org > > https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.i= rtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=3D04%7C01%7Cthomas.por= nin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd= 0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoi= MC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata= =3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&reserved=3D0 > > --00000000000003001e05d7eece25 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi all,

sorry for being a bi= t slow. I agree with Thomas that both errata are correct. One extra detail:= the original formulas are true in more general situations (for example, in= the first case, I believe this holds if p =3D 5 mod 8). The proposed errat= a are correct, as Thomas proved above, but only hold for these specific cho= ices of p; the second one even relies on u and v being constructed from d a= nd y rather than just random field elements. (These are things I just check= ed experimentally in Sage). They are slightly faster, so maybe worth having= , but perhaps with this caveat added in case people erroneously try to use = these formulae for computing square roots in other situations.
All the best,
Chloe

On Fri, = 28 Jan 2022 at 13:48, Thomas Pornin <thomas.pornin@nccgroup.com> wrote:
As for efficiency, the gain is slight.= The modular exponentiation (with exponent (p-5)/8) costs at least 250 squa= rings, and an extra dozen multiplications. The proposed formula saves two s= quarings and three multiplications, i.e. we are talking about an improvemen= t of less than 2%. Nothing ground-breaking here.

Thomas

=EF=BB=BFOn 2022-01-28, 08:44, "Crypto-panel on behalf of Thomas Porni= n" <crypto-panel-bounces@irtf.org on behalf of thomas.pornin=3D40nccgroup.com@= dmarc.ietf.org> wrote:

=C2=A0 =C2=A0 OK, the proposed formulas are correct. The original formulas = were correct, too.

=C2=A0 =C2=A0 For p =3D 2^255-19: given u and v in the field, then:
=C2=A0 =C2=A0 v*x^2 =3D v*(u*(u*v)^((p-5)/8))^2 =3D v*(u^2)*(u^((p-5)/4))*(= v^((p-5)/4)) =3D u * (u^((p-1)/4) * v^((p-1)/4))
=C2=A0 =C2=A0 If u/v is a square (and u !=3D 0, v !=3D 0) then u^((p-1)/2) = * v^((p-1)/2) =3D 1 (i.e. both u and v are squares, or both u and v are non= -squares).
=C2=A0 =C2=A0 (u^((p-1)/4) * v^((p-1)/4)) is a square root of (u^((p-1)/2) = * v^((p-1)/2)), so its value can only be 1 or -1, therefore v*x^2 =3D u or = -u. In both cases, this leads to a square root of (u/v) by applying step 3 = of RFC 8032 section 5.1.3: if we got x such that v*x^2 =3D u, then x is a s= quare root of u/v; if x is such that v*x^2 =3D -u, then x*i is a square roo= t of u/v, using i =3D sqrt(-1) (in the RFC, it's given as 2^((p-1)/4), = and it is indeed a square root of -1).
=C2=A0 =C2=A0 Thus, the proposed formula, inserted in the RFC text, indeed = yields a square root of u/v if it exists. It does not necessarily yield the= same square root as the original formula, but that does not matter since s= tep 4 of the decoding process normalizes the solution using the least signi= ficant bit.
=C2=A0 =C2=A0 Note that step 3 of section 5.1.3 includes explicitly checkin= g that v*x^2 =3D u or -u, and if u/v is not a square then there cannot be a= x value that matches that test; thus, the new formula does not incorrectly= return a value for a non-square u/v.

=C2=A0 =C2=A0 For p =3D 2^448 - 2^224 - 1, it is slightly simpler:
=C2=A0 =C2=A0 v*x^2 =3D v*(u*(u*v)^((p-3)/4))^2 =3D u * (u^((p-1)/2) * v^((= p-1)/2)
=C2=A0 =C2=A0 If u/v is a square then u^((p-1)/2) * v^((p-1)/2) =3D 1 (see = above), hence v*x^2 =3D u and x is necessarily a solution. Again, this is t= ested explicitly (step 3 of section 5.2.3) so there is no risk of incorrect= ly accepting a non-square.

=C2=A0 =C2=A0 As noted above, the normalizing step means that it makes no d= ifference which of the two square roots you get, at least in the context of= RFC 8032. I think it has some slight impact in another context, where the = exact choice of the square root can help simplify a formula, but my memory = is a bit hazy here. This may be related to the fact that, with p =3D 2^448 = - 2^224 - 1, exactly one of the two square roots of u/v is itself a square,= and the original RFC formula always returns that one, while the proposed f= ormula may return the square root which is a non-square; again, this does n= ot matter in the case of RFC 8032.

=C2=A0 =C2=A0 Thomas

=C2=A0 =C2=A0 From: Crypto-panel <crypto-panel-bounces@irtf.org> on behal= f of "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
=C2=A0 =C2=A0 Date: Friday, January 28, 2022 at 07:45
=C2=A0 =C2=A0 To: Thomas Pornin <thomas.pornin=3D40nccgroup.com@dmarc.ietf.org>
=C2=A0 =C2=A0 Cc: Chloe Martindale <chloemartindale@gmail.com>, "crypto-panel@irtf.org" <cry= pto-panel@irtf.org>, "cfrg-chairs@ietf.org" <cfrg-chairs@ietf.org>
=C2=A0 =C2=A0 Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review = of two erratas opened against RFC 8032 (EdDSA)

=C2=A0 =C2=A0 Thank you, Thomas!

=C2=A0 =C2=A0 Regards,
=C2=A0 =C2=A0 Stanislav

=C2=A0 =C2=A0 On Fri, 28 Jan 2022 at 15:43, Thomas Pornin <thomas.pornin= =3D40ncc= group.com@dmarc.ietf.org> wrote:
=C2=A0 =C2=A0 I will have a look too. This looks weird.

=C2=A0 =C2=A0 Thomas

=C2=A0 =C2=A0 From: Crypto-panel <crypto-panel-bounces@irtf.org> on behal= f of Chloe Martindale <chloemartindale@gmail.com>
=C2=A0 =C2=A0 Date: Friday, January 28, 2022 at 06:24
=C2=A0 =C2=A0 To: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
=C2=A0 =C2=A0 Cc: "crypto-panel@irtf.org" <crypto-panel@irtf.org>, "cfrg-chairs@ietf.org&qu= ot; <cfrg-chai= rs@ietf.org>
=C2=A0 =C2=A0 Subject: EXTERNAL: Re: [Crypto-panel] Request for review of t= wo erratas opened against RFC 8032 (EdDSA)

=C2=A0 =C2=A0 Hi all,

=C2=A0 =C2=A0 I can take a look at this.

=C2=A0 =C2=A0 All the best,
=C2=A0 =C2=A0 Chloe

=C2=A0 =C2=A0 On Fri, 28 Jan 2022 at 06:20, Stanislav V. Smyshlyaev <smyshsv@gmail.com&g= t; wrote:
=C2=A0 =C2=A0 Dear Crypto Review Panel experts,

=C2=A0 =C2=A0 We've received a request to have a closer look at two err= ata opened against RFC 8032: https:= //gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.rfc-edito= r.org%2Ferrata%2Feid5758&amp;data=3D04%7C01%7Cthomas.pornin%40nccgroup.= com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7= C0%7C0%7C637789742687386303%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJ= QIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=3Dk49Gr2Wu= YIRmJtbPMkL8y8uhUztvAgtHOgZNWo9yOUw%3D&amp;reserved=3D0, https://gbr01.safelinks.protection.outlook.co= m/?url=3Dhttps%3A%2F%2Fwww.rfc-editor.org%2Ferrata%2Feid5759&amp;data= =3D04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416a= f%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown= %7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6= Mn0%3D%7C3000&amp;sdata=3DB6QR5Z50rB0Vz3XkgFEtteBSLLL7iV1qFjiRWu8LyfE%3= D&amp;reserved=3D0.

=C2=A0 =C2=A0 Previously these two errata were rejected since no mistakes i= n the current text of the draft had been found. At the same time, the two e= rrata might provide more effective ways for square-roots-mod-p.

=C2=A0 =C2=A0 We would like to ask a Crypto Panel expert (or two experts) t= o check the proposed formulas, i.e., to verify that they are correct and mo= re effective (always or in a vast majority of cases).

=C2=A0 =C2=A0 Any volunteers?

=C2=A0 =C2=A0 Best regards,
=C2=A0 =C2=A0 Stanislav (for chairs)
=C2=A0 =C2=A0 _______________________________________________
=C2=A0 =C2=A0 Crypto-panel mailing list
=C2=A0 =C2=A0 Cr= ypto-panel@irtf.org
=C2=A0 =C2=A0 https://gb= r01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.irtf.org%2Fma= ilman%2Flistinfo%2Fcrypto-panel&amp;data=3D04%7C01%7Cthomas.pornin%40nc= cgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62= f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAw= MDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=3DG= EKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved=3D0
=C2=A0 =C2=A0 _______________________________________________
=C2=A0 =C2=A0 Crypto-panel mailing list
=C2=A0 =C2=A0 Cr= ypto-panel@irtf.org
=C2=A0 =C2=A0 https://gb= r01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.irtf.org%2Fma= ilman%2Flistinfo%2Fcrypto-panel&amp;data=3D04%7C01%7Cthomas.pornin%40nc= cgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62= f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAw= MDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=3DG= EKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved=3D0

=C2=A0 =C2=A0 _______________________________________________
=C2=A0 =C2=A0 Crypto-panel mailing list
=C2=A0 =C2=A0 Cr= ypto-panel@irtf.org
=C2=A0 =C2=A0 https://gb= r01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.irtf.org%2Fma= ilman%2Flistinfo%2Fcrypto-panel&amp;data=3D04%7C01%7Cthomas.pornin%40nc= cgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62= f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAw= MDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=3DG= EKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved=3D0

--00000000000003001e05d7eece25-- From nobody Sun Feb 13 21:40:49 2022 Return-Path: X-Original-To: crypto-panel@ietfa.amsl.com Delivered-To: crypto-panel@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 932E53A07AC for ; Sun, 13 Feb 2022 21:40:46 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.097 X-Spam-Level: X-Spam-Status: No, score=-2.097 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, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=unavailable 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 xygIGp84-Fyq for ; Sun, 13 Feb 2022 21:40:41 -0800 (PST) Received: from mail-ed1-x532.google.com (mail-ed1-x532.google.com [IPv6:2a00:1450:4864:20::532]) (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 1D3DD3A07B1 for ; Sun, 13 Feb 2022 21:40:41 -0800 (PST) Received: by mail-ed1-x532.google.com with SMTP id da4so25264237edb.4 for ; Sun, 13 Feb 2022 21:40:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=kc9XMR6MU1ZA8MxGLeb5ZWjGtLUMIxvDsSPxZVkGOlw=; b=l8g2/l1o0dHbWLmk/NeUWugsUGHdCrsrJGlopAt18aeAZNdAANGAc2O1rIBXQ/ZT4D lo+o96DvSJOUIJqSUq2GlvKMQrF5dxFsdKDTJl5u4C2ymufKfR6fU1oN91J8vrFnQtmo dRAtZFg3eN0C3KlGWgVwXQu6BRZcABF+ZErkobtj7bqebBRgioGDUqWk1uObL9nk0Ohi lJY6T2YGBnwq8jlz6WW9MC8viwnqqKngb7zSKANKZOPrh74vdaTTdntk8AM5UCPYOesg vZRlUcHddIWGbbYFr8bNo0+DNVeooxs/CD2vPbkyc2Cxc/Gvqwo/V4K0q+X8uJmr7cEr vrbQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=kc9XMR6MU1ZA8MxGLeb5ZWjGtLUMIxvDsSPxZVkGOlw=; b=GTujn9SRXvP9gG7nM6z9rra+dMScatgVDcphU486aAlokA64WlJ2ksF2TyObpjZ/U0 zWLva7RPv6nsasmjcNM1sG5mVdEGEZpJyVXczjThai48gc/KaoTjYJY9a+OhaRXsOnN7 mdUviFI87zf1qh8+isWkgN+DlbFG2mCFkAraQCfA5w8CDtJjRctfjhfNjOfQ0R4CUvMK taxrBxxbTHn7436hnEYcG+16YofNoAHKOqEgL1+sqciPVwXEJbpp6pE9YRsAFpxGJI+7 b9oRFI9wJyCLQMUnfsr+r/gTr2EouNErwHkFgYsrKGdwI8u4G+zg1LZ3ZUlwWz/NEOXv QCpw== X-Gm-Message-State: AOAM532cZBQ8/ejxO2dKoWCD9Tfyj2lVxUfeKIyhBd79sossE7+Ew2PB eyaTT1/hld3eFtRpVD4U0VmKi7iHp/2n3TwyhgY= X-Google-Smtp-Source: ABdhPJwu28cRnanz6CcgSl52+8YohSvohOf9KbTMiWUdBuFH8kLdnowKyE6NkC825/MWR41UsRIrxHV4xz2ECPOjimU= X-Received: by 2002:a05:6402:2754:: with SMTP id z20mr13579203edd.235.1644817238417; Sun, 13 Feb 2022 21:40:38 -0800 (PST) MIME-Version: 1.0 References: <83FC3CEC-7742-4356-9471-34826B05ACC7@nccgroup.com> In-Reply-To: From: "Stanislav V. Smyshlyaev" Date: Mon, 14 Feb 2022 08:41:48 +0300 Message-ID: To: Chloe Martindale Cc: Thomas Pornin , Thomas Pornin , "crypto-panel@irtf.org" , "cfrg-chairs@ietf.org" Content-Type: multipart/alternative; boundary="0000000000003763e705d7f3dbc9" Archived-At: Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review of two erratas opened against RFC 8032 (EdDSA) X-BeenThere: crypto-panel@irtf.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 14 Feb 2022 05:40:47 -0000 --0000000000003763e705d7f3dbc9 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Dear Chloe, Thank you so much for your work! >> but only hold for these specific choices of p Do I understand correctly that for this specific RFC the formulas are always correct (i.e., the text of errata can be used in the updated version of the RFC without additional remarks), but are not always correct in other cases? Regards, Stanislav On Mon, 14 Feb 2022 at 02:39, Chloe Martindale wrote: > Hi all, > > sorry for being a bit slow. I agree with Thomas that both errata are > correct. One extra detail: the original formulas are true in more general > situations (for example, in the first case, I believe this holds if p =3D= 5 > mod 8). The proposed errata are correct, as Thomas proved above, but only > hold for these specific choices of p; the second one even relies on u and= v > being constructed from d and y rather than just random field elements. > (These are things I just checked experimentally in Sage). They are slight= ly > faster, so maybe worth having, but perhaps with this caveat added in case > people erroneously try to use these formulae for computing square roots i= n > other situations. > > All the best, > Chloe > > > On Fri, 28 Jan 2022 at 13:48, Thomas Pornin > wrote: > >> As for efficiency, the gain is slight. The modular exponentiation (with >> exponent (p-5)/8) costs at least 250 squarings, and an extra dozen >> multiplications. The proposed formula saves two squarings and three >> multiplications, i.e. we are talking about an improvement of less than 2= %. >> Nothing ground-breaking here. >> >> Thomas >> >> =EF=BB=BFOn 2022-01-28, 08:44, "Crypto-panel on behalf of Thomas Pornin"= < >> crypto-panel-bounces@irtf.org on behalf of thomas.pornin=3D >> 40nccgroup.com@dmarc.ietf.org> wrote: >> >> OK, the proposed formulas are correct. The original formulas were >> correct, too. >> >> For p =3D 2^255-19: given u and v in the field, then: >> v*x^2 =3D v*(u*(u*v)^((p-5)/8))^2 =3D v*(u^2)*(u^((p-5)/4))*(v^((p-5= )/4)) >> =3D u * (u^((p-1)/4) * v^((p-1)/4)) >> If u/v is a square (and u !=3D 0, v !=3D 0) then u^((p-1)/2) * >> v^((p-1)/2) =3D 1 (i.e. both u and v are squares, or both u and v are >> non-squares). >> (u^((p-1)/4) * v^((p-1)/4)) is a square root of (u^((p-1)/2) * >> v^((p-1)/2)), so its value can only be 1 or -1, therefore v*x^2 =3D u or= -u. >> In both cases, this leads to a square root of (u/v) by applying step 3 o= f >> RFC 8032 section 5.1.3: if we got x such that v*x^2 =3D u, then x is a s= quare >> root of u/v; if x is such that v*x^2 =3D -u, then x*i is a square root o= f >> u/v, using i =3D sqrt(-1) (in the RFC, it's given as 2^((p-1)/4), and it= is >> indeed a square root of -1). >> Thus, the proposed formula, inserted in the RFC text, indeed yields = a >> square root of u/v if it exists. It does not necessarily yield the same >> square root as the original formula, but that does not matter since step= 4 >> of the decoding process normalizes the solution using the least signific= ant >> bit. >> Note that step 3 of section 5.1.3 includes explicitly checking that >> v*x^2 =3D u or -u, and if u/v is not a square then there cannot be a x v= alue >> that matches that test; thus, the new formula does not incorrectly retur= n a >> value for a non-square u/v. >> >> For p =3D 2^448 - 2^224 - 1, it is slightly simpler: >> v*x^2 =3D v*(u*(u*v)^((p-3)/4))^2 =3D u * (u^((p-1)/2) * v^((p-1)/2) >> If u/v is a square then u^((p-1)/2) * v^((p-1)/2) =3D 1 (see above), >> hence v*x^2 =3D u and x is necessarily a solution. Again, this is tested >> explicitly (step 3 of section 5.2.3) so there is no risk of incorrectly >> accepting a non-square. >> >> As noted above, the normalizing step means that it makes no >> difference which of the two square roots you get, at least in the contex= t >> of RFC 8032. I think it has some slight impact in another context, where >> the exact choice of the square root can help simplify a formula, but my >> memory is a bit hazy here. This may be related to the fact that, with p = =3D >> 2^448 - 2^224 - 1, exactly one of the two square roots of u/v is itself = a >> square, and the original RFC formula always returns that one, while the >> proposed formula may return the square root which is a non-square; again= , >> this does not matter in the case of RFC 8032. >> >> Thomas >> >> From: Crypto-panel on behalf of >> "Stanislav V. Smyshlyaev" >> Date: Friday, January 28, 2022 at 07:45 >> To: Thomas Pornin >> Cc: Chloe Martindale , " >> crypto-panel@irtf.org" , "cfrg-chairs@ietf.org" < >> cfrg-chairs@ietf.org> >> Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review of two >> erratas opened against RFC 8032 (EdDSA) >> >> Thank you, Thomas! >> >> Regards, >> Stanislav >> >> On Fri, 28 Jan 2022 at 15:43, Thomas Pornin > 40nccgroup.com@dmarc.ietf.org> wrote: >> I will have a look too. This looks weird. >> >> Thomas >> >> From: Crypto-panel on behalf of >> Chloe Martindale >> Date: Friday, January 28, 2022 at 06:24 >> To: "Stanislav V. Smyshlyaev" >> Cc: "crypto-panel@irtf.org" , " >> cfrg-chairs@ietf.org" >> Subject: EXTERNAL: Re: [Crypto-panel] Request for review of two >> erratas opened against RFC 8032 (EdDSA) >> >> Hi all, >> >> I can take a look at this. >> >> All the best, >> Chloe >> >> On Fri, 28 Jan 2022 at 06:20, Stanislav V. Smyshlyaev < >> smyshsv@gmail.com> wrote: >> Dear Crypto Review Panel experts, >> >> We've received a request to have a closer look at two errata opened >> against RFC 8032: >> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.= rfc-editor.org%2Ferrata%2Feid5758&data=3D04%7C01%7Cthomas.pornin%40nccg= roup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f3= 68e%7C0%7C0%7C637789742687386303%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMD= AiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3Dk49Gr2W= uYIRmJtbPMkL8y8uhUztvAgtHOgZNWo9yOUw%3D&reserved=3D0, >> >> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.= rfc-editor.org%2Ferrata%2Feid5759&data=3D04%7C01%7Cthomas.pornin%40nccg= roup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f3= 68e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMD= AiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DB6QR5Z5= 0rB0Vz3XkgFEtteBSLLL7iV1qFjiRWu8LyfE%3D&reserved=3D0. >> >> >> Previously these two errata were rejected since no mistakes in the >> current text of the draft had been found. At the same time, the two erra= ta >> might provide more effective ways for square-roots-mod-p. >> >> We would like to ask a Crypto Panel expert (or two experts) to check >> the proposed formulas, i.e., to verify that they are correct and more >> effective (always or in a vast majority of cases). >> >> Any volunteers? >> >> Best regards, >> Stanislav (for chairs) >> _______________________________________________ >> Crypto-panel mailing list >> Crypto-panel@irtf.org >> >> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.= irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=3D04%7C01%7Cthomas.po= rnin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68b= d0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjo= iMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdat= a=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&reserved=3D0 >> _______________________________________________ >> Crypto-panel mailing list >> Crypto-panel@irtf.org >> >> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.= irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=3D04%7C01%7Cthomas.po= rnin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68b= d0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjo= iMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdat= a=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&reserved=3D0 >> >> _______________________________________________ >> Crypto-panel mailing list >> Crypto-panel@irtf.org >> >> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.= irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=3D04%7C01%7Cthomas.po= rnin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68b= d0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjo= iMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdat= a=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&reserved=3D0 >> >> --0000000000003763e705d7f3dbc9 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Dear Chloe,

Thank you so much for your = work!

>> but only hold for these specific ch= oices of p
Do I understand correctly that for this specific RFC t= he formulas=C2=A0are always correct (i.e., the text of errata can be used i= n the updated=C2=A0version of the RFC without additional remarks), but are = not always correct in other cases?

Regards,
<= div>Stanislav


On Mon, 14 Feb 2022 at 02:39, Chloe Marti= ndale <chloemartindale@gmai= l.com> wrote:
Hi all,

sorry for being= a bit slow. I agree with Thomas that both errata are correct. One extra de= tail: the original formulas are true in more general situations (for exampl= e, in the first case, I believe this holds if p =3D 5 mod 8). The proposed = errata are correct, as Thomas proved above, but only hold for these specifi= c choices of p; the second one even relies on u and v being constructed fro= m d and y rather than just random field elements. (These are things I just = checked experimentally in Sage). They are slightly faster, so maybe worth h= aving, but perhaps with this caveat added in case people erroneously try to= use these formulae for computing square roots in other situations.

All the best,
Chloe


On = Fri, 28 Jan 2022 at 13:48, Thomas Pornin <thomas.pornin@nccgroup.com> wrote:=
As for efficien= cy, the gain is slight. The modular exponentiation (with exponent (p-5)/8) = costs at least 250 squarings, and an extra dozen multiplications. The propo= sed formula saves two squarings and three multiplications, i.e. we are talk= ing about an improvement of less than 2%. Nothing ground-breaking here.

Thomas

=EF=BB=BFOn 2022-01-28, 08:44, "Crypto-panel on behalf of Thomas Porni= n" <crypto-panel-bounces@irtf.org on behalf of thomas.pornin=3D40nccgroup.com@= dmarc.ietf.org> wrote:

=C2=A0 =C2=A0 OK, the proposed formulas are correct. The original formulas = were correct, too.

=C2=A0 =C2=A0 For p =3D 2^255-19: given u and v in the field, then:
=C2=A0 =C2=A0 v*x^2 =3D v*(u*(u*v)^((p-5)/8))^2 =3D v*(u^2)*(u^((p-5)/4))*(= v^((p-5)/4)) =3D u * (u^((p-1)/4) * v^((p-1)/4))
=C2=A0 =C2=A0 If u/v is a square (and u !=3D 0, v !=3D 0) then u^((p-1)/2) = * v^((p-1)/2) =3D 1 (i.e. both u and v are squares, or both u and v are non= -squares).
=C2=A0 =C2=A0 (u^((p-1)/4) * v^((p-1)/4)) is a square root of (u^((p-1)/2) = * v^((p-1)/2)), so its value can only be 1 or -1, therefore v*x^2 =3D u or = -u. In both cases, this leads to a square root of (u/v) by applying step 3 = of RFC 8032 section 5.1.3: if we got x such that v*x^2 =3D u, then x is a s= quare root of u/v; if x is such that v*x^2 =3D -u, then x*i is a square roo= t of u/v, using i =3D sqrt(-1) (in the RFC, it's given as 2^((p-1)/4), = and it is indeed a square root of -1).
=C2=A0 =C2=A0 Thus, the proposed formula, inserted in the RFC text, indeed = yields a square root of u/v if it exists. It does not necessarily yield the= same square root as the original formula, but that does not matter since s= tep 4 of the decoding process normalizes the solution using the least signi= ficant bit.
=C2=A0 =C2=A0 Note that step 3 of section 5.1.3 includes explicitly checkin= g that v*x^2 =3D u or -u, and if u/v is not a square then there cannot be a= x value that matches that test; thus, the new formula does not incorrectly= return a value for a non-square u/v.

=C2=A0 =C2=A0 For p =3D 2^448 - 2^224 - 1, it is slightly simpler:
=C2=A0 =C2=A0 v*x^2 =3D v*(u*(u*v)^((p-3)/4))^2 =3D u * (u^((p-1)/2) * v^((= p-1)/2)
=C2=A0 =C2=A0 If u/v is a square then u^((p-1)/2) * v^((p-1)/2) =3D 1 (see = above), hence v*x^2 =3D u and x is necessarily a solution. Again, this is t= ested explicitly (step 3 of section 5.2.3) so there is no risk of incorrect= ly accepting a non-square.

=C2=A0 =C2=A0 As noted above, the normalizing step means that it makes no d= ifference which of the two square roots you get, at least in the context of= RFC 8032. I think it has some slight impact in another context, where the = exact choice of the square root can help simplify a formula, but my memory = is a bit hazy here. This may be related to the fact that, with p =3D 2^448 = - 2^224 - 1, exactly one of the two square roots of u/v is itself a square,= and the original RFC formula always returns that one, while the proposed f= ormula may return the square root which is a non-square; again, this does n= ot matter in the case of RFC 8032.

=C2=A0 =C2=A0 Thomas

=C2=A0 =C2=A0 From: Crypto-panel <crypto-panel-bounces@irtf.org> on behal= f of "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
=C2=A0 =C2=A0 Date: Friday, January 28, 2022 at 07:45
=C2=A0 =C2=A0 To: Thomas Pornin <thomas.pornin=3D40nccgroup.com@dmarc.ietf.org>
=C2=A0 =C2=A0 Cc: Chloe Martindale <chloemartindale@gmail.com>, "crypto-panel@irtf.org" <cry= pto-panel@irtf.org>, "cfrg-chairs@ietf.org" <cfrg-chairs@ietf.org>
=C2=A0 =C2=A0 Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review = of two erratas opened against RFC 8032 (EdDSA)

=C2=A0 =C2=A0 Thank you, Thomas!

=C2=A0 =C2=A0 Regards,
=C2=A0 =C2=A0 Stanislav

=C2=A0 =C2=A0 On Fri, 28 Jan 2022 at 15:43, Thomas Pornin <thomas.pornin= =3D40ncc= group.com@dmarc.ietf.org> wrote:
=C2=A0 =C2=A0 I will have a look too. This looks weird.

=C2=A0 =C2=A0 Thomas

=C2=A0 =C2=A0 From: Crypto-panel <crypto-panel-bounces@irtf.org> on behal= f of Chloe Martindale <chloemartindale@gmail.com>
=C2=A0 =C2=A0 Date: Friday, January 28, 2022 at 06:24
=C2=A0 =C2=A0 To: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
=C2=A0 =C2=A0 Cc: "crypto-panel@irtf.org" <crypto-panel@irtf.org>, "cfrg-chairs@ietf.org&qu= ot; <cfrg-chai= rs@ietf.org>
=C2=A0 =C2=A0 Subject: EXTERNAL: Re: [Crypto-panel] Request for review of t= wo erratas opened against RFC 8032 (EdDSA)

=C2=A0 =C2=A0 Hi all,

=C2=A0 =C2=A0 I can take a look at this.

=C2=A0 =C2=A0 All the best,
=C2=A0 =C2=A0 Chloe

=C2=A0 =C2=A0 On Fri, 28 Jan 2022 at 06:20, Stanislav V. Smyshlyaev <smyshsv@gmail.com&g= t; wrote:
=C2=A0 =C2=A0 Dear Crypto Review Panel experts,

=C2=A0 =C2=A0 We've received a request to have a closer look at two err= ata opened against RFC 8032: https:= //gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.rfc-edito= r.org%2Ferrata%2Feid5758&amp;data=3D04%7C01%7Cthomas.pornin%40nccgroup.= com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7= C0%7C0%7C637789742687386303%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJ= QIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=3Dk49Gr2Wu= YIRmJtbPMkL8y8uhUztvAgtHOgZNWo9yOUw%3D&amp;reserved=3D0, https://gbr01.safelinks.protection.outlook.co= m/?url=3Dhttps%3A%2F%2Fwww.rfc-editor.org%2Ferrata%2Feid5759&amp;data= =3D04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416a= f%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown= %7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6= Mn0%3D%7C3000&amp;sdata=3DB6QR5Z50rB0Vz3XkgFEtteBSLLL7iV1qFjiRWu8LyfE%3= D&amp;reserved=3D0.

=C2=A0 =C2=A0 Previously these two errata were rejected since no mistakes i= n the current text of the draft had been found. At the same time, the two e= rrata might provide more effective ways for square-roots-mod-p.

=C2=A0 =C2=A0 We would like to ask a Crypto Panel expert (or two experts) t= o check the proposed formulas, i.e., to verify that they are correct and mo= re effective (always or in a vast majority of cases).

=C2=A0 =C2=A0 Any volunteers?

=C2=A0 =C2=A0 Best regards,
=C2=A0 =C2=A0 Stanislav (for chairs)
=C2=A0 =C2=A0 _______________________________________________
=C2=A0 =C2=A0 Crypto-panel mailing list
=C2=A0 =C2=A0 Cr= ypto-panel@irtf.org
=C2=A0 =C2=A0 https://gb= r01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.irtf.org%2Fma= ilman%2Flistinfo%2Fcrypto-panel&amp;data=3D04%7C01%7Cthomas.pornin%40nc= cgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62= f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAw= MDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=3DG= EKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved=3D0
=C2=A0 =C2=A0 _______________________________________________
=C2=A0 =C2=A0 Crypto-panel mailing list
=C2=A0 =C2=A0 Cr= ypto-panel@irtf.org
=C2=A0 =C2=A0 https://gb= r01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.irtf.org%2Fma= ilman%2Flistinfo%2Fcrypto-panel&amp;data=3D04%7C01%7Cthomas.pornin%40nc= cgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62= f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAw= MDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=3DG= EKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved=3D0

=C2=A0 =C2=A0 _______________________________________________
=C2=A0 =C2=A0 Crypto-panel mailing list
=C2=A0 =C2=A0 Cr= ypto-panel@irtf.org
=C2=A0 =C2=A0 https://gb= r01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.irtf.org%2Fma= ilman%2Flistinfo%2Fcrypto-panel&amp;data=3D04%7C01%7Cthomas.pornin%40nc= cgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62= f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAw= MDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=3DG= EKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved=3D0

--0000000000003763e705d7f3dbc9-- From nobody Mon Feb 14 02:02:59 2022 Return-Path: X-Original-To: crypto-panel@ietfa.amsl.com Delivered-To: crypto-panel@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 4C5653A0C36 for ; Mon, 14 Feb 2022 02:02:56 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -7.098 X-Spam-Level: X-Spam-Status: No, score=-7.098 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, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=unavailable 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 liU7UV_8-aPG for ; Mon, 14 Feb 2022 02:02:51 -0800 (PST) Received: from mail-yb1-xb36.google.com (mail-yb1-xb36.google.com [IPv6:2607:f8b0:4864:20::b36]) (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 8F9AE3A0CA8 for ; Mon, 14 Feb 2022 02:02:50 -0800 (PST) Received: by mail-yb1-xb36.google.com with SMTP id bt13so44521389ybb.2 for ; Mon, 14 Feb 2022 02:02:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=bQBlnVJRnGcafqcIotvK0GpV94O0vvIzY2vmvil5gGg=; b=NoQu31q/hYVeXLFzEgAGs7kuvS7xXoyie3YWCCqKI7bW9DrSTMX977oZuEhHe+yt5/ 1wMQfF3c/pwXj7XwOSGN0nvrqC99gk+dXhnMud62s+MRpeAY33ystxNXZR098gljmGLM D6dsH1HXsqVEbi+uGcF1PXUkuSsxnEbAMSMKpecgyD4Exw4+c4Ve0EVygwks7fdYs/ic EhqLkfPPSGWr9KvQX05CufDbfUE3azCde4Rj2OU4ZiH6PObHQmZ36X38WLiceLEH0zM9 v/32c1CqSly9u4v92wwJQjVkC+y2j9R/vVduqIMiPIJ71RzltcQVVlp8OL1kQ9bAECkE nQPg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=bQBlnVJRnGcafqcIotvK0GpV94O0vvIzY2vmvil5gGg=; b=HdBr1bhFfoOYwom4EQbzbVWXyUoL4VImJ5c83aMvjAOKEBdNXceG107MNjaEruerWL Iu2QvfkMkWfQK1qqgK52TsLy2a+pSQxaOWo74n5YNppZBNcP3M46xGOnf1WPE+Yc918/ uaVrtCkqvbGgZVqYGx5wbOodLMxKByJ8hh4A2i2Hc/KKrHEvaJ2chH4W6huYOP0uFfpd xK0Zg1agM6NYAjcJ6vGUdnNxKUe+q6fpWvuP1zx11UIUsX8wGDKH7yI4T9KzlDyYN2E/ rFdkD/vzFabKcJmNRqsxzP5egD+sWxDDeMpSH/u+joOM6PERLsamYZ11GhZ1t9BEChou uq7A== X-Gm-Message-State: AOAM531/VdHbBU1z+7PGFHdj5hhFdMoxSld8kV9Zb1G1iNim8qlBXOzW VXF0wVcOEvkIV3JroXjflQ4MGhyag8k0JFGTXPY= X-Google-Smtp-Source: ABdhPJxrCw9Xil4sni4nf23G4L646z0dk4G8MC5D9XAPo2jhTsYgk0jNAC3pWRczZ7Os94O5+M9YqaLBvg3bYTALgFU= X-Received: by 2002:a81:e90b:: with SMTP id d11mr12856523ywm.409.1644832967694; Mon, 14 Feb 2022 02:02:47 -0800 (PST) MIME-Version: 1.0 References: <83FC3CEC-7742-4356-9471-34826B05ACC7@nccgroup.com> In-Reply-To: From: Chloe Martindale Date: Mon, 14 Feb 2022 10:02:36 +0000 Message-ID: To: "Stanislav V. Smyshlyaev" Cc: Thomas Pornin , Thomas Pornin , crypto-panel@irtf.org, cfrg-chairs@ietf.org Content-Type: multipart/alternative; boundary="000000000000c11e2f05d7f784ef" Archived-At: Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review of two erratas opened against RFC 8032 (EdDSA) X-BeenThere: crypto-panel@irtf.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 14 Feb 2022 10:02:57 -0000 --000000000000c11e2f05d7f784ef Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Dear Stanislav, Yes they are correct. No remarks are needed for correctness, but for completeness I would suggest adding a citation/justification and a comment that these speed ups are possible only in these specific cases. If you prefer to keep it simple and just accept based on correctness that's also fine with me. All the best, Chloe On Mon, 14 Feb 2022, 05:40 Stanislav V. Smyshlyaev, wrote: > Dear Chloe, > > Thank you so much for your work! > > >> but only hold for these specific choices of p > Do I understand correctly that for this specific RFC the formulas are > always correct (i.e., the text of errata can be used in the updated versi= on > of the RFC without additional remarks), but are not always correct in oth= er > cases? > > Regards, > Stanislav > > > On Mon, 14 Feb 2022 at 02:39, Chloe Martindale > wrote: > >> Hi all, >> >> sorry for being a bit slow. I agree with Thomas that both errata are >> correct. One extra detail: the original formulas are true in more genera= l >> situations (for example, in the first case, I believe this holds if p = =3D 5 >> mod 8). The proposed errata are correct, as Thomas proved above, but onl= y >> hold for these specific choices of p; the second one even relies on u an= d v >> being constructed from d and y rather than just random field elements. >> (These are things I just checked experimentally in Sage). They are sligh= tly >> faster, so maybe worth having, but perhaps with this caveat added in cas= e >> people erroneously try to use these formulae for computing square roots = in >> other situations. >> >> All the best, >> Chloe >> >> >> On Fri, 28 Jan 2022 at 13:48, Thomas Pornin >> wrote: >> >>> As for efficiency, the gain is slight. The modular exponentiation (with >>> exponent (p-5)/8) costs at least 250 squarings, and an extra dozen >>> multiplications. The proposed formula saves two squarings and three >>> multiplications, i.e. we are talking about an improvement of less than = 2%. >>> Nothing ground-breaking here. >>> >>> Thomas >>> >>> =EF=BB=BFOn 2022-01-28, 08:44, "Crypto-panel on behalf of Thomas Pornin= " < >>> crypto-panel-bounces@irtf.org on behalf of thomas.pornin=3D >>> 40nccgroup.com@dmarc.ietf.org> wrote: >>> >>> OK, the proposed formulas are correct. The original formulas were >>> correct, too. >>> >>> For p =3D 2^255-19: given u and v in the field, then: >>> v*x^2 =3D v*(u*(u*v)^((p-5)/8))^2 =3D >>> v*(u^2)*(u^((p-5)/4))*(v^((p-5)/4)) =3D u * (u^((p-1)/4) * v^((p-1)/4)) >>> If u/v is a square (and u !=3D 0, v !=3D 0) then u^((p-1)/2) * >>> v^((p-1)/2) =3D 1 (i.e. both u and v are squares, or both u and v are >>> non-squares). >>> (u^((p-1)/4) * v^((p-1)/4)) is a square root of (u^((p-1)/2) * >>> v^((p-1)/2)), so its value can only be 1 or -1, therefore v*x^2 =3D u o= r -u. >>> In both cases, this leads to a square root of (u/v) by applying step 3 = of >>> RFC 8032 section 5.1.3: if we got x such that v*x^2 =3D u, then x is a = square >>> root of u/v; if x is such that v*x^2 =3D -u, then x*i is a square root = of >>> u/v, using i =3D sqrt(-1) (in the RFC, it's given as 2^((p-1)/4), and i= t is >>> indeed a square root of -1). >>> Thus, the proposed formula, inserted in the RFC text, indeed yields >>> a square root of u/v if it exists. It does not necessarily yield the sa= me >>> square root as the original formula, but that does not matter since ste= p 4 >>> of the decoding process normalizes the solution using the least signifi= cant >>> bit. >>> Note that step 3 of section 5.1.3 includes explicitly checking that >>> v*x^2 =3D u or -u, and if u/v is not a square then there cannot be a x = value >>> that matches that test; thus, the new formula does not incorrectly retu= rn a >>> value for a non-square u/v. >>> >>> For p =3D 2^448 - 2^224 - 1, it is slightly simpler: >>> v*x^2 =3D v*(u*(u*v)^((p-3)/4))^2 =3D u * (u^((p-1)/2) * v^((p-1)/2= ) >>> If u/v is a square then u^((p-1)/2) * v^((p-1)/2) =3D 1 (see above)= , >>> hence v*x^2 =3D u and x is necessarily a solution. Again, this is teste= d >>> explicitly (step 3 of section 5.2.3) so there is no risk of incorrectly >>> accepting a non-square. >>> >>> As noted above, the normalizing step means that it makes no >>> difference which of the two square roots you get, at least in the conte= xt >>> of RFC 8032. I think it has some slight impact in another context, wher= e >>> the exact choice of the square root can help simplify a formula, but my >>> memory is a bit hazy here. This may be related to the fact that, with p= =3D >>> 2^448 - 2^224 - 1, exactly one of the two square roots of u/v is itself= a >>> square, and the original RFC formula always returns that one, while the >>> proposed formula may return the square root which is a non-square; agai= n, >>> this does not matter in the case of RFC 8032. >>> >>> Thomas >>> >>> From: Crypto-panel on behalf of >>> "Stanislav V. Smyshlyaev" >>> Date: Friday, January 28, 2022 at 07:45 >>> To: Thomas Pornin >>> Cc: Chloe Martindale , " >>> crypto-panel@irtf.org" , "cfrg-chairs@ietf.org" = < >>> cfrg-chairs@ietf.org> >>> Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review of two >>> erratas opened against RFC 8032 (EdDSA) >>> >>> Thank you, Thomas! >>> >>> Regards, >>> Stanislav >>> >>> On Fri, 28 Jan 2022 at 15:43, Thomas Pornin >> 40nccgroup.com@dmarc.ietf.org> wrote: >>> I will have a look too. This looks weird. >>> >>> Thomas >>> >>> From: Crypto-panel on behalf of >>> Chloe Martindale >>> Date: Friday, January 28, 2022 at 06:24 >>> To: "Stanislav V. Smyshlyaev" >>> Cc: "crypto-panel@irtf.org" , " >>> cfrg-chairs@ietf.org" >>> Subject: EXTERNAL: Re: [Crypto-panel] Request for review of two >>> erratas opened against RFC 8032 (EdDSA) >>> >>> Hi all, >>> >>> I can take a look at this. >>> >>> All the best, >>> Chloe >>> >>> On Fri, 28 Jan 2022 at 06:20, Stanislav V. Smyshlyaev < >>> smyshsv@gmail.com> wrote: >>> Dear Crypto Review Panel experts, >>> >>> We've received a request to have a closer look at two errata opened >>> against RFC 8032: >>> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww= .rfc-editor.org%2Ferrata%2Feid5758&data=3D04%7C01%7Cthomas.pornin%40ncc= group.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f= 368e%7C0%7C0%7C637789742687386303%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwM= DAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3Dk49Gr2= WuYIRmJtbPMkL8y8uhUztvAgtHOgZNWo9yOUw%3D&reserved=3D0, >>> >>> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww= .rfc-editor.org%2Ferrata%2Feid5759&data=3D04%7C01%7Cthomas.pornin%40ncc= group.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f= 368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwM= DAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DB6QR5Z= 50rB0Vz3XkgFEtteBSLLL7iV1qFjiRWu8LyfE%3D&reserved=3D0. >>> >>> >>> Previously these two errata were rejected since no mistakes in the >>> current text of the draft had been found. At the same time, the two err= ata >>> might provide more effective ways for square-roots-mod-p. >>> >>> We would like to ask a Crypto Panel expert (or two experts) to chec= k >>> the proposed formulas, i.e., to verify that they are correct and more >>> effective (always or in a vast majority of cases). >>> >>> Any volunteers? >>> >>> Best regards, >>> Stanislav (for chairs) >>> _______________________________________________ >>> Crypto-panel mailing list >>> Crypto-panel@irtf.org >>> >>> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww= .irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=3D04%7C01%7Cthomas.p= ornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68= bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIj= oiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sda= ta=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&reserved=3D0 >>> _______________________________________________ >>> Crypto-panel mailing list >>> Crypto-panel@irtf.org >>> >>> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww= .irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=3D04%7C01%7Cthomas.p= ornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68= bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIj= oiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sda= ta=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&reserved=3D0 >>> >>> _______________________________________________ >>> Crypto-panel mailing list >>> Crypto-panel@irtf.org >>> >>> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww= .irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=3D04%7C01%7Cthomas.p= ornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68= bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIj= oiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sda= ta=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&reserved=3D0 >>> >>> --000000000000c11e2f05d7f784ef Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Dear Stanislav,

Yes they are correct. No remarks are needed for correctness, but for co= mpleteness I would suggest adding a citation/justification and a comment th= at these speed ups are possible only in these specific cases. If you prefer= to keep it simple and just accept based on correctness that's also fin= e=C2=A0with me.

All the = best,
Chloe

<= br>
On Mon,= 14 Feb 2022, 05:40 Stanislav V. Smyshlyaev, <smyshsv@gmail.com> wrote:
Dear Chloe,

Thank you so much = for your work!

>> but only hold for these sp= ecific choices of p
Do I understand correctly that for this speci= fic RFC the formulas=C2=A0are always correct (i.e., the text of errata can = be used in the updated=C2=A0version of the RFC without additional remarks),= but are not always correct in other cases?

Regard= s,
Stanislav


On Mon, 14 Feb 2022 at 02:39, Ch= loe Martindale <chloemartindale@gmail.com> wrote:
Hi= all,

sorry for being a bit slow. I agree with Tho= mas that both errata are correct. One extra detail: the original formulas a= re true in more general situations (for example, in the first case, I belie= ve this holds if p =3D 5 mod 8). The proposed errata are correct, as Thomas= proved above, but only hold for these specific choices of p; the second on= e even relies on u and v being constructed from d and y rather than just ra= ndom field elements. (These are things I just checked experimentally in Sag= e). They are slightly faster, so maybe worth having, but perhaps with this = caveat added in case people erroneously try to use these formulae for compu= ting square roots in other situations.

All the bes= t,
Chloe


On Fri, 28 Jan 2022 at 13:48, Th= omas Pornin <thomas.pornin@nccgroup.com> wrote:
=
As for efficiency, the ga= in is slight. The modular exponentiation (with exponent (p-5)/8) costs at l= east 250 squarings, and an extra dozen multiplications. The proposed formul= a saves two squarings and three multiplications, i.e. we are talking about = an improvement of less than 2%. Nothing ground-breaking here.

Thomas

=EF=BB=BFOn 2022-01-28, 08:44, "Crypto-panel on behalf of Thomas Porni= n" <crypto-panel-bounces@irtf.org on behalf of thoma= s.pornin=3D40nccgroup.com@dmarc.ietf.org> wrote:

=C2=A0 =C2=A0 OK, the proposed formulas are correct. The original formulas = were correct, too.

=C2=A0 =C2=A0 For p =3D 2^255-19: given u and v in the field, then:
=C2=A0 =C2=A0 v*x^2 =3D v*(u*(u*v)^((p-5)/8))^2 =3D v*(u^2)*(u^((p-5)/4))*(= v^((p-5)/4)) =3D u * (u^((p-1)/4) * v^((p-1)/4))
=C2=A0 =C2=A0 If u/v is a square (and u !=3D 0, v !=3D 0) then u^((p-1)/2) = * v^((p-1)/2) =3D 1 (i.e. both u and v are squares, or both u and v are non= -squares).
=C2=A0 =C2=A0 (u^((p-1)/4) * v^((p-1)/4)) is a square root of (u^((p-1)/2) = * v^((p-1)/2)), so its value can only be 1 or -1, therefore v*x^2 =3D u or = -u. In both cases, this leads to a square root of (u/v) by applying step 3 = of RFC 8032 section 5.1.3: if we got x such that v*x^2 =3D u, then x is a s= quare root of u/v; if x is such that v*x^2 =3D -u, then x*i is a square roo= t of u/v, using i =3D sqrt(-1) (in the RFC, it's given as 2^((p-1)/4), = and it is indeed a square root of -1).
=C2=A0 =C2=A0 Thus, the proposed formula, inserted in the RFC text, indeed = yields a square root of u/v if it exists. It does not necessarily yield the= same square root as the original formula, but that does not matter since s= tep 4 of the decoding process normalizes the solution using the least signi= ficant bit.
=C2=A0 =C2=A0 Note that step 3 of section 5.1.3 includes explicitly checkin= g that v*x^2 =3D u or -u, and if u/v is not a square then there cannot be a= x value that matches that test; thus, the new formula does not incorrectly= return a value for a non-square u/v.

=C2=A0 =C2=A0 For p =3D 2^448 - 2^224 - 1, it is slightly simpler:
=C2=A0 =C2=A0 v*x^2 =3D v*(u*(u*v)^((p-3)/4))^2 =3D u * (u^((p-1)/2) * v^((= p-1)/2)
=C2=A0 =C2=A0 If u/v is a square then u^((p-1)/2) * v^((p-1)/2) =3D 1 (see = above), hence v*x^2 =3D u and x is necessarily a solution. Again, this is t= ested explicitly (step 3 of section 5.2.3) so there is no risk of incorrect= ly accepting a non-square.

=C2=A0 =C2=A0 As noted above, the normalizing step means that it makes no d= ifference which of the two square roots you get, at least in the context of= RFC 8032. I think it has some slight impact in another context, where the = exact choice of the square root can help simplify a formula, but my memory = is a bit hazy here. This may be related to the fact that, with p =3D 2^448 = - 2^224 - 1, exactly one of the two square roots of u/v is itself a square,= and the original RFC formula always returns that one, while the proposed f= ormula may return the square root which is a non-square; again, this does n= ot matter in the case of RFC 8032.

=C2=A0 =C2=A0 Thomas

=C2=A0 =C2=A0 From: Crypto-panel <crypto-panel-bounces@irtf.o= rg> on behalf of "Stanislav V. Smyshlyaev" <smyshsv@gmai= l.com>
=C2=A0 =C2=A0 Date: Friday, January 28, 2022 at 07:45
=C2=A0 =C2=A0 To: Thomas Pornin <thomas.pornin=3D40nccgroup.c= om@dmarc.ietf.org>
=C2=A0 =C2=A0 Cc: Chloe Martindale <chloemartindale@gmail.com= >, "crypto-panel@irtf.org" <crypto-panel@irtf.or= g>, "cfrg-chairs@ietf.org" <cfrg-chairs@ietf.or= g>
=C2=A0 =C2=A0 Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review = of two erratas opened against RFC 8032 (EdDSA)

=C2=A0 =C2=A0 Thank you, Thomas!

=C2=A0 =C2=A0 Regards,
=C2=A0 =C2=A0 Stanislav

=C2=A0 =C2=A0 On Fri, 28 Jan 2022 at 15:43, Thomas Pornin <thomas.pornin= =3D40nccgroup.com@dmarc.ietf.org> wrote:
=C2=A0 =C2=A0 I will have a look too. This looks weird.

=C2=A0 =C2=A0 Thomas

=C2=A0 =C2=A0 From: Crypto-panel <crypto-panel-bounces@irtf.o= rg> on behalf of Chloe Martindale <chloemartindale@gmail.c= om>
=C2=A0 =C2=A0 Date: Friday, January 28, 2022 at 06:24
=C2=A0 =C2=A0 To: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com<= /a>>
=C2=A0 =C2=A0 Cc: "crypto-panel@irtf.org" <crypto-pa= nel@irtf.org>, "cfrg-chairs@ietf.org" <cfrg-= chairs@ietf.org>
=C2=A0 =C2=A0 Subject: EXTERNAL: Re: [Crypto-panel] Request for review of t= wo erratas opened against RFC 8032 (EdDSA)

=C2=A0 =C2=A0 Hi all,

=C2=A0 =C2=A0 I can take a look at this.

=C2=A0 =C2=A0 All the best,
=C2=A0 =C2=A0 Chloe

=C2=A0 =C2=A0 On Fri, 28 Jan 2022 at 06:20, Stanislav V. Smyshlyaev <smys= hsv@gmail.com> wrote:
=C2=A0 =C2=A0 Dear Crypto Review Panel experts,

=C2=A0 =C2=A0 We've received a request to have a closer look at two err= ata opened against RFC 8032: https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fww= w.rfc-editor.org%2Ferrata%2Feid5758&amp;data=3D04%7C01%7Cthomas.pornin%= 40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee0= 1a62f368e%7C0%7C0%7C637789742687386303%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4w= LjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata= =3Dk49Gr2WuYIRmJtbPMkL8y8uhUztvAgtHOgZNWo9yOUw%3D&amp;reserved=3D0,= https://gbr01.safelin= ks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.rfc-editor.org%2Ferrata%= 2Feid5759&amp;data=3D04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6= b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789= 742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLC= JBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=3DB6QR5Z50rB0Vz3XkgFEtteB= SLLL7iV1qFjiRWu8LyfE%3D&amp;reserved=3D0.

=C2=A0 =C2=A0 Previously these two errata were rejected since no mistakes i= n the current text of the draft had been found. At the same time, the two e= rrata might provide more effective ways for square-roots-mod-p.

=C2=A0 =C2=A0 We would like to ask a Crypto Panel expert (or two experts) t= o check the proposed formulas, i.e., to verify that they are correct and mo= re effective (always or in a vast majority of cases).

=C2=A0 =C2=A0 Any volunteers?

=C2=A0 =C2=A0 Best regards,
=C2=A0 =C2=A0 Stanislav (for chairs)
=C2=A0 =C2=A0 _______________________________________________
=C2=A0 =C2=A0 Crypto-panel mailing list
=C2=A0 =C2=A0 Crypto-panel@irtf.org
=C2=A0 =C2=A0 https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.ir= tf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&amp;data=3D04%7C01%7Cthomas.= pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f6= 8bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWI= joiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&am= p;sdata=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved= =3D0
=C2=A0 =C2=A0 _______________________________________________
=C2=A0 =C2=A0 Crypto-panel mailing list
=C2=A0 =C2=A0 Crypto-panel@irtf.org
=C2=A0 =C2=A0 https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.ir= tf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&amp;data=3D04%7C01%7Cthomas.= pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f6= 8bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWI= joiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&am= p;sdata=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved= =3D0

=C2=A0 =C2=A0 _______________________________________________
=C2=A0 =C2=A0 Crypto-panel mailing list
=C2=A0 =C2=A0 Crypto-panel@irtf.org
=C2=A0 =C2=A0 https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.ir= tf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&amp;data=3D04%7C01%7Cthomas.= pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f6= 8bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWI= joiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&am= p;sdata=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved= =3D0

--000000000000c11e2f05d7f784ef-- From nobody Mon Feb 14 21:32:50 2022 Return-Path: X-Original-To: crypto-panel@ietfa.amsl.com Delivered-To: crypto-panel@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BAF3C3A0CB2 for ; Mon, 14 Feb 2022 21:32:48 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.004 X-Spam-Level: X-Spam-Status: No, score=-2.004 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, HTML_MESSAGE=0.001, HTML_OBFUSCATE_10_20=0.093, 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=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 FS3hFiefTDT6 for ; Mon, 14 Feb 2022 21:32:47 -0800 (PST) Received: from mail-ej1-x632.google.com (mail-ej1-x632.google.com [IPv6:2a00:1450:4864:20::632]) (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 3B7393A0ABD for ; Mon, 14 Feb 2022 21:32:47 -0800 (PST) Received: by mail-ej1-x632.google.com with SMTP id p9so18947059ejd.6 for ; Mon, 14 Feb 2022 21:32:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:from:date:message-id:subject:to:cc; bh=4tR+H/uvalUNolsGnjdTe0CbkgODy+65FtzRo47VXA4=; b=ph/g+Pw9uAXm2FyiFQ1Ig0rRTxG1j7WetPU1Z7tlHyxR8HX2NVBV8YRm1xi8O0uNuj zNRCgb5OJdvz6U3/GtXaMi44OOfIS7bHI4eRyEAq1XJ+LZMsf4lJTx2dS/V4iIcovKYK VWGx5T5zbYRKksi633j++23bzYTiFKyfbtWRa+hi7k8/ataqiiyG3Fu8vPq+yRBoWtac 2JsWmrkFIli7VJ0M/hb5LH4HdSCGN5L9U3lR5i5I1/BTryNdahYqbDT2C2ssRqkg7i+3 INFvXy/F9WA8ztRBsRgdUV83kyMManuGUL8EDsoS0LQ5ckJd8K/wg/gV/IMpxpN699A/ Do0w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:from:date:message-id:subject:to:cc; bh=4tR+H/uvalUNolsGnjdTe0CbkgODy+65FtzRo47VXA4=; b=OfUTKvPKetZWl5H3IzVfPdeiJ9XN9HWpN2U+7ShSt9Hsu7hGLzohqmgh87k7d9Fs7s mugBi7y+YPH8viaKns7zWdmtY4Yju48+AMxD3ibif7lpOxhmQp3G9qZ7T/0Q5LT6MRoM u8VV24fwOJ894Ilt9HcX1pZ9r1rGu5Vybbv805dEs5KsJ0f59EbE3k1s6gnusH4zua5H 2Uz1MypF/xksc1sKMO4g4Z5AS9yLd8w29qUOLwVlez9lsFB6wdoqQn6WvDfp3FJY5Wm6 rolzEjSjEoNC8ViOchdGeTTBbmti1fZ6T/co+dhEVGXcNVQ4gskDjP90fCTBtIIi//X5 jQNQ== X-Gm-Message-State: AOAM530mrwa7UGERNcLB9ScbPzA0RWRcWd513PnyxksB68iYvvWsxWp+ jXsIm84lH+6QCiPzWiChPAx3l1RycuX+LN8YdUbXI+R8g/XM2Q== X-Google-Smtp-Source: ABdhPJxSx0+VIfeqlKB2iNVn9C8mohs8ZPzNuA9ZWj1lmpCEZUCnRMkMjyqvPTUWhWj2cpSaSnQFL3FT2L+fRFEzRxw= X-Received: by 2002:a17:906:644f:: with SMTP id l15mr1600610ejn.135.1644903163643; Mon, 14 Feb 2022 21:32:43 -0800 (PST) MIME-Version: 1.0 From: "Stanislav V. Smyshlyaev" Date: Tue, 15 Feb 2022 08:33:54 +0300 Message-ID: To: crypto-panel@irtf.org Cc: cfrg-chairs@ietf.org Content-Type: multipart/alternative; boundary="000000000000c2484705d807dcf2" Archived-At: Subject: [Crypto-panel] Request for review: OPRFs using Prime-Order Groups X-BeenThere: crypto-panel@irtf.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 15 Feb 2022 05:32:49 -0000 --000000000000c2484705d807dcf2 Content-Type: text/plain; charset="UTF-8" Dear Crypto Panel Experts, The chairs would like to ask the Crypto Panel to provide a review for version -09 of the "Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups" draft, draft-irtf-cfrg-voprf-09 ( https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-voprf-09). Any volunteers? Stanislav (on behalf of the CFRG Chairs) --000000000000c2484705d807dcf2 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Dear=C2=A0Crypto=C2= =A0Panel=C2=A0Experts,
<= br>
The chairs would like to ask the=C2=A0Crypto=C2=A0Panel=C2=A0to provide = a review for version -09 of the "Oblivious Pseudorandom Functions (OPR= Fs) using Prime-Order Groups" draft, draft-irtf-cfrg-voprf-09 (https:/= /datatracker.ietf.org/doc/html/draft-irtf-cfrg-voprf-09).

Any volunteers?

Stanislav (on behalf of the CFRG Cha= irs)

--000000000000c2484705d807dcf2-- From nobody Mon Feb 14 21:35:48 2022 Return-Path: X-Original-To: crypto-panel@ietfa.amsl.com Delivered-To: crypto-panel@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8470E3A0CF7 for ; Mon, 14 Feb 2022 21:35:46 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -7.097 X-Spam-Level: X-Spam-Status: No, score=-7.097 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, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=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 yYrKJHhx_3KY for ; Mon, 14 Feb 2022 21:35:41 -0800 (PST) Received: from mail-ed1-x533.google.com (mail-ed1-x533.google.com [IPv6:2a00:1450:4864:20::533]) (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 3D8963A0CCB for ; Mon, 14 Feb 2022 21:35:41 -0800 (PST) Received: by mail-ed1-x533.google.com with SMTP id z13so12036937edc.12 for ; Mon, 14 Feb 2022 21:35:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=G6lWDQ1Qv3S/eJYdJpicXLKgMD7ioYspWkw0XPoLExg=; b=TP9hBGdUgiRaBwmv0QVFucLPzwLrpV0gkuNQfyWcJhB7siQuu08rwFXyeM1myvRwxx sI3mBLomQEEHgOBA374PZsxnRbVkX9eJxvI4MXdUvT5oPVxdw/LWa7eptT3kqJ/F2RO9 JuaN8qszCjQaTU2FxwBiT/hffcbxCP4HCxqtf7jELCL6fjOzHXV7tr8jat1+5TlwkN5b /8xw7a6/wsjvfdcbLPfT5dXqYGZjfvasr3POqbbop6BFtGit+nuzPc/t1Zyo3dsuAonJ 9lOdLQTtQBWfkYXqr3W+GdXoagclQ3Awj6VwAvy5jyLPtB70ZcKN6MC2+RayhYhVoM5M nqpw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=G6lWDQ1Qv3S/eJYdJpicXLKgMD7ioYspWkw0XPoLExg=; b=ICH5iyQmmPtapkLBRK83RmMuJPjBT517b50RTSChyvOL6yngP//83gCE2JNOBNi4f8 iuQKy+Pc0FG8u/hKjdHIuTpcHC2MT3ncOSyh+6FO/57RvnDJYJmw8rWnLRlIlDvLzKhU YCl+6TbGU4MkxRzzufLduOgQCBd0QqMFqxrbQ3pOBtV1al3YTsbaDHlwTX4rHkOTh0l9 P8KhjBCz789M0JBJ1dKPahWiVoyUUXHNv6AKV3d5VsgACB2HEC6wJwTv/w9TunI/rYA3 L9Jy5MRdqaj5GxohoY5KV/n6EI38XimP8jdKPQWQb32yXaI10JR1Z3ChJsUt5b8xiXyF mSAA== X-Gm-Message-State: AOAM532WKBKPvJuTlPVjtcsPiePYUaGZgaplKYDxLxK1M1f/T36yb6GP 7SVY+XJuREXlbtHgEtpI9IgSdPaD9LGWV8J3QIM= X-Google-Smtp-Source: ABdhPJyGoYYhtbblVxzAJOUnfrk+F82lqon87JBPkMlLGPVHW01+b5ED76kuDmYWQPHuAki/3XgI++s5234ALV63e68= X-Received: by 2002:a05:6402:348c:: with SMTP id v12mr2237617edc.384.1644903339077; Mon, 14 Feb 2022 21:35:39 -0800 (PST) MIME-Version: 1.0 References: <83FC3CEC-7742-4356-9471-34826B05ACC7@nccgroup.com> In-Reply-To: From: "Stanislav V. Smyshlyaev" Date: Tue, 15 Feb 2022 08:36:49 +0300 Message-ID: To: Chloe Martindale Cc: Thomas Pornin , Thomas Pornin , crypto-panel@irtf.org, cfrg-chairs@ietf.org Content-Type: multipart/alternative; boundary="0000000000003731b705d807e7c2" Archived-At: Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review of two erratas opened against RFC 8032 (EdDSA) X-BeenThere: crypto-panel@irtf.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 15 Feb 2022 05:35:47 -0000 --0000000000003731b705d807e7c2 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Chloe and Thomas, Thank you so much for your reviews! We'll mark the errata as "hold for future update", with a comment about formulas being only slightly faster than the existing ones. Thanks again! Regards, Stanislav (on behalf of CFRG Chairs) On Mon, 14 Feb 2022 at 13:02, Chloe Martindale wrote: > Dear Stanislav, > > Yes they are correct. No remarks are needed for correctness, but for > completeness I would suggest adding a citation/justification and a commen= t > that these speed ups are possible only in these specific cases. If you > prefer to keep it simple and just accept based on correctness that's also > fine with me. > > All the best, > Chloe > > > On Mon, 14 Feb 2022, 05:40 Stanislav V. Smyshlyaev, > wrote: > >> Dear Chloe, >> >> Thank you so much for your work! >> >> >> but only hold for these specific choices of p >> Do I understand correctly that for this specific RFC the formulas are >> always correct (i.e., the text of errata can be used in the updated vers= ion >> of the RFC without additional remarks), but are not always correct in ot= her >> cases? >> >> Regards, >> Stanislav >> >> >> On Mon, 14 Feb 2022 at 02:39, Chloe Martindale >> wrote: >> >>> Hi all, >>> >>> sorry for being a bit slow. I agree with Thomas that both errata are >>> correct. One extra detail: the original formulas are true in more gener= al >>> situations (for example, in the first case, I believe this holds if p = =3D 5 >>> mod 8). The proposed errata are correct, as Thomas proved above, but on= ly >>> hold for these specific choices of p; the second one even relies on u a= nd v >>> being constructed from d and y rather than just random field elements. >>> (These are things I just checked experimentally in Sage). They are slig= htly >>> faster, so maybe worth having, but perhaps with this caveat added in ca= se >>> people erroneously try to use these formulae for computing square roots= in >>> other situations. >>> >>> All the best, >>> Chloe >>> >>> >>> On Fri, 28 Jan 2022 at 13:48, Thomas Pornin >>> wrote: >>> >>>> As for efficiency, the gain is slight. The modular exponentiation (wit= h >>>> exponent (p-5)/8) costs at least 250 squarings, and an extra dozen >>>> multiplications. The proposed formula saves two squarings and three >>>> multiplications, i.e. we are talking about an improvement of less than= 2%. >>>> Nothing ground-breaking here. >>>> >>>> Thomas >>>> >>>> =EF=BB=BFOn 2022-01-28, 08:44, "Crypto-panel on behalf of Thomas Porni= n" < >>>> crypto-panel-bounces@irtf.org on behalf of thomas.pornin=3D >>>> 40nccgroup.com@dmarc.ietf.org> wrote: >>>> >>>> OK, the proposed formulas are correct. The original formulas were >>>> correct, too. >>>> >>>> For p =3D 2^255-19: given u and v in the field, then: >>>> v*x^2 =3D v*(u*(u*v)^((p-5)/8))^2 =3D >>>> v*(u^2)*(u^((p-5)/4))*(v^((p-5)/4)) =3D u * (u^((p-1)/4) * v^((p-1)/4)= ) >>>> If u/v is a square (and u !=3D 0, v !=3D 0) then u^((p-1)/2) * >>>> v^((p-1)/2) =3D 1 (i.e. both u and v are squares, or both u and v are >>>> non-squares). >>>> (u^((p-1)/4) * v^((p-1)/4)) is a square root of (u^((p-1)/2) * >>>> v^((p-1)/2)), so its value can only be 1 or -1, therefore v*x^2 =3D u = or -u. >>>> In both cases, this leads to a square root of (u/v) by applying step 3= of >>>> RFC 8032 section 5.1.3: if we got x such that v*x^2 =3D u, then x is a= square >>>> root of u/v; if x is such that v*x^2 =3D -u, then x*i is a square root= of >>>> u/v, using i =3D sqrt(-1) (in the RFC, it's given as 2^((p-1)/4), and = it is >>>> indeed a square root of -1). >>>> Thus, the proposed formula, inserted in the RFC text, indeed yield= s >>>> a square root of u/v if it exists. It does not necessarily yield the s= ame >>>> square root as the original formula, but that does not matter since st= ep 4 >>>> of the decoding process normalizes the solution using the least signif= icant >>>> bit. >>>> Note that step 3 of section 5.1.3 includes explicitly checking tha= t >>>> v*x^2 =3D u or -u, and if u/v is not a square then there cannot be a x= value >>>> that matches that test; thus, the new formula does not incorrectly ret= urn a >>>> value for a non-square u/v. >>>> >>>> For p =3D 2^448 - 2^224 - 1, it is slightly simpler: >>>> v*x^2 =3D v*(u*(u*v)^((p-3)/4))^2 =3D u * (u^((p-1)/2) * v^((p-1)/= 2) >>>> If u/v is a square then u^((p-1)/2) * v^((p-1)/2) =3D 1 (see above= ), >>>> hence v*x^2 =3D u and x is necessarily a solution. Again, this is test= ed >>>> explicitly (step 3 of section 5.2.3) so there is no risk of incorrectl= y >>>> accepting a non-square. >>>> >>>> As noted above, the normalizing step means that it makes no >>>> difference which of the two square roots you get, at least in the cont= ext >>>> of RFC 8032. I think it has some slight impact in another context, whe= re >>>> the exact choice of the square root can help simplify a formula, but m= y >>>> memory is a bit hazy here. This may be related to the fact that, with = p =3D >>>> 2^448 - 2^224 - 1, exactly one of the two square roots of u/v is itsel= f a >>>> square, and the original RFC formula always returns that one, while th= e >>>> proposed formula may return the square root which is a non-square; aga= in, >>>> this does not matter in the case of RFC 8032. >>>> >>>> Thomas >>>> >>>> From: Crypto-panel on behalf of >>>> "Stanislav V. Smyshlyaev" >>>> Date: Friday, January 28, 2022 at 07:45 >>>> To: Thomas Pornin >>>> Cc: Chloe Martindale , " >>>> crypto-panel@irtf.org" , "cfrg-chairs@ietf.org" >>>> >>>> Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review of tw= o >>>> erratas opened against RFC 8032 (EdDSA) >>>> >>>> Thank you, Thomas! >>>> >>>> Regards, >>>> Stanislav >>>> >>>> On Fri, 28 Jan 2022 at 15:43, Thomas Pornin >>> 40nccgroup.com@dmarc.ietf.org> wrote: >>>> I will have a look too. This looks weird. >>>> >>>> Thomas >>>> >>>> From: Crypto-panel on behalf of >>>> Chloe Martindale >>>> Date: Friday, January 28, 2022 at 06:24 >>>> To: "Stanislav V. Smyshlyaev" >>>> Cc: "crypto-panel@irtf.org" , " >>>> cfrg-chairs@ietf.org" >>>> Subject: EXTERNAL: Re: [Crypto-panel] Request for review of two >>>> erratas opened against RFC 8032 (EdDSA) >>>> >>>> Hi all, >>>> >>>> I can take a look at this. >>>> >>>> All the best, >>>> Chloe >>>> >>>> On Fri, 28 Jan 2022 at 06:20, Stanislav V. Smyshlyaev < >>>> smyshsv@gmail.com> wrote: >>>> Dear Crypto Review Panel experts, >>>> >>>> We've received a request to have a closer look at two errata opene= d >>>> against RFC 8032: >>>> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fww= w.rfc-editor.org%2Ferrata%2Feid5758&data=3D04%7C01%7Cthomas.pornin%40nc= cgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62= f368e%7C0%7C0%7C637789742687386303%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAw= MDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3Dk49Gr= 2WuYIRmJtbPMkL8y8uhUztvAgtHOgZNWo9yOUw%3D&reserved=3D0, >>>> >>>> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fww= w.rfc-editor.org%2Ferrata%2Feid5759&data=3D04%7C01%7Cthomas.pornin%40nc= cgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62= f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAw= MDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DB6QR5= Z50rB0Vz3XkgFEtteBSLLL7iV1qFjiRWu8LyfE%3D&reserved=3D0. >>>> >>>> >>>> Previously these two errata were rejected since no mistakes in the >>>> current text of the draft had been found. At the same time, the two er= rata >>>> might provide more effective ways for square-roots-mod-p. >>>> >>>> We would like to ask a Crypto Panel expert (or two experts) to >>>> check the proposed formulas, i.e., to verify that they are correct and= more >>>> effective (always or in a vast majority of cases). >>>> >>>> Any volunteers? >>>> >>>> Best regards, >>>> Stanislav (for chairs) >>>> _______________________________________________ >>>> Crypto-panel mailing list >>>> Crypto-panel@irtf.org >>>> >>>> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fww= w.irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=3D04%7C01%7Cthomas.= pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f6= 8bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWI= joiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sd= ata=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&reserved=3D0 >>>> _______________________________________________ >>>> Crypto-panel mailing list >>>> Crypto-panel@irtf.org >>>> >>>> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fww= w.irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=3D04%7C01%7Cthomas.= pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f6= 8bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWI= joiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sd= ata=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&reserved=3D0 >>>> >>>> _______________________________________________ >>>> Crypto-panel mailing list >>>> Crypto-panel@irtf.org >>>> >>>> https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fww= w.irtf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&data=3D04%7C01%7Cthomas.= pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f6= 8bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWI= joiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sd= ata=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&reserved=3D0 >>>> >>>> --0000000000003731b705d807e7c2 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Chloe and Thomas,=C2=A0

= Thank you so much for your reviews!=C2=A0

We'l= l mark the errata as "hold for future update", with a comment abo= ut formulas being only slightly faster than the existing ones.
Thanks again!

Regards,
Stan= islav (on behalf of CFRG Chairs)

=
On Mon, 14 Feb 2022 at 13:02, Chloe M= artindale <chloemartindale@= gmail.com> wrote:
Dear Stanislav,

Yes they are correct. No remarks are needed for correctness,= but for completeness I would suggest adding a citation/justification and a= comment that these speed ups are possible only in these specific cases. If= you prefer to keep it simple and just accept based on correctness that'= ;s also fine=C2=A0with me.

All the best,
Chloe


On Mon, 14 Feb 2022, 05:40 Stanislav V. Smyshlyaev, <smyshsv@gmail.com> wrote:
D= ear Chloe,

Thank you so much for your work!
>> but only hold for these specific choices of p
Do I understand correctly that for this specific RFC the formulas=C2=A0a= re always correct (i.e., the text of errata can be used in the updated=C2= =A0version of the RFC without additional remarks), but are not always corre= ct in other cases?

Regards,
Stanislav


On Mon, 14 Feb 2022 at 02:39, Chloe Martindale <chloemartindale@gmail.com> wrote:
Hi all,

sorry for being a bit slow. I agree with Thomas that both errata are = correct. One extra detail: the original formulas are true in more general s= ituations (for example, in the first case, I believe this holds if p =3D 5 = mod 8). The proposed errata are correct, as Thomas proved above, but only h= old for these specific choices of p; the second one even relies on u and v = being constructed from d and y rather than just random field elements. (The= se are things I just checked experimentally in Sage). They are slightly fas= ter, so maybe worth having, but perhaps with this caveat added in case peop= le erroneously try to use these formulae for computing square roots in othe= r situations.

All the best,
Chloe


On Fri, 28 Jan 2022 at 13:48, Thomas Pornin <thomas.pornin@nccgroup.com> wrote:
As for efficiency, the gain is slight. The modul= ar exponentiation (with exponent (p-5)/8) costs at least 250 squarings, and= an extra dozen multiplications. The proposed formula saves two squarings a= nd three multiplications, i.e. we are talking about an improvement of less = than 2%. Nothing ground-breaking here.

Thomas

=EF=BB=BFOn 2022-01-28, 08:44, "Crypto-panel on behalf of Thomas Porni= n" <crypto-panel-bounces@irtf.org on behalf of thoma= s.pornin=3D40nccgroup.com@dmarc.ietf.org> wrote:

=C2=A0 =C2=A0 OK, the proposed formulas are correct. The original formulas = were correct, too.

=C2=A0 =C2=A0 For p =3D 2^255-19: given u and v in the field, then:
=C2=A0 =C2=A0 v*x^2 =3D v*(u*(u*v)^((p-5)/8))^2 =3D v*(u^2)*(u^((p-5)/4))*(= v^((p-5)/4)) =3D u * (u^((p-1)/4) * v^((p-1)/4))
=C2=A0 =C2=A0 If u/v is a square (and u !=3D 0, v !=3D 0) then u^((p-1)/2) = * v^((p-1)/2) =3D 1 (i.e. both u and v are squares, or both u and v are non= -squares).
=C2=A0 =C2=A0 (u^((p-1)/4) * v^((p-1)/4)) is a square root of (u^((p-1)/2) = * v^((p-1)/2)), so its value can only be 1 or -1, therefore v*x^2 =3D u or = -u. In both cases, this leads to a square root of (u/v) by applying step 3 = of RFC 8032 section 5.1.3: if we got x such that v*x^2 =3D u, then x is a s= quare root of u/v; if x is such that v*x^2 =3D -u, then x*i is a square roo= t of u/v, using i =3D sqrt(-1) (in the RFC, it's given as 2^((p-1)/4), = and it is indeed a square root of -1).
=C2=A0 =C2=A0 Thus, the proposed formula, inserted in the RFC text, indeed = yields a square root of u/v if it exists. It does not necessarily yield the= same square root as the original formula, but that does not matter since s= tep 4 of the decoding process normalizes the solution using the least signi= ficant bit.
=C2=A0 =C2=A0 Note that step 3 of section 5.1.3 includes explicitly checkin= g that v*x^2 =3D u or -u, and if u/v is not a square then there cannot be a= x value that matches that test; thus, the new formula does not incorrectly= return a value for a non-square u/v.

=C2=A0 =C2=A0 For p =3D 2^448 - 2^224 - 1, it is slightly simpler:
=C2=A0 =C2=A0 v*x^2 =3D v*(u*(u*v)^((p-3)/4))^2 =3D u * (u^((p-1)/2) * v^((= p-1)/2)
=C2=A0 =C2=A0 If u/v is a square then u^((p-1)/2) * v^((p-1)/2) =3D 1 (see = above), hence v*x^2 =3D u and x is necessarily a solution. Again, this is t= ested explicitly (step 3 of section 5.2.3) so there is no risk of incorrect= ly accepting a non-square.

=C2=A0 =C2=A0 As noted above, the normalizing step means that it makes no d= ifference which of the two square roots you get, at least in the context of= RFC 8032. I think it has some slight impact in another context, where the = exact choice of the square root can help simplify a formula, but my memory = is a bit hazy here. This may be related to the fact that, with p =3D 2^448 = - 2^224 - 1, exactly one of the two square roots of u/v is itself a square,= and the original RFC formula always returns that one, while the proposed f= ormula may return the square root which is a non-square; again, this does n= ot matter in the case of RFC 8032.

=C2=A0 =C2=A0 Thomas

=C2=A0 =C2=A0 From: Crypto-panel <crypto-panel-bounces@irtf.o= rg> on behalf of "Stanislav V. Smyshlyaev" <smyshsv@gmai= l.com>
=C2=A0 =C2=A0 Date: Friday, January 28, 2022 at 07:45
=C2=A0 =C2=A0 To: Thomas Pornin <thomas.pornin=3D40nccgroup.c= om@dmarc.ietf.org>
=C2=A0 =C2=A0 Cc: Chloe Martindale <chloemartindale@gmail.com= >, "crypto-panel@irtf.org" <crypto-panel@irtf.org= >, "cfrg-chairs@ietf.org" <cfrg-chairs@ietf.org= >
=C2=A0 =C2=A0 Subject: Re: [Crypto-panel] EXTERNAL: Re: Request for review = of two erratas opened against RFC 8032 (EdDSA)

=C2=A0 =C2=A0 Thank you, Thomas!

=C2=A0 =C2=A0 Regards,
=C2=A0 =C2=A0 Stanislav

=C2=A0 =C2=A0 On Fri, 28 Jan 2022 at 15:43, Thomas Pornin <thomas.pornin= =3D40nccgroup.com@dmarc.ietf.org> wrote:
=C2=A0 =C2=A0 I will have a look too. This looks weird.

=C2=A0 =C2=A0 Thomas

=C2=A0 =C2=A0 From: Crypto-panel <crypto-panel-bounces@irtf.o= rg> on behalf of Chloe Martindale <chloemartindale@gmail.c= om>
=C2=A0 =C2=A0 Date: Friday, January 28, 2022 at 06:24
=C2=A0 =C2=A0 To: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com<= /a>>
=C2=A0 =C2=A0 Cc: "crypto-panel@irtf.org" <crypto-pa= nel@irtf.org>, "cfrg-chairs@ietf.org" <cfrg-cha= irs@ietf.org>
=C2=A0 =C2=A0 Subject: EXTERNAL: Re: [Crypto-panel] Request for review of t= wo erratas opened against RFC 8032 (EdDSA)

=C2=A0 =C2=A0 Hi all,

=C2=A0 =C2=A0 I can take a look at this.

=C2=A0 =C2=A0 All the best,
=C2=A0 =C2=A0 Chloe

=C2=A0 =C2=A0 On Fri, 28 Jan 2022 at 06:20, Stanislav V. Smyshlyaev <smys= hsv@gmail.com> wrote:
=C2=A0 =C2=A0 Dear Crypto Review Panel experts,

=C2=A0 =C2=A0 We've received a request to have a closer look at two err= ata opened against RFC 8032: https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fww= w.rfc-editor.org%2Ferrata%2Feid5758&amp;data=3D04%7C01%7Cthomas.pornin%= 40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee0= 1a62f368e%7C0%7C0%7C637789742687386303%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4w= LjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata= =3Dk49Gr2WuYIRmJtbPMkL8y8uhUztvAgtHOgZNWo9yOUw%3D&amp;reserved=3D0,= https://gbr01.safelin= ks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.rfc-editor.org%2Ferrata%= 2Feid5759&amp;data=3D04%7C01%7Cthomas.pornin%40nccgroup.com%7C39588fcd6= b3a4eb2a2e408d9e26416af%7Ca41111be486b45f68bd0ee01a62f368e%7C0%7C0%7C637789= 742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLC= JBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=3DB6QR5Z50rB0Vz3XkgFEtteB= SLLL7iV1qFjiRWu8LyfE%3D&amp;reserved=3D0.

=C2=A0 =C2=A0 Previously these two errata were rejected since no mistakes i= n the current text of the draft had been found. At the same time, the two e= rrata might provide more effective ways for square-roots-mod-p.

=C2=A0 =C2=A0 We would like to ask a Crypto Panel expert (or two experts) t= o check the proposed formulas, i.e., to verify that they are correct and mo= re effective (always or in a vast majority of cases).

=C2=A0 =C2=A0 Any volunteers?

=C2=A0 =C2=A0 Best regards,
=C2=A0 =C2=A0 Stanislav (for chairs)
=C2=A0 =C2=A0 _______________________________________________
=C2=A0 =C2=A0 Crypto-panel mailing list
=C2=A0 =C2=A0 Crypto-panel@irtf.org
=C2=A0 =C2=A0 https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.ir= tf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&amp;data=3D04%7C01%7Cthomas.= pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f6= 8bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWI= joiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&am= p;sdata=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved= =3D0
=C2=A0 =C2=A0 _______________________________________________
=C2=A0 =C2=A0 Crypto-panel mailing list
=C2=A0 =C2=A0 Crypto-panel@irtf.org
=C2=A0 =C2=A0 https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.ir= tf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&amp;data=3D04%7C01%7Cthomas.= pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f6= 8bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWI= joiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&am= p;sdata=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved= =3D0

=C2=A0 =C2=A0 _______________________________________________
=C2=A0 =C2=A0 Crypto-panel mailing list
=C2=A0 =C2=A0 Crypto-panel@irtf.org
=C2=A0 =C2=A0 https://gbr01.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fwww.ir= tf.org%2Fmailman%2Flistinfo%2Fcrypto-panel&amp;data=3D04%7C01%7Cthomas.= pornin%40nccgroup.com%7C39588fcd6b3a4eb2a2e408d9e26416af%7Ca41111be486b45f6= 8bd0ee01a62f368e%7C0%7C0%7C637789742687542555%7CUnknown%7CTWFpbGZsb3d8eyJWI= joiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&am= p;sdata=3DGEKFMaVjuISqEdKPktiXnkMwk87FtwrgNIxdYTqa0gA%3D&amp;reserved= =3D0

--0000000000003731b705d807e7c2-- From nobody Tue Feb 15 02:21:04 2022 Return-Path: X-Original-To: crypto-panel@ietfa.amsl.com Delivered-To: crypto-panel@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 296243A0B47 for ; Tue, 15 Feb 2022 02:21:01 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -4.299 X-Spam-Level: X-Spam-Status: No, score=-4.299 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_MED=-2.3, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=qti.qualcomm.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 q2y5kL-SMm8l for ; Tue, 15 Feb 2022 02:20:56 -0800 (PST) Received: from esa.hc3962-90.iphmx.com (esa.hc3962-90.iphmx.com [216.71.140.77]) (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 6E5E73A0B44 for ; Tue, 15 Feb 2022 02:20:56 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=qti.qualcomm.com; i=@qti.qualcomm.com; q=dns/txt; s=qccesdkim1; t=1644920456; x=1645525256; h=from:to:cc:subject:date:message-id:references: in-reply-to:mime-version; bh=JDUw8jPkY60MoEdicLC+YpL1PefewTAWOBWy8mnnwKU=; b=WTA+Ul+AlXAtnIinHvIX5t007OMYz3hb1FbcRL4sL4I0dfcfDzU5mTlh oyBU9YDAioZoX2TW++DXytFtIyeBhUeuvmhKz3as6nrI1BIb2Z96FQz6l Vk2tcolRR8+2Olva9DhwTFhhLYa8zj9Tf0X4uPx6naDKu3Q2Id4JQEvZ4 8=; Received: from mail-mw2nam10lp2100.outbound.protection.outlook.com (HELO NAM10-MW2-obe.outbound.protection.outlook.com) ([104.47.55.100]) by ob1.hc3962-90.iphmx.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 15 Feb 2022 10:20:54 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Xq8jlbcCobba0mi9dc80kA00HB7uyDZILL2QCL/z+Y0F3XyWY+tzPlTGDlDVSqFNK6wVzf8fE2YpjBhofdUDEao/es8ygaGIagrI34OCL/j7s7G7C9Rq64OncQvCIoxgnaKXPxXz2CbVOCJvKBml20ZIGRUNTaJ9xl8GVP1/xYLSqa0t8dcRaH9oAYGVjqciBQ6ZtCUHYdOA31wL+igXosRlEuFSt4GyDVHWLe7dnDFcPcLq/G79IuoWV5bF2lOVny6/YPl5U62GFguUj9YsJHXi46ocYuCtz6g1SsQ3qkiMc2BfAya0ZH4hyIj7025/nWIIejSsRtys5WhzvRRYTA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=JDUw8jPkY60MoEdicLC+YpL1PefewTAWOBWy8mnnwKU=; b=S5eTAsFcqpbvW3B+J/X3qP1QddLOys0MAyPNGCRcyxRKUOsYpQRxW1u0X2Nl5/WZ38SaGcTmOQrh/CVYvk11e6RUdLCASythrxjRgTLl2Eu8Yionse6bPBBdBCZv+mRhRWyoct/rPthspr8yir92kL1XYsSXDX5k1HQIIYdWJTff/5wgmMVtX0kjpUmxNA8+qWNNn5sNvLtrRn4pk5mq35KhXnco6E5oTkZmJFGuSFdEQR1PuDZdVBzjwQl9OuA9dA9HHMSBIoPW8t9TpD+xL/ILHj3c5sm0VLF368VhGBp/oQTLhk+Sj+iaJK459MKneuYYUOdXCZIQBtRpVCuvGQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=qti.qualcomm.com; dmarc=pass action=none header.from=qti.qualcomm.com; dkim=pass header.d=qti.qualcomm.com; arc=none Received: from BL3PR02MB7970.namprd02.prod.outlook.com (2603:10b6:208:355::10) by CO1PR02MB8588.namprd02.prod.outlook.com (2603:10b6:303:15f::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4995.14; Tue, 15 Feb 2022 10:20:50 +0000 Received: from BL3PR02MB7970.namprd02.prod.outlook.com ([fe80::503f:e4f5:5efe:e7bd]) by BL3PR02MB7970.namprd02.prod.outlook.com ([fe80::503f:e4f5:5efe:e7bd%6]) with mapi id 15.20.4995.014; Tue, 15 Feb 2022 10:20:50 +0000 From: Virendra Kumar To: "Stanislav V. Smyshlyaev" , "crypto-panel@irtf.org" CC: "cfrg-chairs@ietf.org" Thread-Topic: [Crypto-panel] Request for review: OPRFs using Prime-Order Groups Thread-Index: AQHYIi1+XK3p389gn0qVouHfTiBpTKyUZliQ Date: Tue, 15 Feb 2022 10:20:50 +0000 Message-ID: References: In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=qti.qualcomm.com; x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 089b9e7e-630c-457f-c912-08d9f06cd6e6 x-ms-traffictypediagnostic: CO1PR02MB8588:EE_ x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:7691; x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: 8bjj6woUnzh/7PCFgFlHuBxnxeRGk2k9vhMpA7nJp21cbvHuyGa4BVIc2Fhnax+osdiT9iJSdQAvwnrxnhcwxwDRuKHFjWl4Qk9uGVjkKs2gIlqfPv2luPnD4YVhZ13gr6LwnlbCJxAi79NU2WsCgl8LDTstieLdB9jry8E8coyUan4kAs505B0zAXLkk9fO5X6vmCCGMxJflh4iKv6VMqMQeJXRq5yddThoUuYgckcQhQR+FmWrEfcagsHJUZ/2tC6AxkzjCQbsOQYnPV92Sh1xzqDpTzQ7gwIQjTgdFcPrSFwUaP8DkjNxfL5Rx8lEUPcDROgo/1jpHH945cWKs/b1KYdvxnjSqmcBZd8NHNVSEkJDGTbf12XceFPwdRj31yOOoaK8G3CQoI85K2hjOPbSKlOGN/9ly5Di2WyKB4YmD9F4Kbv2te4jhV4NG5ULAUWRztWZGn1iG+lgCofCimQQiKq/ONG5Wp+f8nMNBw9INHftBi7HbW3BGWJ1gAdbKquKHpvacxsalJSUrGHhymRqPgd6tnmv38eYgCY6uJTYWoAvo6Vom6m3Wkhn69gTUg1ZoI7w5jzGntUsvQvm69zyjgA1qxKIB9khx2Bx4jWEPXGl6oewUYRHZaQPmMwSL2kaPsNAlP4chtCORZ2OzvqFdzA9PL9zyqo7tk0DbuZvC0rS4pebzPsJgVvFWmN58SVwOMy3sKSrKtjUEHjNXsGcQ0nlOr/8lSUTsO+UHxJ9Po76goPVGxv8zHVKM7s/CDs23NWP7zXXKL5k7LzWMQqyrdR0B6pJPJE9fwKVMAE= x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:BL3PR02MB7970.namprd02.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230001)(4636009)(366004)(316002)(53546011)(38070700005)(8676002)(86362001)(2906002)(4326008)(64756008)(8936002)(66556008)(66446008)(66476007)(83380400001)(76116006)(66946007)(166002)(122000001)(55016003)(186003)(26005)(508600001)(6506007)(9686003)(7696005)(33656002)(4744005)(71200400001)(38100700002)(110136005)(9326002)(5660300002)(52536014); DIR:OUT; SFP:1102; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?utf-8?B?U3Q4RWVJeU04bWJmZnRuVnl4amcvQW5VU1Y3MUYrRk4yZjFXS3ZoV1ZMTis4?= =?utf-8?B?ZzRLU00rTWZBOHZIUzhUOFRic0pEdmRtVERaUjlsSHdzYVJMZkJCWUlHSGhy?= =?utf-8?B?TWR3cEF0d1hLYi9EU3YwQ1BBMG45MjA2bXVzb2Iyd2l4c3FWdHI4N3EwcXd0?= =?utf-8?B?Qm1VRFc1NjF3dG9Pb2o2eTU4Y0dacURmalU0czhJYjBTTEFsUy9nSVBUNzdZ?= =?utf-8?B?ZjFEZzB6dytiUVVPMUxsaXpYTEVaZis2czhFbVgzMksvYmRIMEhRempmNEly?= =?utf-8?B?TE9rMGhDbHFuOVhka3NXcjJ5dUhjRVdGY3FZNW15RlFtY2YxT01YWWc1Z0Zq?= =?utf-8?B?SFlSbnQ4bmFPK2lSSzlaNGlJUmhZQXR0VUpxVTNtcHJKVmp0SFhPLytrYkR0?= =?utf-8?B?ZkNWMFFwUlpJejNQelFFTkZ6NTdSZGMyaUZMR1Z2MDZIcWhML21zMjd6am9H?= =?utf-8?B?RjV1eXFlR2dmZXVMQU9ZNkZIblhFTG1peGNub2Z4Vzl2U2JtWE5FcWlNUlcr?= =?utf-8?B?bG9INkNwTFVGam03dlAyVGxLd2MrcFlQV3NCdEdCcUd0MStnVWtmOEhmMkpr?= =?utf-8?B?UkJleXcvaHd2UFBqR0E1VzRtdXZlMmdmTFJwbnFSZHRpOXovMnAwd2FTSEZX?= =?utf-8?B?WUJSNVFVbGtsSXBOV2FqMTBqV09URWtvV3lraVpBaHZ6R0d4T3VsR01ZRFI3?= =?utf-8?B?bW5aOUsrWDlJMDN0ZWVMWCt0R1puZ3ZaQ3pQVjRZV0hoUE9nOHp4WEN3SzZW?= =?utf-8?B?YWljc21XMmlnU0lwMzNhSk5NL1Z3VXhDSnAxSDlqTDZnTXVWWGE4d2hRSW9r?= =?utf-8?B?bkNTa3BYci8wVUZZT1RNb2ZaZjluQzNuYW4vLzdJYnFsNzVubldzaUVocEEv?= =?utf-8?B?cWNVU011V0NhcEdJQVVieWllaDRZRnN2RGtlNHNsZFZaOExPaXJWQzJ0NnFZ?= =?utf-8?B?bDRKL1JkZ1pYVmVKcHJrOHBVa1ZRazZPdFBkQWZCMURhLzlwbURNTDQ5S2Qy?= =?utf-8?B?SWg0QnpwOHRVRC9najVTWEZ5UkpKVktEZzMxVzN6Y3M0VUN6Q2J3L3BZbTVB?= =?utf-8?B?dk9YYk50d3R5ejNxcmN4dGM0SVA4TjE0dHlRYUR2ZU9XYzdlc09KS3F2Rm4w?= =?utf-8?B?ZTJrK1pmbGRjcFlFUVE0Y2JscDE0bGtFblZ4Tk1vOG1yWW9TQmZQNnNKdEJI?= =?utf-8?B?dnlUTXZZNjZjc3FnMUNnOG9nOFE4N09uM1BQMW9DanY1QlQycGhQYnptY3pa?= =?utf-8?B?RTVhaDJLakhVQXpQckgrZFpYV3RMZmlibTNpMEVQMlVPS1lHcCtQb3EzWGdD?= =?utf-8?B?OFp3bjN3UW1jZCtKVGwrS1Q4dlhNZWt5bUtubWJyZTdlYjU0cTVaSW9xU1NC?= =?utf-8?B?SVN6OU5ORG9haEFsN21xeWNTYVlTVDZ1d0lBdXRFaWxUK0JLRHhveGp5bUhj?= =?utf-8?B?T3dOUnp1QXorcXlHV290ZGJnWGdQZyt0RXpyTlliZ0VwdWoxWGZObS9iNUFs?= =?utf-8?B?RU9hdjY3YVVBMmVkS29jZ0RKTnRzaEhwKzJGUmg0L1J0aHVsM3FkaFZGQ0Jj?= =?utf-8?B?UWh3N2QyeFVGa1NIUGxMRlVkdlZwdE85bmY2dmNlbnNzN2tON1dWSTBNT3My?= =?utf-8?B?aHhXR2xnRFJJMmYvVEZSU3ZuSFdVVVdRNnZSSllCTnY4eTBiYXYzc3VyMytz?= =?utf-8?B?WmswZFVoMFVld3phWG1EdW81YkNjVUtObjlTNTFpNmVJY0xiNktGc3VnaVdo?= =?utf-8?B?dENlUDhHMHpLVkZuczAvbmxDZW8xLzNzU2NzaDBKMlUyVUJWMEIrWlZTbXk1?= =?utf-8?B?RjdFQ29qSUFNUXJEVVR6Q2dldzhiTFAySXJuWld3WktHeTBEWEduVVk5aXJv?= =?utf-8?B?R3pheDRuZlNlQTQ2RFFudU9Eekh3ZkdTN2VybEZTV010QzlVNDNxMUtIUWNG?= =?utf-8?B?T094SEpvQ2ZxVnhlK3lZME1MOWgxL0VwK05IZ0c4amRoOGMwTnFldjZMRW9T?= =?utf-8?B?ZytDaHc0VEpjaVBOS3k0Y3ZQR0RqSzN2WmlyaTN0ZHpQaENJODAzdG5lSHJQ?= =?utf-8?B?azk0bHpoMEhxUFBhL1AySFk5RVJUWXJjS3Y5SUh0VUxZclpRL2NISUNpU2Vt?= =?utf-8?B?T1VKOVVodWFIMUlYZ3FpSU1UZnRQUWY0L1lJOW1JV0o4YUtVZHBrbmFmZXBw?= =?utf-8?B?SEpkOWZiSkg2SkNtdHFxS0dIVEJFbE5qcit0by9UVVBPMm4rQWdHcmUybkYv?= =?utf-8?B?KzFSd1R2TVRYYmdYeExSdFZnQUhBPT0=?= Content-Type: multipart/alternative; boundary="_000_BL3PR02MB79703D3668B972C06467813DE3349BL3PR02MB7970namp_" MIME-Version: 1.0 X-OriginatorOrg: qti.qualcomm.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: BL3PR02MB7970.namprd02.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 089b9e7e-630c-457f-c912-08d9f06cd6e6 X-MS-Exchange-CrossTenant-originalarrivaltime: 15 Feb 2022 10:20:50.1125 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 98e9ba89-e1a1-4e38-9007-8bdabc25de1d X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: u7T0L0VvbmxO2Gp9w63YCYta3JilZ1bIkcf/MIeKJUJIl7A/dj7bvJSxuFPU82Fc4jGc64bbhJkjnE5wEwzMJ0lFj1/Gu3PCHFv1S2kgKF0= X-MS-Exchange-Transport-CrossTenantHeadersStamped: CO1PR02MB8588 Archived-At: Subject: Re: [Crypto-panel] Request for review: OPRFs using Prime-Order Groups X-BeenThere: crypto-panel@irtf.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 15 Feb 2022 10:21:01 -0000 --_000_BL3PR02MB79703D3668B972C06467813DE3349BL3PR02MB7970namp_ Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 SGkgU3RhbmlzbGF2LA0KDQpJIHdvdWxkIGxpa2UgdG8gcmV2aWV3IHRoaXMgZHJhZnQuIEluIHRl cm1zIG9mIHRpbWUsIHRoaXMgYW5kIHRoZSBuZXh0IHdlZWsgYXJlIGV4dHJlbWVseSBidXN5IGZv ciBtZSwgc28gdGhlIGVhcmxpZXN0IEkgY291bGQgZG8gd291bGQgYmUgRnJpZGF5LCBNYXJjaCAx MXRoLiBQbGVhc2UgbGV0IG1lIGtub3cgaWYgdGhhdCB3b3VsZCB3b3JrLg0KDQpSZWdhcmRzLA0K VmlyZW5kcmENCg0KRnJvbTogQ3J5cHRvLXBhbmVsIDxjcnlwdG8tcGFuZWwtYm91bmNlc0BpcnRm Lm9yZz4gT24gQmVoYWxmIE9mIFN0YW5pc2xhdiBWLiBTbXlzaGx5YWV2DQpTZW50OiBUdWVzZGF5 LCBGZWJydWFyeSAxNSwgMjAyMiAxMjozNCBBTQ0KVG86IGNyeXB0by1wYW5lbEBpcnRmLm9yZw0K Q2M6IGNmcmctY2hhaXJzQGlldGYub3JnDQpTdWJqZWN0OiBbQ3J5cHRvLXBhbmVsXSBSZXF1ZXN0 IGZvciByZXZpZXc6IE9QUkZzIHVzaW5nIFByaW1lLU9yZGVyIEdyb3Vwcw0KDQoNCldBUk5JTkc6 IFRoaXMgZW1haWwgb3JpZ2luYXRlZCBmcm9tIG91dHNpZGUgb2YgUXVhbGNvbW0uIFBsZWFzZSBi ZSB3YXJ5IG9mIGFueSBsaW5rcyBvciBhdHRhY2htZW50cywgYW5kIGRvIG5vdCBlbmFibGUgbWFj cm9zLg0KRGVhciBDcnlwdG8gUGFuZWwgRXhwZXJ0cywNCg0KVGhlIGNoYWlycyB3b3VsZCBsaWtl IHRvIGFzayB0aGUgQ3J5cHRvIFBhbmVsIHRvIHByb3ZpZGUgYSByZXZpZXcgZm9yIHZlcnNpb24g LTA5IG9mIHRoZSAiT2JsaXZpb3VzIFBzZXVkb3JhbmRvbSBGdW5jdGlvbnMgKE9QUkZzKSB1c2lu ZyBQcmltZS1PcmRlciBHcm91cHMiIGRyYWZ0LCBkcmFmdC1pcnRmLWNmcmctdm9wcmYtMDkgKGh0 dHBzOi8vZGF0YXRyYWNrZXIuaWV0Zi5vcmcvZG9jL2h0bWwvZHJhZnQtaXJ0Zi1jZnJnLXZvcHJm LTA5KS4NCg0KDQpBbnkgdm9sdW50ZWVycz8NCg0KU3RhbmlzbGF2IChvbiBiZWhhbGYgb2YgdGhl IENGUkcgQ2hhaXJzKQ0KDQo= --_000_BL3PR02MB79703D3668B972C06467813DE3349BL3PR02MB7970namp_ Content-Type: text/html; charset="utf-8" Content-Transfer-Encoding: base64 PGh0bWwgeG1sbnM6dj0idXJuOnNjaGVtYXMtbWljcm9zb2Z0LWNvbTp2bWwiIHhtbG5zOm89InVy bjpzY2hlbWFzLW1pY3Jvc29mdC1jb206b2ZmaWNlOm9mZmljZSIgeG1sbnM6dz0idXJuOnNjaGVt YXMtbWljcm9zb2Z0LWNvbTpvZmZpY2U6d29yZCIgeG1sbnM6bT0iaHR0cDovL3NjaGVtYXMubWlj cm9zb2Z0LmNvbS9vZmZpY2UvMjAwNC8xMi9vbW1sIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcv VFIvUkVDLWh0bWw0MCI+DQo8aGVhZD4NCjxtZXRhIGh0dHAtZXF1aXY9IkNvbnRlbnQtVHlwZSIg Y29udGVudD0idGV4dC9odG1sOyBjaGFyc2V0PXV0Zi04Ij4NCjxtZXRhIG5hbWU9IkdlbmVyYXRv ciIgY29udGVudD0iTWljcm9zb2Z0IFdvcmQgMTUgKGZpbHRlcmVkIG1lZGl1bSkiPg0KPHN0eWxl PjwhLS0NCi8qIEZvbnQgRGVmaW5pdGlvbnMgKi8NCkBmb250LWZhY2UNCgl7Zm9udC1mYW1pbHk6 IkNhbWJyaWEgTWF0aCI7DQoJcGFub3NlLTE6MiA0IDUgMyA1IDQgNiAzIDIgNDt9DQpAZm9udC1m YWNlDQoJe2ZvbnQtZmFtaWx5OkNhbGlicmk7DQoJcGFub3NlLTE6MiAxNSA1IDIgMiAyIDQgMyAy IDQ7fQ0KLyogU3R5bGUgRGVmaW5pdGlvbnMgKi8NCnAuTXNvTm9ybWFsLCBsaS5Nc29Ob3JtYWws IGRpdi5Nc29Ob3JtYWwNCgl7bWFyZ2luOjBpbjsNCglmb250LXNpemU6MTEuMHB0Ow0KCWZvbnQt ZmFtaWx5OiJDYWxpYnJpIixzYW5zLXNlcmlmO30NCmE6bGluaywgc3Bhbi5Nc29IeXBlcmxpbmsN Cgl7bXNvLXN0eWxlLXByaW9yaXR5Ojk5Ow0KCWNvbG9yOmJsdWU7DQoJdGV4dC1kZWNvcmF0aW9u OnVuZGVybGluZTt9DQpzcGFuLmdtYWlsLWlsDQoJe21zby1zdHlsZS1uYW1lOmdtYWlsLWlsO30N CnNwYW4uRW1haWxTdHlsZTIxDQoJe21zby1zdHlsZS10eXBlOnBlcnNvbmFsLXJlcGx5Ow0KCWZv bnQtZmFtaWx5OiJDYWxpYnJpIixzYW5zLXNlcmlmOw0KCWNvbG9yOndpbmRvd3RleHQ7fQ0KLk1z b0NocERlZmF1bHQNCgl7bXNvLXN0eWxlLXR5cGU6ZXhwb3J0LW9ubHk7DQoJZm9udC1zaXplOjEw LjBwdDt9DQpAcGFnZSBXb3JkU2VjdGlvbjENCgl7c2l6ZTo4LjVpbiAxMS4waW47DQoJbWFyZ2lu OjEuMGluIDEuMGluIDEuMGluIDEuMGluO30NCmRpdi5Xb3JkU2VjdGlvbjENCgl7cGFnZTpXb3Jk U2VjdGlvbjE7fQ0KLS0+PC9zdHlsZT48IS0tW2lmIGd0ZSBtc28gOV0+PHhtbD4NCjxvOnNoYXBl ZGVmYXVsdHMgdjpleHQ9ImVkaXQiIHNwaWRtYXg9IjEwMjYiIC8+DQo8L3htbD48IVtlbmRpZl0t LT48IS0tW2lmIGd0ZSBtc28gOV0+PHhtbD4NCjxvOnNoYXBlbGF5b3V0IHY6ZXh0PSJlZGl0Ij4N CjxvOmlkbWFwIHY6ZXh0PSJlZGl0IiBkYXRhPSIxIiAvPg0KPC9vOnNoYXBlbGF5b3V0PjwveG1s PjwhW2VuZGlmXS0tPg0KPC9oZWFkPg0KPGJvZHkgbGFuZz0iRU4tVVMiIGxpbms9ImJsdWUiIHZs aW5rPSJwdXJwbGUiIHN0eWxlPSJ3b3JkLXdyYXA6YnJlYWstd29yZCI+DQo8ZGl2IGNsYXNzPSJX b3JkU2VjdGlvbjEiPg0KPHAgY2xhc3M9Ik1zb05vcm1hbCI+SGkgU3RhbmlzbGF2LDxvOnA+PC9v OnA+PC9wPg0KPHAgY2xhc3M9Ik1zb05vcm1hbCI+PG86cD4mbmJzcDs8L286cD48L3A+DQo8cCBj bGFzcz0iTXNvTm9ybWFsIj5JIHdvdWxkIGxpa2UgdG8gcmV2aWV3IHRoaXMgZHJhZnQuIEluIHRl cm1zIG9mIHRpbWUsIHRoaXMgYW5kIHRoZSBuZXh0IHdlZWsgYXJlIGV4dHJlbWVseSBidXN5IGZv ciBtZSwgc28gdGhlIGVhcmxpZXN0IEkgY291bGQgZG8gd291bGQgYmUgRnJpZGF5LCBNYXJjaCAx MTxzdXA+dGg8L3N1cD4uIFBsZWFzZSBsZXQgbWUga25vdyBpZiB0aGF0IHdvdWxkIHdvcmsuPG86 cD48L286cD48L3A+DQo8cCBjbGFzcz0iTXNvTm9ybWFsIj48bzpwPiZuYnNwOzwvbzpwPjwvcD4N CjxwIGNsYXNzPSJNc29Ob3JtYWwiPlJlZ2FyZHMsPG86cD48L286cD48L3A+DQo8cCBjbGFzcz0i TXNvTm9ybWFsIj5WaXJlbmRyYTxvOnA+PC9vOnA+PC9wPg0KPHAgY2xhc3M9Ik1zb05vcm1hbCI+ PG86cD4mbmJzcDs8L286cD48L3A+DQo8ZGl2Pg0KPGRpdiBzdHlsZT0iYm9yZGVyOm5vbmU7Ym9y ZGVyLXRvcDpzb2xpZCAjRTFFMUUxIDEuMHB0O3BhZGRpbmc6My4wcHQgMGluIDBpbiAwaW4iPg0K PHAgY2xhc3M9Ik1zb05vcm1hbCI+PGI+RnJvbTo8L2I+IENyeXB0by1wYW5lbCAmbHQ7Y3J5cHRv LXBhbmVsLWJvdW5jZXNAaXJ0Zi5vcmcmZ3Q7IDxiPg0KT24gQmVoYWxmIE9mIDwvYj5TdGFuaXNs YXYgVi4gU215c2hseWFldjxicj4NCjxiPlNlbnQ6PC9iPiBUdWVzZGF5LCBGZWJydWFyeSAxNSwg MjAyMiAxMjozNCBBTTxicj4NCjxiPlRvOjwvYj4gY3J5cHRvLXBhbmVsQGlydGYub3JnPGJyPg0K PGI+Q2M6PC9iPiBjZnJnLWNoYWlyc0BpZXRmLm9yZzxicj4NCjxiPlN1YmplY3Q6PC9iPiBbQ3J5 cHRvLXBhbmVsXSBSZXF1ZXN0IGZvciByZXZpZXc6IE9QUkZzIHVzaW5nIFByaW1lLU9yZGVyIEdy b3VwczxvOnA+PC9vOnA+PC9wPg0KPC9kaXY+DQo8L2Rpdj4NCjxwIGNsYXNzPSJNc29Ob3JtYWwi PjxvOnA+Jm5ic3A7PC9vOnA+PC9wPg0KPHAgYWxpZ249ImNlbnRlciIgc3R5bGU9InRleHQtYWxp Z246Y2VudGVyIj48c3Ryb25nPjxzcGFuIHN0eWxlPSJmb250LXNpemU6MTAuNXB0O2ZvbnQtZmFt aWx5OiZxdW90O0FyaWFsJnF1b3Q7LHNhbnMtc2VyaWY7Y29sb3I6YmxhY2s7YmFja2dyb3VuZDp5 ZWxsb3ciPldBUk5JTkc6PC9zcGFuPjwvc3Ryb25nPjxzcGFuIHN0eWxlPSJmb250LXNpemU6MTAu NXB0O2ZvbnQtZmFtaWx5OiZxdW90O0FyaWFsJnF1b3Q7LHNhbnMtc2VyaWY7Y29sb3I6YmxhY2s7 YmFja2dyb3VuZDp5ZWxsb3ciPg0KIFRoaXMgZW1haWwgb3JpZ2luYXRlZCBmcm9tIG91dHNpZGUg b2YgUXVhbGNvbW0uIFBsZWFzZSBiZSB3YXJ5IG9mIGFueSBsaW5rcyBvciBhdHRhY2htZW50cywg YW5kIGRvIG5vdCBlbmFibGUgbWFjcm9zLjwvc3Bhbj48bzpwPjwvbzpwPjwvcD4NCjxkaXY+DQo8 ZGl2Pg0KPGRpdj4NCjxwIGNsYXNzPSJNc29Ob3JtYWwiPkRlYXImbmJzcDs8c3BhbiBjbGFzcz0i Z21haWwtaWwiPkNyeXB0bzwvc3Bhbj4mbmJzcDs8c3BhbiBjbGFzcz0iZ21haWwtaWwiPlBhbmVs PC9zcGFuPiZuYnNwO0V4cGVydHMsPG86cD48L286cD48L3A+DQo8L2Rpdj4NCjxkaXY+DQo8ZGl2 Pg0KPHAgY2xhc3M9Ik1zb05vcm1hbCI+PG86cD4mbmJzcDs8L286cD48L3A+DQo8L2Rpdj4NCjxk aXY+DQo8cCBjbGFzcz0iTXNvTm9ybWFsIj5UaGUgY2hhaXJzIHdvdWxkIGxpa2UgdG8gYXNrIHRo ZSZuYnNwOzxzcGFuIGNsYXNzPSJnbWFpbC1pbCI+Q3J5cHRvPC9zcGFuPiZuYnNwOzxzcGFuIGNs YXNzPSJnbWFpbC1pbCI+UGFuZWw8L3NwYW4+Jm5ic3A7dG8gcHJvdmlkZSBhIHJldmlldyBmb3Ig dmVyc2lvbiAtMDkgb2YgdGhlICZxdW90O09ibGl2aW91cyBQc2V1ZG9yYW5kb20gRnVuY3Rpb25z IChPUFJGcykgdXNpbmcgUHJpbWUtT3JkZXIgR3JvdXBzJnF1b3Q7IGRyYWZ0LCBkcmFmdC1pcnRm LWNmcmctdm9wcmYtMDkNCiAoPGEgaHJlZj0iaHR0cHM6Ly9kYXRhdHJhY2tlci5pZXRmLm9yZy9k b2MvaHRtbC9kcmFmdC1pcnRmLWNmcmctdm9wcmYtMDkiPmh0dHBzOi8vZGF0YXRyYWNrZXIuaWV0 Zi5vcmcvZG9jL2h0bWwvZHJhZnQtaXJ0Zi1jZnJnLXZvcHJmLTA5PC9hPikuPG86cD48L286cD48 L3A+DQo8L2Rpdj4NCjxkaXY+DQo8cCBjbGFzcz0iTXNvTm9ybWFsIj48bzpwPiZuYnNwOzwvbzpw PjwvcD4NCjwvZGl2Pg0KPGRpdj4NCjxwIGNsYXNzPSJNc29Ob3JtYWwiPjxicj4NCkFueSB2b2x1 bnRlZXJzPzxicj4NCjxicj4NClN0YW5pc2xhdiAob24gYmVoYWxmIG9mIHRoZSBDRlJHIENoYWly cykgPG86cD48L286cD48L3A+DQo8ZGl2Pg0KPHAgY2xhc3M9Ik1zb05vcm1hbCI+PG86cD4mbmJz cDs8L286cD48L3A+DQo8L2Rpdj4NCjwvZGl2Pg0KPC9kaXY+DQo8L2Rpdj4NCjwvZGl2Pg0KPC9k aXY+DQo8L2JvZHk+DQo8L2h0bWw+DQo= --_000_BL3PR02MB79703D3668B972C06467813DE3349BL3PR02MB7970namp_-- From nobody Tue Feb 15 02:43:44 2022 Return-Path: X-Original-To: crypto-panel@ietfa.amsl.com Delivered-To: crypto-panel@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D7EC53A0C0D for ; Tue, 15 Feb 2022 02:43:41 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.097 X-Spam-Level: X-Spam-Status: No, score=-2.097 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, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=unavailable 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 4SIavrwNTsQ4 for ; Tue, 15 Feb 2022 02:43:37 -0800 (PST) Received: from mail-ej1-x633.google.com (mail-ej1-x633.google.com [IPv6:2a00:1450:4864:20::633]) (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 4CE133A0C25 for ; Tue, 15 Feb 2022 02:43:37 -0800 (PST) Received: by mail-ej1-x633.google.com with SMTP id k25so43268975ejp.5 for ; Tue, 15 Feb 2022 02:43:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=yn0ZDX6YlThCoBzkjFk1kjXuJKMhxjEnEvpFQXzI2UI=; b=GlDbk5FYV4TK0xEYIkrGeP7WBxIB3S0sKx8JTHavOnjUZWsnoIKQPGUFOISjzI8XWJ qEC1rQ31sjhNTbX1SP2ILFnbdEPdDgSbxslE0PHa6+04A1eQPe6tneY3+YMklTzGwDjr kPGGmQcZUCxDGOvkxSeZb3isnP1IEwbyT4Wl2aQ9Iz1wG7D6iwL8gyX9vaEf/LWcBWeR M362TBkPNQkk8RoWXkNvRpho9EEjZ5N3NjkgkQolv9CNVVwr9kP3vOvsVf5vr/gtcDU9 jNH7nn6Zqu3/9IzfRZMdTo8EhSH3OW9SWrNYrwtG2z/rmZ89Q5VIOjSBH9YJQYnhapzA cT2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=yn0ZDX6YlThCoBzkjFk1kjXuJKMhxjEnEvpFQXzI2UI=; b=MhMFfEnBN9HAp8O3G2uTJHBlvF+gh5lWDO0BtMNQpZg8a5GRB/0HlvDIDrSd2eXXQn Umqvet6wEaKctmvew9eB7yZK5JuSGuEycgGflT3OTCKPnzMZPBQDTTAc7IxBXw92cTm7 ix+L3adnZA1AsJg+K1WyLacgKD+67deJP4T9wT5lRpnBIKjo0aEicYhb1Ww2sZCttpVz jXsOZobziOAIDCTpLXhbuXW2C9VUYogbk261u6NiyLcFJNiJdHuR4wM0fIrMzZtrT6sn MaKkdFWdnvshK0DtQfqQ4O+JengsjjMxC6VJeK0m7JoxAe4x5GHS6rqIlJR9hiI5uxvZ rhfA== X-Gm-Message-State: AOAM533Yuj2FBS/DcbUiMarsWm1VvvhleIr605Cent4+7aQHDsiVJdT9 Vo1al7lon0LZcNSb2DrQ3mGCBpm8SqIB5Ylvfnb6JiFDa6taKw== X-Google-Smtp-Source: ABdhPJx5LitwTuiAkswfaKvLN63l336UL+45mnMRNcfLUuodGCR0QSQ8AdbYMY/7FaYczTqWFt+O4RjiBB60oDjmv60= X-Received: by 2002:a17:906:7316:: with SMTP id di22mr2446437ejc.211.1644921814037; Tue, 15 Feb 2022 02:43:34 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: "Stanislav V. Smyshlyaev" Date: Tue, 15 Feb 2022 13:44:44 +0300 Message-ID: To: Virendra Kumar Cc: "crypto-panel@irtf.org" , "cfrg-chairs@ietf.org" Content-Type: multipart/alternative; boundary="00000000000068b95e05d80c34e8" Archived-At: Subject: Re: [Crypto-panel] Request for review: OPRFs using Prime-Order Groups X-BeenThere: crypto-panel@irtf.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 15 Feb 2022 10:43:42 -0000 --00000000000068b95e05d80c34e8 Content-Type: text/plain; charset="UTF-8" >> I would like to review this draft. Thank you, Virendra! >> Please let me know if that would work. Yes, three weeks (or so) is a fine time period for review. Thank you, we'll be waiting for a review! Please send it to cfrg@irtf.org (CC'ing cfrg-chairs@ietf.org and draft-irtf-cfrg-voprf@ietf.org), when it is ready. Regards, Stanislav On Tue, 15 Feb 2022 at 13:20, Virendra Kumar wrote: > Hi Stanislav, > > > > I would like to review this draft. In terms of time, this and the next > week are extremely busy for me, so the earliest I could do would be Friday, > March 11th. Please let me know if that would work. > > > > Regards, > > Virendra > > > > *From:* Crypto-panel * On Behalf Of *Stanislav > V. Smyshlyaev > *Sent:* Tuesday, February 15, 2022 12:34 AM > *To:* crypto-panel@irtf.org > *Cc:* cfrg-chairs@ietf.org > *Subject:* [Crypto-panel] Request for review: OPRFs using Prime-Order > Groups > > > > *WARNING:* This email originated from outside of Qualcomm. Please be wary > of any links or attachments, and do not enable macros. > > Dear Crypto Panel Experts, > > > > The chairs would like to ask the Crypto Panel to provide a review for > version -09 of the "Oblivious Pseudorandom Functions (OPRFs) using > Prime-Order Groups" draft, draft-irtf-cfrg-voprf-09 ( > https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-voprf-09). > > > > > Any volunteers? > > Stanislav (on behalf of the CFRG Chairs) > > > --00000000000068b95e05d80c34e8 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
>> I would like to review this draft.
=
Thank you, Virendra!

>>=C2=A0 Please let me know if that would work.
Yes, three weeks (or so) is a fi= ne time period for review.

Thank you, we'l= l be waiting for a review! Please send it to cfrg@irtf.org (CC'ing cf= rg-chairs@ietf.org and draft-irtf-cfrg-voprf@ietf.org), when it is ready.

Regards,
Stanislav


On Tue, 15 Feb 2022= at 13:20, Virendra Kumar <= virendra@qti.qualcomm.com> wrote:

Hi Stanislav,

=C2=A0

I would like to review this draft. In terms of time,= this and the next week are extremely busy for me, so the earliest I could = do would be Friday, March 11th. Please let me know if that would= work.

=C2=A0

Regards,

Virendra

=C2=A0

=C2=A0

WA= RNING: This email originated from outside of Qualcomm. Please be wary of any link= s or attachments, and do not enable macros.

Dear=C2=A0Crypto=C2=A0Panel=C2=A0Experts,

=C2=A0

The chairs would like to ask the=C2=A0Crypto=C2=A0Panel=C2=A0to provide a review for= version -09 of the "Oblivious Pseudorandom Functions (OPRFs) using Pr= ime-Order Groups" draft, draft-irtf-cfrg-voprf-09 (https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-v= oprf-09).

=C2=A0


Any volunteers?

Stanislav (on behalf of the CFRG Chairs)

=C2=A0

--00000000000068b95e05d80c34e8-- From nobody Fri Feb 25 05:50:16 2022 Return-Path: X-Original-To: crypto-panel@ietfa.amsl.com Delivered-To: crypto-panel@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0CA043A11FA; Fri, 25 Feb 2022 05:50:06 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -0.998 X-Spam-Level: X-Spam-Status: No, score=-0.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, BITCOIN_OBFU_SUBJ=1, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_BLOCKED=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=filippo.io header.b=MS0+Qz8s; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=njEoAx5a 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 reVKxHCAYZpY; Fri, 25 Feb 2022 05:50:01 -0800 (PST) Received: from out5-smtp.messagingengine.com (out5-smtp.messagingengine.com [66.111.4.29]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B613A3A1185; Fri, 25 Feb 2022 05:50:00 -0800 (PST) Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailout.nyi.internal (Postfix) with ESMTP id 1086F5C01E2; Fri, 25 Feb 2022 08:49:57 -0500 (EST) Received: from imap47 ([10.202.2.97]) by compute3.internal (MEProxy); Fri, 25 Feb 2022 08:49:57 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=filippo.io; h=cc :cc:content-type:date:date:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:sender:subject :subject:to:to; s=fm2; bh=kI3Y+HQETZOHzQIgyQBBkgN8oAniN877v2QZnd E3+8g=; b=MS0+Qz8sRzO04q6WS2HLVYPvi4jzdWduo1LrnWF3wTl7DsPUhTtOJ7 5z38wdCGmHcnU7QhBX9poTP0W6oIq997Y56sXCortXovDcndYgL0uoriJRdVPPoK fdrdOq/ytKcMBnQFSi6J/XeqwrUlxXsb8fo4IAneCebZzChUuFjHs/Pks5IwtY6n F48bKTA/N4OBlaUINtK3YOQ0xjqrlAy4mEnOi/cMaxnLTRAqz4ZFXjjmYj1R3jAc zRC0t3YuVvck3gwpsozmWi89ol7OvCrXwU3zaytUMTbU3uhSr7nWavxMuV0oJfVP CsCT2pH0HeXE6fiZUz1bD02yIMtOtqXQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:date:date:from:from :in-reply-to:in-reply-to:message-id:mime-version:references :reply-to:sender:subject:subject:to:to:x-me-proxy:x-me-proxy :x-me-sender:x-me-sender:x-sasl-enc; s=fm2; bh=kI3Y+HQETZOHzQIgy QBBkgN8oAniN877v2QZndE3+8g=; b=njEoAx5aa1Ok8Hps996zcbBhDFGkZVF3S ulfQKniDn5xq+BYcgpCqUMbGX2nEt+WEuJRmnHnQ69CKIA4RAWePVnYxWYEl8mzK xWZZfOw1IP4XLY0DY0JcIr24RYNtIl8qhyTm29mZ8DOIhlbYSnNoAArlK+TsVDXH Z48s4BEm4goyHqnq1APUSMX8eHrqGkWvemNBvIJz0LFtXHp0OrAFwrpx3hF22ld0 YhX68MQSzBNq0xd9ny5pCfN7x/mfsfYR4WYpTEgMCE1IXIFWSDo0fyaL4JQjITGs qBkv83H2m3n9O4+EFuja+QEx+2qPASpGrfJOZ6K4hffJ2YsHr64MQ== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvvddrleeggdehkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpefofgggkfgjfhffhffvufgtsegrtderreerredtnecuhfhrohhmpedfhfhilhhi phhpohcugggrlhhsohhruggrfdcuoehfihhlihhpphhosehmlhdrfhhilhhiphhpohdrih hoqeenucggtffrrghtthgvrhhnpeetgeefuddvleelheeggfelhffhgfdtudelhfduvddu feefvdduiedutdeujeehvdenucffohhmrghinhepihgvthhfrdhorhhgpdhgihhthhhusg drtghomhdprhhishhtrhgvthhtohdrghhrohhuphdpihhrthhfrdhorhhgnecuvehluhhs thgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepfhhilhhiphhpohesmh hlrdhfihhlihhpphhordhioh X-ME-Proxy: Received: by mailuser.nyi.internal (Postfix, from userid 501) id D842027400FA; Fri, 25 Feb 2022 08:49:56 -0500 (EST) X-Mailer: MessagingEngine.com Webmail Interface User-Agent: Cyrus-JMAP/3.5.0-alpha0-4778-g14fba9972e-fm-20220217.001-g14fba997 Mime-Version: 1.0 Message-Id: <83c4c2d3-de15-4b56-b5ab-d829aee7735c@www.fastmail.com> In-Reply-To: <164579389507.15738.2508481933777547020@ietfa.amsl.com> References: <164579389507.15738.2508481933777547020@ietfa.amsl.com> Date: Fri, 25 Feb 2022 14:49:35 +0100 From: "Filippo Valsorda" To: cfrg@irtf.org, crypto-panel@irtf.org, "Thomas Pornin" Cc: draft-irtf-cfrg-ristretto255-decaf448@ietf.org Content-Type: multipart/alternative; boundary=cf0b7d86d0d94f4e858d3fff3cfa1d16 Archived-At: Subject: Re: [Crypto-panel] [CFRG] I-D Action: draft-irtf-cfrg-ristretto255-decaf448-03.txt X-BeenThere: crypto-panel@irtf.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 25 Feb 2022 13:50:14 -0000 --cf0b7d86d0d94f4e858d3fff3cfa1d16 Content-Type: text/plain -02 and -03 address the Crypto Panel review by Thomas Pornin. Notes inline below. https://mailarchive.ietf.org/arch/msg/crypto-panel/isgCxg9ddxoPkNnOdGbwK2Z2_Cw/ Latest HTML and diff from the reviewed version. https://www.ietf.org/archive/id/draft-irtf-cfrg-ristretto255-decaf448-03.html https://tools.ietf.org/rfcdiff?url1=draft-irtf-cfrg-ristretto255-decaf448-01&url2=draft-irtf-cfrg-ristretto255-decaf448-03 Some discussion on the changes. https://github.com/cfrg/draft-irtf-cfrg-ristretto255/pull/9 https://github.com/cfrg/draft-irtf-cfrg-ristretto255/pull/11 > The ristretto255 and decaf448 Groups > draft-irtf-cfrg-ristretto255-decaf448-01 > > Overall I find this draft to be well-written and reasonable; my comments below are mostly cosmetic in nature. > > page 3: "fastest known formulas curve operations" -> I could dispute > that, at least for point doubling. I suggest: "[...] and formulas among > the fastest known for curve operations". Done. > page 4: "https://ristretto.group (https://ristretto.group)" -> I would > expect this reference to be, indeed, a reference to an entry in section 11 > ("Informative References"), where the URL would be, instead of having > the URL directly inlined (twice!) in the text. (If you don't use a > reference, the RFC editor will probably be very cross.) Done. > page 4: about curve names: it might be worth including somewhere that > what is described as "Curve25519" here is what is called "edwards25519" > in RFC 7748 (which uses "Curve25519" to designate the Montgomery curve). Done. > page 4: "the Curve25519 prime 2^255 - 19 or the edwards448 prime" -> for > symmetry of expression, if you include the value of the Curve25519 prime > (2^255 - 19), then you should also include the value of the edwards448 > prime (2^448 - 2^224 - 1). Done. > page 4: "array[A:B]" -> maybe also specify that array indices start at 0? Done. > page 5: the American spelling of "behavior" is used (and also on page 17), > whereas the British spelling ("behaviour") was used on page 3. Done. > page 5: "bytestring" -> this term is not defined in the draft; it's not > defined either in RFC 7748 or 8032. This is not an utterly obscure term, > but it is still a neologism (plain English would use "byte string" in > two words); moreover, communication protocol standards tend to prefer > the use of "octet" rather than "byte", the latter being historically > imprecise. I suggest adding a definition in section 2, e.g. something > like: "In this document, a byte is an 8-bit entity (also known as > "octet") and a bytestring is an ordered sequence of bytes." Defined "byte string" and "N-byte string" in Section 2, and used throughout. > page 6: "using Curve25519 points as internal representations" -> I think > it should be "representation" here. I think the number of "representations" is supposed to match the number of "points"? > page 6: "encoding" is a sequence of octets (a "bytestring") but here > we see a sequence of eight 8-digit hexadecimal integers. This notation > is slightly ambiguous because it does not say whether each 8-digit > integer should be converted into bytes using little-endian or big-endian > convention. Both conventions exist! (unfortunately) > > RFC 7748 uses a single sequence of 64 characters (in its test vectors), > with no internal spaces, which might be considered more reliably > defined. Defined the hex encoding with spaces in Section 2. > page 7: non-zero quadratic residues have two distinct square roots, exactly > one of them being non-negative (in the sense defined in section 2.1). The > constants SQRT_M1 = sqrt(-1) and INVSQRT_A_MINUS_D = 1/sqrt(A-D) both > use the non-negative square root, but SQRT_AD_MINUS_ONE = sqrt(A*D - 1) > uses the negative square root. Is there a specific reason for this choice? > (If a rationale is added, it would be nice to say that A = -1; this allows > verification of the values.) > (Also, it would be nice to add somewhere that the formulas leverage > the fact that A = -1 in several places and cannot be applied "as is" > on other Edwards curves where A != -1.) SQRT_AD_MINUS_ONE was generated with Sage which selects the value with the least absolute residue by default. That would be the non-negative one by the Ed448-style definition of negativity, but it's the negative one by the Ed25519-style definition. Consistency would be preferable, but changing the value (and the one-way map formula) now would lead to confusion when comparing the spec and existing implementations, which doesn't feel worth it. The rationale feels out of scope for a document aimed at implementers. It was a good discussion to have to make sure we are putting the right number into the spec, but this kind of concerns is a better fit for the paper and website referenced from the spec, along with all the formulas justifications. > page 8: "All elements are encoded as a 32-byte string" -> "All elements > [...] as 32-byte strings" (or, preferably: "as bytestrings of length > exactly 32 bytes each") Ah, missed this until now. Fixed on main. > page 9: 'the internal representation "(x, y, 1, t)"' -> up until that > point, there was not a word about representation of group elements, > except to say that there can be several, and that API consumers are > utterly prohibited from looking at them, ever. There should be a > paragraph somewhere (e.g. near the start of section 4) that says: "in this > document, the internal representation of a ristretto255 element is the > representation of a Curve25519 point in homogeneous coordinates (x, y, > z, t) as specified in section 5.1.4 of RFC 8032". Section 2 defines the coordinates format, updated with a reference to Section 5.1.4 of RFC 8032. The first paragraph of Section 4 and Section 5 defines the curve on which internal representations lie. "This document describes how to implement the ristretto255/decaf448 prime-order group using Curve25519/edwards448 points as internal representations." > page 10: is there a traditional reason why the denominator is called > "enchanted"? This is maths, not magic (despite superficial similarities, > these are distinct activities). Henry explains: "The naming is related to Mike's ingenious trick for computing the encoding in the cofactor-8 case with only a single inverse square root. Clever use of the curve equation gives a number that relates two of the quantities, called `magic` in Mike's script. I named the variable `enchanted_denominator` to reflect the fact that it had magic multiplied in." The authors are fairly unanimous in being fond of the naming. > page 10: "x = CT_SELECT(iy0 IF rotate ELSE x0)" -> maybe add a comment > there to highlight that the use of "iy0" here (and not "ix0") is > intentional and not a typo (and similarly for the next formula). Done. > page 11: In the interest of clarity, it may be worth pointing out that > the "one-way map" is not, by itself, one-way: given an output > ristretto255 element, it's not too hard to find an input 64-byte string > b that yields that element (you try random values b[0:32] and, for each, > you apply the reverse Elligator2 on P2; it will work with sufficiently > high probability that the process will complete quickly). What makes the > map one-way is the combination of the process of section 4.3.4 with a > suitable hash construction; the one-wayness is really that of the hash. > The role of the mapping of section 4.3.4 is to turn the one-way hash > output b into a close-to-uniformly distributed group element in such a > way that nobody can work out the discrete logarithm of the output > relatively to the conventional generator. Done. > page 11: "The one-way map operates an uniformly [...]" > -> "[...] operates on [...]" Done. > page 11: "on a 32-bytes string" -> "on a 32-byte string" > (or: "a string of 32 bytes") Done, and then changed on main to be "on 32-byte strings" for consistency with the element encoding sections. > page 11: "Interpret the least significant 255 bits of the string as an > integer r in little-endian representation" -> to be clear about that, > the _256_ bits are interpreted in little-endian representation, which > defines which ones of these bits are the "least significant 255 bits", > and only then is the top bit ignored. And, to be _really_ clear, the > string does not contain bits but bytes, and the transform here is not > fully specified if you do not say how the bits of a byte are to be > extracted. And you probably do not want to go there, because then you > will have to say things like "we use little-endian convention at the > byte level, but big-endian convention for bits within a byte", and a lot > of confusion lies down that path. Previously in the document, the input > _bytes_ were simply interpreted in "little-endian convention" and that > was not ambiguous as long as we simply used bytes, i.e. each byte having > a value in the 0..255 range, and we never even tried to look at > individual _bits_. > I thus suggest writing step 1 of the MAP function as: > > 1. Interpret the input bytestring as in integer in little-endian > convention, then reduce it modulo 2^255 (this is equivalent to > "masking out the most significant bit" as in [RFC7748], > section 5). The resulting integer, which is lower than 2^255, > is then further reduced modulo p, yielding a field element t. Agreed that "the least significant 255 bits of the string" is under-specified. On the other hand, we want to point implementers to the simple way to perform this operation. Changed to "mask the most significant bit in the final byte of the string" which matches the RFC 7748 language (which does not feel the need to specify the use of big-endian for bytes), and added a sub-element noting that the operation is equivalent to reduction modulo 2^255 to avoid any ambiguity. > page 12: section 4.4 uses "byte string" while the document previously > used "bytestring". Now using "byte string" throughout. See above. > page 12: the provisions on canonical encodings of scalars use "SHOULD"; > maybe that should be "MUST", for the same reasons that make canonical > encodings of group elements desirable? Otherwise, you end up with > things like malleable signatures, and Bitcoin is sad. They are SHOULD to allow reuse of existing implementations. Added a rationale and reiterated that omitting the checks is NOT RECOMMENDED. > page 12: "Given a uniformly distributed 64-byte string b [...]" -> It > might be worth saying what is the point of this paragraph. For any > integer l, one can obtain a value modulo l by taking an integer and > reducing it modulo l. What you want to express here is that IF the > source 64-byte string is uniformly distributed, THEN the result of > the reduction will be very close to uniformly distributed among > integers modulo l. > (Arguably, since l is very close to 2^252, taking an input 32-byte > string b would already yield a sufficiently uniform output for > cryptographic purposes. Using a full 64-byte input is overkill, but does > not harm much beyond the extra cost of reduction.) Precised that the purpose is to "obtain a *uniformly distributed* scalar". > page 12: "This documents" -> "This document" Done. > page 12: as on page 9, there should be a definition of the internal > representation of curve points. This is made slightly more complicated > because RFC 8032, for edwards448, uses projective coordinates (in > section 5.2.4) and not homogeneous coordinates, so you cannot simply > add a reference to that RFC. See above, defined in Section 2 and at the top of Section 5. > page 13: same remark as page 6 on expression of bytestrings as 8-digit > hexadecimal numbers. See above. > page 14: "similar to Section 5.1.3 of [RFC8032]" -> This is the wrong > section. 5.1.3 is for Curve25519; you want to reference section 5.2.3, > which is about edwards448. > Also, the formula in section 5.2.3 of RFC 8032 is different; the one > in your draft is simpler, and also correct. I don't know why RFC 8032 > used a more complicated formula. Done. > page 14: "encoded as a 56-byte string" -> "[...] as 56-byte strings" Done in main. See above. > (Note: I am not verifying the encoding formulas of section 5.3.2.) > > page 15: "encoding of s, reduced modulo p" -> since s is a field > element, it is inherently "reduced modulo p". Maybe write this as: > "encoding of the unique integer representation of s as an integer in the > 0 to p-1 range". Agreed that this is redundant, as a field element is defined in Section 2 as "values modulo p". Trimmed to just "encoding of s" for brevity. > page 16: "operates an uniformly" -> "operates on uniformly" Done. > page 16: same remark as page 11 about one-wayness. Done. See above. > (Note: I am not verifying the map formulas of section 5.3.4.) > > page 17: "byte strings" -> "bytestrings" Now using "byte string" throughout. See above. > page 17: "SHOULD" on encoding of scalars: same remark as on page 12. See above. > page 17: reducing an integer modulo l: as on page 12, there should be a > word about what is the point here. Also, one may note that a 512-bit > integer is not very much larger than the 446-bit subgroup order; but it > is still fine here because l is very close to a power of 2. This might > be worth a comment (otherwise, one might imagine that the paragraph was > copy&pasted from the one in section 4.4, and that the "64" is a typo). Like above, precised that the purpose is to "obtain a *uniformly distributed* scalar". The bias analysis and rationale for the size was deemed out of scope for an implementer oriented document. > page 17: "they MUST NOT construct group elements except via decoding and > the one-way map" -> Actually, group operations such as adding two > elements together are also allowed ways to construct group elements. Done. > page 18: section 8 explains that decoding always returns either a valid > representation, or an error. However, some implementations may return an > error _and_ an invalid representation; this would be typical of C > implementations where the output point is written into a > caller-allocated structure, and the error code is the return value of > the function. In that case, a depressingly common implementation failure > is to ignore the error code and keep on with the invalid representation. > This might be worth an explicit warning sentence in section 8. I tried to formulate the warning, but kept failing because it felt jarring and contradictory to say "this API MUST return either X or Y" and then follow up with "if you get both X and Y, here's the precedence rule". Moreover, it boiled down to "tell your applications not to ignore the error or defeat the API!" which is not even under the draft implementer's control. I don't disagree that this might be depressingly common, but I think it's a general C shortcomings like the lack of memory safety which is out of scope for this document. > (Note: ideally I should implement everything to verify the test vectors, > but there already are existing ristretto255 and decaf448 implementations > around so I assume this has already been done. I verified most formulas, > except those of sections 5.3.2 and 5.3.4, by comparing with the published > formulas on https://ristretto.group/ and the Decaf paper.) > > Thomas As a final note, thank you for the thorough and helpful review! Cheers, Filippo 2022-02-25 13:58 GMT+01:00 internet-drafts@ietf.org: > > A New Internet-Draft is available from the on-line Internet-Drafts directories. > This draft is a work item of the Crypto Forum RG of the IRTF. > > Title : The ristretto255 and decaf448 Groups > Authors : Henry de Valence > Jack Grigg > Mike Hamburg > Isis Lovecruft > George Tankersley > Filippo Valsorda > Filename : draft-irtf-cfrg-ristretto255-decaf448-03.txt > Pages : 27 > Date : 2022-02-25 > > Abstract: > This memo specifies two prime-order groups, ristretto255 and > decaf448, suitable for safely implementing higher-level and complex > cryptographic protocols. The ristretto255 group can be implemented > using Curve25519, allowing existing Curve25519 implementations to be > reused and extended to provide a prime-order group. Likewise, the > decaf448 group can be implemented using edwards448. > > > The IETF datatracker status page for this draft is: > https://datatracker.ietf.org/doc/draft-irtf-cfrg-ristretto255-decaf448/ > > There is also an HTML version available at: > https://www.ietf.org/archive/id/draft-irtf-cfrg-ristretto255-decaf448-03.html > > A diff from the previous version is available at: > https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-ristretto255-decaf448-03 > > > Internet-Drafts are also available by rsync at rsync.ietf.org::internet-drafts > > > _______________________________________________ > CFRG mailing list > CFRG@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg > --cf0b7d86d0d94f4e858d3fff3cfa1d16 Content-Type: text/html Content-Transfer-Encoding: quoted-printable
The ristretto255 and decaf448 = Groups
draft-irtf-cfrg-ristretto255-decaf448-01
<= /div>

Overall I find this draft to be well-written an= d reasonable; my comments below are mostly cosmetic in nature.
=

page 3: "fastest known formulas curve operations" -&= gt; I could dispute
that, at least for point doubling. I s= uggest: "[...] and formulas among
the fastest known for cu= rve operations".

Done.

= expect this reference to be, indeed, a reference to an entry in section = 11
("Informative References"), where the URL would be, ins= tead of having
the URL directly inlined (twice!) in the te= xt. (If you don't use a
reference, the RFC editor will pro= bably be very cross.)

Done.

page 4: about curve= names: it might be worth including somewhere that
what is= described as "Curve25519" here is what is called "edwards25519"
in RFC 7748 (which uses "Curve25519" to designate the Montgomery = curve).

Done.
page 4: "the Curve25519 prime 2^2= 55 - 19 or the edwards448 prime" -> for
symmetry of exp= ression, if you include the value of the Curve25519 prime
= (2^255 - 19), then you should also include the value of the edwards448
prime (2^448 - 2^224 - 1).

<= /div>
Done.

p= age 4: "array[A:B]" -> maybe also specify that array indices start at= 0?

Done.

page 5: the American spelling of "beh= avior" is used (and also on page 17),
whereas the British = spelling ("behaviour") was used on page 3.
Done.

page 5: "bytestring" -> this term is not defined in the draft; it's= not
defined either in RFC 7748 or 8032. This is not an ut= terly obscure term,
but it is still a neologism (plain Eng= lish would use "byte string" in
two words); moreover, comm= unication protocol standards tend to prefer
the use of "oc= tet" rather than "byte", the latter being historically
imp= recise. I suggest adding a definition in section 2, e.g. something
like: "In this document, a byte is an 8-bit entity (also known = as
"octet") and a bytestring is an ordered sequence of byt= es."

Defined "byte string" and= "N-byte string" in Section 2, and used throughout.

page 6: "using Curve25519 points as i= nternal representations" -> I think
it should be "repre= sentation" here.

I think the n= umber of "representations" is supposed to match the number of "points"?<= br>

page 6: "encoding= " is a sequence of octets (a "bytestring") but here
we see= a sequence of eight 8-digit hexadecimal integers. This notation
is slightly ambiguous because it does not say whether each 8-digi= t
integer should be converted into bytes using little-endi= an or big-endian
convention. Both conventions exist! (unfo= rtunately)

RFC 7748 uses a single sequence = of 64 characters (in its test vectors),
with no internal s= paces, which might be considered more reliably
defined.

Defined the hex encoding with sp= aces in Section 2.

page 7: non-zero quadratic residues have two distinct square roots, ex= actly
one of them being non-negative (in the sense defined= in section 2.1). The
constants SQRT_M1 =3D sqrt(-1) and I= NVSQRT_A_MINUS_D =3D 1/sqrt(A-D) both
use the non-negative= square root, but SQRT_AD_MINUS_ONE =3D sqrt(A*D - 1)
uses= the negative square root. Is there a specific reason for this choice?
(If a rationale is added, it would be nice to say that A =3D= -1; this allows
verification of the values.)
(Also, it would be nice to add somewhere that the formulas leverage
the fact that A =3D -1 in several places and cannot be appli= ed "as is"
on other Edwards curves where A !=3D -1.)

SQRT_AD_MINUS_ONE was generated wit= h Sage which selects the value with the least absolute residue by defaul= t. That would be the non-negative one by the Ed448-style definition of n= egativity, but it's the negative one by the Ed25519-style definition. Co= nsistency would be preferable, but changing the value (and the one-way m= ap formula) now would lead to confusion when comparing the spec and exis= ting implementations, which doesn't feel worth it.

The rationale feels out of scope for a document aimed at impleme= nters. It was a good discussion to have to make sure we are putting the = right number into the spec, but this kind of concerns is a better fit fo= r the paper and website referenced from the spec, along with all the for= mulas justifications.

=
page 8: "All elements are encoded as a 32-byte string" -> "All e= lements
[...] as 32-byte strings" (or, preferably: "as byt= estrings of length
exactly 32 bytes each")

Ah, missed this until now. Fixed on main.

page 9: 'the internal representation "(x, y, 1,= t)"' -> up until that
point, there was not a word abou= t representation of group elements,
except to say that the= re can be several, and that API consumers are
utterly proh= ibited from looking at them, ever. There should be a
parag= raph somewhere (e.g. near the start of section 4) that says: "in this
document, the internal representation of a ristretto255 elem= ent is the
representation of a Curve25519 point in homogen= eous coordinates (x, y,
z, t) as specified in section 5.1.= 4 of RFC 8032".

Section 2 defi= nes the coordinates format, updated with a reference to Section 5.1.4 of= RFC 8032. The first paragraph of Section 4 and Section 5 defines the cu= rve on which internal representations lie.

= "This document describes how to implement the ristretto255/decaf448 prim= e-order group using Curve25519/edwards448 points as internal representat= ions."

page 10: i= s there a traditional reason why the denominator is called
"enchanted"? This is maths, not magic (despite superficial similarities= ,
these are distinct activities).

Henry explains: "The naming is related to Mike's ingenious trick= for computing the encoding in the cofactor-8 case with only a singl= e=20 inverse square root. Clever use of the curve equation gives a number=20 that relates two of the quantities, called magic in Mike's = script. I named the variable enchanted_denominator to refle= ct the fact that it had magic multiplied in."

The authors are fairly unanimous in being fond of the naming.

page 10: "x =3D CT_SELEC= T(iy0 IF rotate ELSE x0)" -> maybe add a comment
there = to highlight that the use of "iy0" here (and not "ix0") is
intentional and not a typo (and similarly for the next formula).

Done.

page 11: In the interest of clarity, it may be = worth pointing out that
the "one-way map" is not, by itsel= f, one-way: given an output
ristretto255 element, it's not= too hard to find an input 64-byte string
b that yields th= at element (you try random values b[0:32] and, for each,
y= ou apply the reverse Elligator2 on P2; it will work with sufficiently
high probability that the process will complete quickly). Wh= at makes the
map one-way is the combination of the process= of section 4.3.4 with a
suitable hash construction; the o= ne-wayness is really that of the hash.
The role of the map= ping of section 4.3.4 is to turn the one-way hash
output b= into a close-to-uniformly distributed group element in such a
=
way that nobody can work out the discrete logarithm of the output
relatively to the conventional generator.

Done.

page 11: "The one-way map operates an uniformly [...]"
-> "[...] operates on [...]"

=
Done.

= page 11: "on a 32-bytes string" -> "on a 32-byte string"
(or: "a string of 32 bytes")

Done, and then changed on main to be "on 32-byte strings" for consisten= cy with the element encoding sections.

page 11: "Interpret the least significant 255 bits= of the string as an
integer r in little-endian representa= tion" -> to be clear about that,
the _256_ bits are int= erpreted in little-endian representation, which
defines wh= ich ones of these bits are the "least significant 255 bits",
and only then is the top bit ignored. And, to be _really_ clear, the<= br>
string does not contain bits but bytes, and the transform = here is not
fully specified if you do not say how the bits= of a byte are to be
extracted. And you probably do not wa= nt to go there, because then you
will have to say things l= ike "we use little-endian convention at the
byte level, bu= t big-endian convention for bits within a byte", and a lot
of confusion lies down that path. Previously in the document, the input=
_bytes_ were simply interpreted in "little-endian convent= ion" and that
was not ambiguous as long as we simply used = bytes, i.e. each byte having
a value in the 0..255 range, = and we never even tried to look at
individual _bits_.
<= /div>
I thus suggest writing step 1 of the MAP function as:

   1. Interpret the input bytestring as i= n integer in little-endian
      = convention, then reduce it modulo 2^255 (this is equivalent to
=
      "masking out the most significant bi= t" as in [RFC7748],
      section= 5). The resulting integer, which is lower than 2^255,
&nb= sp;     is then further reduced modulo p, yielding a= field element t.

Agreed that = "the least significant 255 bits of the string" is under-specified. On th= e other hand, we want to point implementers to the simple way to perform= this operation. Changed to "mask the most significant bit in the final = byte of the string" which matches the RFC 7748 language (which does not = feel the need to specify the use of big-endian for bytes), and added a s= ub-element noting that the operation is equivalent to reduction modulo 2= ^255 to avoid any ambiguity.

page 12: section 4.4 uses "byte string" while the document p= reviously
used "bytestring".
Now using "byte string" throughout. See above.

page 12: the provisions on ca= nonical encodings of scalars use "SHOULD";
maybe that shou= ld be "MUST", for the same reasons that make canonical
enc= odings of group elements desirable? Otherwise, you end up with
=
things like malleable signatures, and Bitcoin is sad.

They are SHOULD to allow reuse of existing = implementations. Added a rationale and reiterated that omitting the chec= ks is NOT RECOMMENDED.

page 12: "Given a uniformly distributed 64-byte string b [...]" -&= gt; It
might be worth saying what is the point of this par= agraph. For any
integer l, one can obtain a value modulo l= by taking an integer and
reducing it modulo l. What you w= ant to express here is that IF the
source 64-byte string i= s uniformly distributed, THEN the result of
the reduction = will be very close to uniformly distributed among
integers= modulo l.
(Arguably, since l is very close to 2^252, taki= ng an input 32-byte
string b would already yield a suffici= ently uniform output for
cryptographic purposes. Using a f= ull 64-byte input is overkill, but does
not harm much beyo= nd the extra cost of reduction.)

Precised that the purpose is to "obtain a uniformly distributed scalar".

page 1= 2: "This documents" -> "This document"
Done.

page 12: as on page 9, there should be a definition of the internal
=
representation of curve points. This is made slightly more co= mplicated
because RFC 8032, for edwards448, uses projectiv= e coordinates (in
section 5.2.4) and not homogeneous coord= inates, so you cannot simply
add a reference to that RFC.<= br>

See above, defined in Section = 2 and at the top of Section 5.

page 13: same remark as page 6 on expression of bytestrings = as 8-digit
hexadecimal numbers.

See above.

page 14: "similar to Section 5.1.3 of [RFC8032]" -> This is= the wrong
section. 5.1.3 is for Curve25519; you want to r= eference section 5.2.3,
which is about edwards448.
Also, the formula in section 5.2.3 of RFC 8032 is different; the = one
in your draft is simpler, and also correct. I don't kn= ow why RFC 8032
used a more complicated formula.
=

Done.

page 14: "encoded as a 56-byte string" -> "[...= ] as 56-byte strings"

Done in = main. See above.

= (Note: I am not verifying the encoding formulas of section 5.3.2.)

page 15: "encoding of s, reduced modulo p" ->= since s is a field
element, it is inherently "reduced mod= ulo p". Maybe write this as:
"encoding of the unique integ= er representation of s as an integer in the
0 to p-1 range= ".

Agreed that this is redunda= nt, as a field element is defined in Section 2 as "values modulo p". Tri= mmed to just "encoding of s" for brevity.

page 16: "operates an uniformly" -> "operate= s on uniformly"

Done.

page 16: same remark as p= age 11 about one-wayness.

Done= . See above.

(Not= e: I am not verifying the map formulas of section 5.3.4.)
=
page 17: "byte strings" -> "bytestrings"

Now using "byte string" throughout. See abo= ve.

page 17: "SHO= ULD" on encoding of scalars: same remark as on page 12.

See above.

page 17: reducing an integer modulo l: as on page 12= , there should be a
word about what is the point here. Als= o, one may note that a 512-bit
integer is not very much la= rger than the 446-bit subgroup order; but it
is still fine= here because l is very close to a power of 2. This might
= be worth a comment (otherwise, one might imagine that the paragraph was<= br>
copy&pasted from the one in section 4.4, and that the = "64" is a typo).

Like above, p= recised that the purpose is to "obtain a uniformly distributed sc= alar". The bias analysis and rationale for the size was deemed out of sc= ope for an implementer oriented document.

page 17: "they MUST NOT construct group elements ex= cept via decoding and
the one-way map" -> Actually, gro= up operations such as adding two
elements together are als= o allowed ways to construct group elements.
<= br>
Done.

page 18: section 8 explains that decoding always returns either a val= id
representation, or an error. However, some implementati= ons may return an
error _and_ an invalid representation; t= his would be typical of C
implementations where the output= point is written into a
caller-allocated structure, and t= he error code is the return value of
the function. In that= case, a depressingly common implementation failure
is to = ignore the error code and keep on with the invalid representation.
This might be worth an explicit warning sentence in section 8.<= br>

I tried to formulate the warni= ng, but kept failing because it felt jarring and contradictory to say "t= his API MUST return either X or Y" and then follow up with "if you get b= oth X and Y, here's the precedence rule". Moreover, it boiled down to "t= ell your applications not to ignore the error or defeat the API!" which = is not even under the draft implementer's control. I don't disagree that= this might be depressingly common, but I think it's a general C shortco= mings like the lack of memory safety which is out of scope for this docu= ment.

(Note: idea= lly I should implement everything to verify the test vectors,
<= div>but there already are existing ristretto255 and decaf448 implementat= ions
around so I assume this has already been done. I veri= fied most formulas,
except those of sections 5.3.2 and 5.3= .4, by comparing with the published
formulas on https://ristretto.group/ and the Decaf pa= per.)

Thomas

As a final note, thank you for the thorough and helpful= review!

Cheers,
Filippo
<= /div>

2022-02-25 13:58 GMT+01:00 internet-drafts@ietf.org:

A Ne= w Internet-Draft is available from the on-line Internet-Drafts directori= es.
This draft is a work item of the Crypto Forum RG of th= e IRTF.

      = ;  Title          = ; : The ristretto255 and decaf448 Groups
   = ;     Authors      &nb= sp;  : Henry de Valence
     = ;            = ;         Jack Grigg
           &nb= sp;           &nb= sp;  Mike Hamburg
      = ;            = ;        Isis Lovecruft
            = ;            = ;  George Tankersley
     &n= bsp;           &n= bsp;        Filippo Valsorda
Filename        : draft-irtf-cf= rg-ristretto255-decaf448-03.txt
Pages   &nb= sp;       : 27
Date &nb= sp;          : 2022-02-25

Abstract:
   This me= mo specifies two prime-order groups, ristretto255 and
&nbs= p;  decaf448, suitable for safely implementing higher-level and com= plex
   cryptographic protocols.  The ristr= etto255 group can be implemented
   using Curve2= 5519, allowing existing Curve25519 implementations to be
&= nbsp;  reused and extended to provide a prime-order group.  Li= kewise, the
   decaf448 group can be implemented= using edwards448.


The IETF = datatracker status page for this draft is:

There is also an HTML version available at= :

A diff from the previous version is available at:


Internet-= Drafts are also available by rsync at rsync.ietf.org::internet-drafts


______________________________= _________________
CFRG mailing list


= --cf0b7d86d0d94f4e858d3fff3cfa1d16--