Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt

[Shoko YONEZAWA <[e-mail]>]

Hello Mike,

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 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 
> would 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 my objection to the way in which BN462 has 
> been presented in your draft.
> 
> Mike
> 
> On Mon, Apr 22, 2019 at 2:46 PM Michael Scott <[e-mail] 
> <mailto:[e-mail]>> wrote:
> 
>     (Re-sending as this thread has bloated to over 40k bytes)
> 
>     Hello Shoko,
> 
>     And thanks for 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 suboptimal
>     representation, when a better representation is possible. For
>     example in https://eprint.iacr.org/2017/334.pdf , all the suggested
>     curves use the simpler form, as it offers "the best possible
>     arithmetic", including the original BN462 suggested curve.
> 
>     Maybe, as you suggest, a choice of parameters would be a solution
>     (or some guidance on how to switch between representations)
> 
>     Mike
> 
>     On Mon, Apr 22, 2019 at 12:26 PM Shoko YONEZAWA
>     <[e-mail] <mailto:[e-mail]>> 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=x^3-u+2
>         and the tower of extension field is F_p6 = 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 = 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
>         towers" in
>          > https://eprint.iacr.org/2009/556.pdf
>          >
>          > where the conditions for this choice are satisfied.
>          >
>          >    – If x0 ≡ 7 or 11 mod 12 then x^6 − (1 + √ −1) is
>         irreducible over
>          > Fp2 = Fp( √ −1).
>          >
>          > (in the case of BN462 x0=7 mod 12)
>          >
>          > Mike
>          >
>          >
>          > On Sun, Mar 31, 2019 at 8:28 PM Michael Scott
>         <[e-mail] <mailto:[e-mail]>
>          > <mailto:[e-mail]
>         <mailto:[e-mail]>>> wrote:
>          >
>          >     Hello Shoko,
>          >
>          >     Thanks for previous clarifications.
>          >
>          >     I am a bit puzzled by the proposed BN462 curve
>          >
>          >     You chose the curve E:y^2=x^3+5
>          >     On the twisted curve you choose E':y^2=x^3-u+2 (and I am
>         unclear
>          >     where -u+2 came from)
>          >
>          >     In the paper that first suggested the curve -
>          > https://eprint.iacr.org/2017/334.pdf
>          >
>          >     the authors suggest
>          >     E: y^2=x^3-4, and
>          >     E': y^2=x^3-4(1+u)
>          >
>          >     which seems simpler, and closer to the BLS381 approach
>          >
>          >     I am attempting to implement these curves (and already
>         have BLS381
>          >     done). Any help is much appreciated.
>          >
>          >     Mike
>          >
> 

-- 
Shoko YONEZAWA
Lepidum Co. Ltd.
[e-mail]
TEL: [phone]