Re: [Cfrg] GapDH groups: a long-term research question

Hi Dan,

This is an interesting proposal!  But I can see three major issues, none of which is insurmountable:

First, is there there reason to believe that GapDH is actually harder in a gap group?  Sure, you can actually run a proposed GapDH solver, but that seems like a downside as much as an upside, since it breaks CDH.  I suppose there is an argument from Bernstein’s “special curves might be better” line, but that would need more evidence.

Second, if the pairing is available to the attacker, then why not make it available to the user, i.e. why not make it practical?

Third, is there a way to avoid a large cofactor?

— Mike

On May 5, 2014, at 12:38 PM, Dan Brown <dbrown@certicom.com> wrote:

> Dear CFRG List,
>  
> What about EC groups with a pairing to an extension field with a degree high enough such that the DLP is infeasible in the extension field, but low enough such that pairing is feasible (but not practical)?
>  
> An upside is that proofs assuming hard GapDH problem become less theoretical, since a DDH oracle becomes available.  E.g. if a 2^128 adversary can be converted to a 2^129  DH solver by invoking the a 2^64 cost pairing 2^64 times, then we have a fairly concrete construction.
>  
> A downside is that it weakens the DDH, but then we always use a one-way PRF/KDF, so DDH attacks cannot be extended to PRF.  (This is the same as one argument to ignore Cheon attacks against schemes with static DH keys and hashed shared secrets.)
>  
> A second downside is the risk of using such a curve, because it is special.  Random curves would not be expected to have this property.
>  
> A third downside is that this may not be a well-studied idea, except by those who often think about the GapDH, and TLS seems to want something soon (to solve a different problem …).
>  
> I raised this now, because of the argument that CFRG should commit to recommending a single curve (per security level), that this recommendation should be long-lasting, and that the same recommendation should be used across multiple IETF applications.  To me, this suggests that CFRG should recommend a curve as secure as possible.
>  
> Best regards,
>  
> Daniel Brown
> Research In Motion Limited
> <image001.jpg>
>  
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg