Re: [Cfrg] Some observations after the ECC interim meeting

[Patrick Longa Pierola <[e-mail]>]

> Why can't higher security levels follow the lead of the low security levels, even if designed at different times?

Consistency of the curve selection (curve form, subgroup structure, prime form, etc.) across the different security levels can have several benefits in practice (e.g., easier-to-implement, easier-to-maintain, easier-to-describe, less error-prone implementations). To give an example on why it might be a bad idea to simply follow the design of the lower security curves when choosing higher security curves in the future: some consistency might be lost if different prime forms are chosen for different security levels. So far there has been very little discussion on the selection of high-security curves and ideally we won't want to limit our options in the future when selecting those curves (are the primes for those curves going to have full-bitlength, pseudo-Mersenne form exactly matching the targeted security level or are they going to have extended or reduced bitlength, or other special forms such as Hamburg's proposal, etc.?). IMO some decisions will be better if are taken when looking at the full solution and spectrum of curves.

Regards,

Patrick  


-----Original Message-----
From: Watson Ladd [mailto:[e-mail]] 
Sent: Monday, May 5, 2014 4:23 PM
To: Patrick Longa Pierola
Cc: [e-mail]
Subject: Re: [Cfrg] Some observations after the ECC interim meeting

On Mon, May 5, 2014 at 4:12 PM, Patrick Longa Pierola <[e-mail]> wrote:
> Dear all,
>
> In our presentation at the CFRG meeting we were especially interested 
> in drawing some attention to some issues that are very relevant when 
> using Edwards and Montgomery curves. In particular,
>
>
>
> -   when computing the Montgomery ladder in constant time there is a
> potential failure case if the scalar matches 0 (mod r) or 0 (mod r’), 
> where r and r’ are the prime orders of the subgroups generated on the 
> Montgomery curve and its quadratic twist, respectively. We noted that 
> Curve25519 avoids this issue (together with dealing with subgroup 
> attacks) by restricting the scalar values to 2^254 + 8{0,1,…,2^251-1}. 
> This design feature does not match the standard practice in 
> cryptography that is to allow the scalar value to be in the full range 
> [1, r-1]. For example, when working with
> Ed25519 there is a restriction of scalars to less than half of such 
> full range. Refer to slide 10 in [1].
>
>
>
> -   when using the Montgomery ladder for key exchange (computed with one
> variable-base scalar multiplication) there are engineering issues that 
> need to be addressed: is key generation being computed on the 
> Montgomery form or the Edwards form? If it is computed using the 
> Montgomery form then there is a significant performance impact (option 
> referred to as “hybrid 1” in our presentation; see slides 23-24 in 
> [1]). One can certainly use the Edwards form instead (this option 
> corresponds to “Hybrid 2” in the same slides) but one then needs to 
> deal with issues such as point conversion, special point formatting 
> for transmission, etc. Another potential issue with this second 
> alternative is that good solutions might be protocol-specific, instead 
> of generic. Our performance results indicate that there is no need to 
> deal with these potential issues (issues that are relevant, e.g., to 
> the TLS handshake using PFS, and that might be even more difficult to 
> deal with in different
> protocols) because all the computations can be performed purely on the 
> twisted Edwards form of the curve. This also brings to the table the 
> possibility of using only one curve form (twisted Edwards) for 
> signatures and key exchange (and any other possible ECC operations), 
> instead of defining different curve forms for different ECC 
> operations. This unification might bring several benefits in practice.
>
>
>
> Finally, we point out that the current effort of moving forward with 
> only one curve targeting *one security level* (i.e., 128-bit) might 
> bring the risk of having inconsistencies once future additions are 
> done at other security levels. We suggest instead to first have a 
> solid curve selection that includes all the security levels, with 
> strong consistency in the design.

Why can't higher security levels follow the lead of the low security levels, even if designed at different times?
It would seem that using the twisted Edwards form uniformly (and as a wire format) avoids all the issues you mentioned.

Furthermore, fast implementations can take advantage of isogenies, restrict scalars, etc. even if the standards recommend an algorithm that doesn't.

Sincerely,
Watson Ladd
>
>
>
> Best regards,
>
>
>
> Patrick
>
>
>
>
>
> [1] Patrick Longa, “Selecting Elliptic Curves for Cryptography”, talk 
> given at the interim teleconference meeting, April 2014.
> http://patricklonga.webs.com/Presentation_CFRG_Selecting_Elliptic_Curv
> es_for_Cryptography.pdf
>
>
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>



--
"Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin