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

[Dan Brown <[e-mail]>]

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