I support adoption of this draft.

<= /div>

Mike

On Tue, Apr 30, 2019 at 4:39 PM Marek Jankowski <mjankowski309@gmail.com> wro=
te:

I also support the adoption of this draft. If needed, once adopted I w= ill review it and may be able to produce testvectors.Ma= rek.On Tue, Apr 30, 2019 at 3:51 AM Gerardo Di Giacomo <gdg@fb.com> wrote:I support = the adoption of this draft.

=C2= =A0Gerardo Di= Giacomo

=C2= =A0

From: =Cfrg <cfrg-bounces@irtf.org>= ; on behalf of Tony Arcieri <bascule@gmail.com>

Date:Sunday, April 28, 2019 at 2:15 PM

To:Paterson Kenneth <kenny.paterson@inf.ethz.ch>

Cc:"cfrg@ir= tf.org" <cfr= g@irtf.org>

Subject:Re: [Cfrg] Adoption call for draft-boneh-bls-signature

=C2=A0I support the adoption of this draft.

<= /p>

=C2=A0On Fri, Apr 26, 2019 at 10:11 AM Paterson Kenneth &l= t;kenny.pat= erson@inf.ethz.ch> wrote:

=C2=A0Dear CFRG,

(This is the second of two adoption calls today.)

This email starts a 2-week adoption call for:

https://tools.ietf.org/html/draft-boneh-bls= -signature-00

BLS Signature Scheme

Please give your views on whether this document should be adopted as a CFRG= draft, and if so, whether you'd be willing to help work on it/review i= t.

Thanks,

Kenny (for the chairs)

_______________________________________________

Cfrg mailing list

Cfrg@irtf.org

https://www.irtf.org/mailman/listinfo/cfrg

=C2=A0--

Tony Arcieri

_______________________________________________

Cfrg mailing list

Cfrg@irtf.org

https://www.irtf.org/mailman/listinfo/cfrg

Cfrg mailing list

Cfrg@irtf.org

https://www.irtf.org/mailman/listinfo/cfrg

Hello Shoko,

Just to clarify what is go=
ing on here with the BN462 curve..

By choosing the=
QNR as 1+sqrt(-1), the curve is M type, and F_p^2 arithmetic will be quite=
fast, but M type twists require a bit more work.

=
By choosing the QNR as 2+sqrt(-1) (as in your draft), the curve is D type, =
with slower F_p^2 arithmetic, but faster twisting.

So its depends on which optimization is regarded as more important. I woul=
d still prefer to go with the M type, but really it makes little difference=
. A common approach seems to be to support all QNRs of the form 2^i+sqrt(-1=
), with minimal i.

So basically I am withdrawing m=
y objection to the way in which BN462 has been presented in your draft.

Mike

On Mon, Apr 22, 2019 at 2:46 PM Michael Sco=
tt <mike.scott@miracl.com&g=
t; wrote:

(Re-sending as this thread has bloated to over = 40k bytes)Hello Shoko,And thanks fo= r your reply. I am OK with the choice of parameters for the BLS381 curve.For the BN462 curve it would be a pity to use a sub= optimal representation, when a better representation is possible. For examp= le in=C2=A0https://eprint.iacr.org/2017/334.pdf=C2=A0, all the suggested curves= use the simpler form, as it offers "the best possible arithmetic"= ;, including the original BN462 suggested curve.M= aybe, as you suggest, a choice of parameters would be a solution (or some g= uidance on how to switch between representations)= MikeOn Mon, Apr 22, 2019 at 12:26 PM Shoko YONEZAWA <yonezawa@lepidum.co.jp= > wrote:= Hello Mike,

I'm sorry for being late for responding to your comments,

all of which are important and valuable.

Please allow me to reply to all of your comments in this single mail.

Thank you for your suggestions of the curve parameters.

As you mentioned, there are the curve parameters which provide more

efficient computation than we described,

but we emphasize the implementation status, that is,

whether the curves have been already available.

As for BN462, we refer to the parameters implemented in mcl

(https://github.com/herumi/mcl).

In this implementation, the twisted curve is set to E':y^2=3Dx^3-u+2

and the tower of extension field is F_p6 =3D F_p2[v] / (v^3 - u - 2).

Their implementation of BLS12-381 has been adopted to Zcash

and we cannot ignore the curve parameters chosen in mcl.

Therefore, we would like to choose the existing curve parameters in our

draft in order for interoperability.

We understand that the parameters you suggested can indeed improve the

efficiency.

We can add these parameters to our draft if it is accepted to describe

multiple parameters.

I would be grateful if my answers could make sense.

Best,

Shoko

On 2019/04/03 18:08, Michael Scott wrote:

> .. as a follow up to my comments on the curve BN462..

>

> I note this choice

>

> F_p6 =3D F_p2[v] / (v^3 - u - 2)

>

>

> Its not clear to me why you did not choose the simpler irreducible

> polynomial

>

> x^6-(1+sqrt(-1))

>

> which will always be more efficient. See the section on "BN tower= s" in

> https://eprint.iacr.org/2009/556.pdf

>

> where the conditions for this choice are satisfied.

>

>=C2=A0 =C2=A0 =E2=80=93 If x0 =E2=89=A1 7 or 11 mod 12 then x^6 =E2=88= =92 (1 + =E2=88=9A =E2=88=921) is irreducible over

> Fp2 =3D Fp( =E2=88=9A =E2=88=921).

>

> (in the case of BN462 x0=3D7 mod 12)

>

> Mike

>

>

> On Sun, Mar 31, 2019 at 8:28 PM Michael Scott <mike.scott@miracl.com

> <mailto:= mike.scott@miracl.com>> wrote:

>

>=C2=A0 =C2=A0 =C2=A0Hello Shoko,

>

>=C2=A0 =C2=A0 =C2=A0Thanks for previous clarifications.

>

>=C2=A0 =C2=A0 =C2=A0I am a bit puzzled by the proposed BN462 curve

>

>=C2=A0 =C2=A0 =C2=A0You chose the curve E:y^2=3Dx^3+5

>=C2=A0 =C2=A0 =C2=A0On the twisted curve you choose E':y^2=3Dx^3-u+= 2 (and I am unclear

>=C2=A0 =C2=A0 =C2=A0where -u+2 came from)

>

>=C2=A0 =C2=A0 =C2=A0In the paper that first suggested the curve -

>=C2=A0 =C2=A0 =C2=A0https://eprint.iacr.org/2017/334.pdf=

>

>=C2=A0 =C2=A0 =C2=A0the authors suggest

>=C2=A0 =C2=A0 =C2=A0E: y^2=3Dx^3-4, and

>=C2=A0 =C2=A0 =C2=A0E': y^2=3Dx^3-4(1+u)

>

>=C2=A0 =C2=A0 =C2=A0which seems simpler, and closer to the BLS381 appro= ach

>

>=C2=A0 =C2=A0 =C2=A0I am attempting to implement these curves (and alre= ady have BLS381

>=C2=A0 =C2=A0 =C2=A0done). Any help is much appreciated.

>

>=C2=A0 =C2=A0 =C2=A0Mike

>

Hello Shoko,

Yes, that is another good =
reason. So please proceed...

Mike

<= div class=3D"gmail_quote">

On Thu, May=
2, 2019 at 11:03 AM Shoko YONEZAWA <yonezawa@lepidum.co.jp> wrote:

Hello Mike,--0000000000004eb8690587e56a3c-- From nobody Thu May 2 08:41:55 2019 Return-Path:

Thank you for your consideration.

Another reason why we chose BN462 with 2+sqrt(-1)

is that most of the former BN curves were D type

and we would like to follow them.

We would be grateful if we could proceed with BN462

described in the current version of our draft.

Best,

Shoko

On 2019/05/02 17:34, Michael Scott wrote:

> Hello Shoko,

>

> Just to clarify what is going on here with the BN462 curve..

>

> By choosing the QNR as 1+sqrt(-1), the curve is M type, and F_p^2

> arithmetic will be quite fast, but M type twists require a bit more wo= rk.

>

> By choosing the QNR as 2+sqrt(-1) (as in your draft), the curve is D <= br> > type, with slower F_p^2 arithmetic, but faster twisting.

>

> So its depends on which optimization is regarded as more important. I =

> would still prefer to go with the M type, but really it makes little <= br> > difference. A common approach seems to be to support all QNRs of the <= br> > form 2^i+sqrt(-1), with minimal i.

>

> So basically I am withdrawing my objection to the way in which BN462 h= as

> been presented in your draft.

>

> Mike

>

> On Mon, Apr 22, 2019 at 2:46 PM Michael Scott <mike.scott@miracl.com

> <mailto:= mike.scott@miracl.com>> wrote:

>

>=C2=A0 =C2=A0 =C2=A0(Re-sending as this thread has bloated to over 40k = bytes)

>

>=C2=A0 =C2=A0 =C2=A0Hello Shoko,

>

>=C2=A0 =C2=A0 =C2=A0And thanks for your reply. I am OK with the choice = of parameters for

>=C2=A0 =C2=A0 =C2=A0the BLS381 curve.

>

>=C2=A0 =C2=A0 =C2=A0For the BN462 curve it would be a pity to use a sub= optimal

>=C2=A0 =C2=A0 =C2=A0representation, when a better representation is pos= sible. For

>=C2=A0 =C2=A0 =C2=A0example in https://eprint.iacr.org/2017/= 334.pdf=C2=A0, all the suggested

>=C2=A0 =C2=A0 =C2=A0curves use the simpler form, as it offers "the= best possible

>=C2=A0 =C2=A0 =C2=A0arithmetic", including the original BN462 sugg= ested curve.

>

>=C2=A0 =C2=A0 =C2=A0Maybe, as you suggest, a choice of parameters would= be a solution

>=C2=A0 =C2=A0 =C2=A0(or some guidance on how to switch between represen= tations)

>

>=C2=A0 =C2=A0 =C2=A0Mike

>

>=C2=A0 =C2=A0 =C2=A0On Mon, Apr 22, 2019 at 12:26 PM Shoko YONEZAWA

>=C2=A0 =C2=A0 =C2=A0<yonezawa@lepidum.co.jp <mailto:yonezawa@lepidum.co.jp>> wrot= e:

>

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Hello Mike,

>

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0I'm sorry for being late for resp= onding to your comments,

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0all of which are important and valuab= le.

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Please allow me to reply to all of yo= ur comments in this single

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0mail.

>

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Thank you for your suggestions of the= curve parameters.

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0As you mentioned, there are the curve= parameters which provide more

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0efficient computation than we describ= ed,

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0but we emphasize the implementation s= tatus, that is,

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0whether the curves have been already = available.

>

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0As for BN462, we refer to the paramet= ers implemented in mcl

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(https://github.com/herumi/mcl).

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0In this implementation, the twisted c= urve is set to E':y^2=3Dx^3-u+2

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0and the tower of extension field is F= _p6 =3D F_p2[v] / (v^3 - u - 2).

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Their implementation of BLS12-381 has= been adopted to Zcash

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0and we cannot ignore the curve parame= ters chosen in mcl.

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Therefore, we would like to choose th= e existing curve parameters

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0in our

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0draft in order for interoperability.<= br> >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0We understand that the parameters you= suggested can indeed

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0improve the

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0efficiency.

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0We can add these parameters to our dr= aft if it is accepted to

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0describe

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0multiple parameters.

>

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0I would be grateful if my answers cou= ld make sense.

>

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Best,

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Shoko

>

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0On 2019/04/03 18:08, Michael Scott wr= ote:

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > .. as a follow up to my comment= s on the curve BN462..

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > I note this choice

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > F_p6 =3D F_p2[v] / (v^3 - u - 2= )

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > Its not clear to me why you did= not choose the simpler

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0irreducible

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > polynomial

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > x^6-(1+sqrt(-1))

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > which will always be more effic= ient. See the section on "BN

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0towers" in

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > https://eprint.iacr.= org/2009/556.pdf

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > where the conditions for this c= hoice are satisfied.

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =E2=80=93 If x0 = =E2=89=A1 7 or 11 mod 12 then x^6 =E2=88=92 (1 + =E2=88=9A =E2=88=921) is>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0irreducible over

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > Fp2 =3D Fp( =E2=88=9A =E2=88=92= 1).

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > (in the case of BN462 x0=3D7 mo= d 12)

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > Mike

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > On Sun, Mar 31, 2019 at 8:28 PM= Michael Scott

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0<mike.scott@miracl.com <mailto:mike.scott@miracl.com>= ;

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > <mailto:mike.scott@miracl.com

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0<mailto:mike.scott@miracl.com>>> wrot= e:

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0Hello Shoko,=

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0Thanks for p= revious clarifications.

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0I am a bit p= uzzled by the proposed BN462 curve

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0You chose th= e curve E:y^2=3Dx^3+5

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0On the twist= ed curve you choose E':y^2=3Dx^3-u+2 (and I am

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0unclear

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0where -u+2 c= ame from)

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0In the paper= that first suggested the curve -

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 > https://eprint.iacr.= org/2017/334.pdf

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0the authors = suggest

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0E: y^2=3Dx^3= -4, and

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0E': y^2= =3Dx^3-4(1+u)

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0which seems = simpler, and closer to the BLS381 approach

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0I am attempt= ing to implement these curves (and already

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0have BLS381

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0done). Any h= elp is much appreciated.

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >=C2=A0 =C2=A0 =C2=A0Mike

>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 >

>

--

Shoko YONEZAWA

Lepidum Co. Ltd.

yonezawa@lepidu= m.co.jp

TEL: +81-3-6276-5103

I also support the adoption of this draft.

<=
div>Marek.

On Tue, Apr 30, 2019 at 5:28 PM mcgrew <mcgrew@cisco.com> wrote:

Hi Kenny and Richard,

I support the adoption of draft-barnes-cfrg-hpke, and I have some comments = below.

I like the goal of an RFC that provides a self-contained normative descript= ion of "hybrid public key encryption."=C2=A0

It should be an explicit goal that an implementation can conform to this RF= C and also conform to [keyagreement], for the NIST approved algorithms, bec= ause NIST validation is important in the industry.=C2=A0 I suggest adding a= subsection somewhere that details how this conformance is possible.=C2=A0 = =C2=A0 Please note that I=E2=80=99m not asking that every possible option/c= iphersuite in this document be in the NIST-approved category; rather, I=E2= =80=99m asking that for the NIST-approved algorithms, the details such as k= ey generation, domain parameters, and symmetric key derivation don=E2=80=99= t have any incompatibilities.

I suggest changing the name from hybrid public key encryption to something = from the existing literature.=C2=A0 =C2=A0According to Boyd and Mathuria, f= or instance, this is a key transport scheme, and the term =E2=80=9Chybrid= =E2=80=9D has a different meaning.=C2=A0 =C2=A0Something like "Key Tra= nsport for AEAD Using Discrete Log Cryptography=E2=80=9D seems accurate, si= nce this draft only covers DL, there is no need to have a name that would b= e generic to RSA and McEliece.=C2=A0 =C2=A0=E2=80=9CAsymmetric Key Transpor= t for AEAD=E2=80=9D would be appropriate if there is a need to be more gene= ric.=C2=A0

The phrase "Hybrid public-key encryption (HPKE) is a substantially mor= e efficient solution than traditional public key encryption techniques such= as those based on RSA or ElGamal=E2=80=9D is confusing, because combined a= symmetric/symmetric crypto systems have been the preferred solution since K= ohnfelder=E2=80=99s 1978 thesis.=C2=A0 =C2=A0Someone without domain experti= se might mistakenly think that this draft is claiming to be an improvement = over current public key algorithms.=C2=A0 =C2=A0I suggest motivating this d= raft with something like =E2=80=9CWhile there are well accepted standards f= or public key encryption [RFC7748][keyagreement], in several scenarios thes= e techniques must be combined with symmetric authenticated encryption."= ;

There should be some discussion about replay attacks and their prevention.= =C2=A0

If there is not a strong mechanism protecting against replays, would it mak= e sense to use an AEAD that is robust against nonce misuse, like GCM-SIV?= =C2=A0

"A given context SHOULD be used either only for encryption or only for= decryption.=E2=80=9D=C2=A0 =C2=A0Why not a MUST?=C2=A0

It seems that there is no citation given for P-256 and P-521.=C2=A0

A nit: KEM is used before it is defined.

thanks

David

> On Apr 26, 2019, at 4:09 AM, Paterson Kenneth <kenny.paterson@inf.ethz.ch&= gt; wrote:

>

> Dear CFRG,

>

> (This is the first of two adoption calls today.)

>

> This email starts a 2-week adoption call for:

>

> https://tools.ietf.org/html/draft-barnes-= cfrg-hpke-01

>

> Hybrid Public Key Encryption

>

> Please give your views on whether this document should be adopted as a= CFRG draft, and if so, whether you'd be willing to help work on it/rev= iew it.

>

> Thanks,

>

> Kenny (for the chairs)

>

>

> _______________________________________________

> Cfrg mailing list

> Cfrg@irtf.org> https://www.irtf.org/mailman/listinfo/cfrg

_______________________________________________

Cfrg mailing list

Cfrg@irtf.org

https://www.irtf.org/mailman/listinfo/cfrg

Hi Dan:

The paper [1] may be of interest to
your problem.

Best regards, Rene

Ref: [1] DLP - Small Generic Hardcore
Subset for DLP, Short Secret DL Keys (Claus Schnorr, Inform. Proc.
Letters, 2001)

On 5/2/2019 11:41 AM, Dan Brown wrote:

Dear CFRG, Is there a multi-user attack (e.g., see below) on _any_ 128-bit-secure public keys (e.g. 256-bit ECC keys) if they are generated by hashing 128-bit uniformly random seed? I will call this key generation method "bottleneck key generation". To be clear, all user users share the same 128-bit bottleneck, and that may be the problem. If there is indeed an multi-user attack here, is the multi-user attack (against 2^N users) prevented by using a (128+N)-bit seed, OR by using a unique-per-public-key salt/nonce/tag/personalization value? The very notion of multi-user security has always puzzled me: I question its merit as a goal. This might be why I forget how it works so easily. (Over the last day, I tried to remember/search for existing write-ups on this, see further below.) On the issue of naivety of the bottleneck key generation above, I think it very plausible that many would consider it reasonably secure. This topic touches a couple CFRG items, but seems to be question of general crypto interest. *** For completeness, here is what I think the multi-user attack on bottleneck key generation: Each of 2^32 users does the following. - User j chooses a uniformly random 128-bit seed s[j], independently of all other users. - User j computes a secret key a[j] by hashing s[j], e.g., using SHA-256 (or some other deterministic, collision-resistant function). - User j computes a public key A[j] from a[j], e.g. in ECC A[j]=a[j]*G. The attacker does the following. - Obtain all 2^32 values A[j], and sorts them, or stores in a hash-table. - Does the following up to 2^96 times: - compute a 128-bit seed, s', - compute secret key a', the same way as the user, e.g. a' = SHA256(s'), - compute public key A', the same way as the user, e.g. A' = a' * G, - check if A' in is list of A[j], via table-lookup. - If A' in A[j] is found, then attacker outputs a' as the guess for a[j]. The attacker wins the multi-user game. Success rate: The attack is expected to work with probability near 1/e (e~2.7?), essentially finding a collision at the level of seeds with s[j]=s', being a variation of the birthday paradox. (Proof sketch? Each s' has prob 2^32/2^128 of hitting an s[j], assuming all user seed distinct. This is 1/M for M=2^96. The prob of all M independent s' missing is (1-1/M)^M ~ 1/e. This ignore the prob of s[j] collisions, and SHA256 collisions, etc.) Attack cost: The attacker uses 2^96 steps (each step matching the user's cost). Hmm ... is this somehow an "optimal" multi-user attack, in the sense the cost reduction factor equals the number of users? If the seeds above are increased to 160 bits, then the multi-user attack (against 2^32 users) seems to take 2^128 steps. In this case, the multi-user security is optimal (matching single-user security). If we put a max of 2^64 users, then a 192-seed may be good enough for maximal multi-user security. Why do I question multi-user security? The cost of resisting multi-user attacks seems to be nonzero for the single user. It seems to me that the single-user should only pay for this cost if there is a common interest with other users. If there is a common interest, then maybe so formalized communal crypto is needed instead? E.g. group/ring/whatever signature? *** Relevant past work on multi-user security, in approximate chronological order: [1] Salting password hashes. Not sure what the best reference is for this. I think the oldest work is salting the password hashes. Is "salt" the usual word here? The numbers for larger seeds and keys correspond to higher security levels then passwords and hashes, but the logic is otherwise similar, isn't it? (In other words, not sure why new words would be used instead of salt.) [2] Hastad-style security analysis: I lump MANY works together, perhaps originating from Hastad, which all assume full-power key generation, i.e. NOT 128-bit bottleneck key generation. Instead, these papers ask other important questions about multi-user security. In other words, the question is whether the public key algorithm itself has some other kind of bottleneck (which all users share). As some examples of this direction of research, I include Bellare--Boldyreva--Micali work on PKE https://cseweb.ucsd.edu/~mihir/papers/musu.pdf and Bernstein's work on Schnorr signatures https://ia.cr/2015/996, but I would need to re-read these works carefully: perhaps they treat the issue of bottleneck key generation in an off-hand remark as an something obvious, dating back to [1]. [4] The issue seems to be discussed, rather vaguely, in ANSI X9.62-2005, Section K.5, item e. (I am trying to resolve comments from Elaine Barker about this Section K.5. I eventually clued about the generality of this issue, leading me to this email.) [5] Zaverucha, https://ia.cr/2012/159, "Hybrid encryption in the multi-user setting" perhaps goes a little further than the Hastad-type attacks that I lumped together in [3], since it describes 128-bottlenecks in key derivation more generally, including the key generation and HKDF. As with [3], I have forgotten the details, and would need re-read the paper very carefully to see if it really should be lumped together with [3]. [6] NIST Special publication 800-90Ar1, specifies a "DRBG". A DRBG can be interpreted as a deterministic function mapping a 128-bit secret seed to a pseudorandom 256-key. The NIST SP 800-90Ar1 requires a "nonce" or a "personalization string", unique to each user. Is this not just another example of the "salt" solution? Is the purpose of this "multi-user" security? I find the NIST document very long, and find it difficult to be certain if the multi-user security is resolved. [7] RFC 8032 has a comment about a few missing bits of entropy (in the EdDSA key) missing not being disastrous. This claim sounds correct (see the attack where I talk about 192-bit seeds). Is the justification for this claim quantified somewhere? There was also some discussion of multi-user security surrounding EdDSA variants, so maybe bottleneck key generation is an issue for EdDSA too. [8] The randomness improvement draft https://datatracker.ietf.org/doc/draft-irtf-cfrg-randomness-improvements/ uses the term "tag", which should be user-specific (?). Another example of a "salt", if I understand it. See also https://ia.cr/2018/1057 A digression: best practice password-hashing involves costly hashes, e.g. Argon2, not just per-user salts. Costly hashes may be re-usable for public key seeding, no? Dan Brown Phone: +1 (289) 261-4157 BlackBerry, Security in Motion

_______________________________________________ Cfrg mailing list Cfrg@irtf.org https://www.irtf.org/mailman/listinfo/cfrg

-- email: rstruik.ext@gmail.com | Skype: rstruik cell: +1 (647) 867-5658 | US: +1 (415) 690-7363--------------5BDF396E52C935C1994D16D3-- From nobody Tue May 7 08:46:12 2019 Return-Path: