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

From: Dan Brown <[email-masked]>
Date: Mon, 5 May 2014 19:38:38 +0000

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

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 5 May 2014 12:52:21 -0700

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 <[email-masked]> 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
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Watson Ladd <[email-masked]>
Date: Mon, 5 May 2014 14:34:23 -0700

On Mon, May 5, 2014 at 12:52 PM, Michael Hamburg <[email-masked]> wrote:

> 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?
>
> 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
> 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.
>
> 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.
>
> (to solve a different problem …).
>
Why is this curve more secure? We don't have any idea for solving the CDH
given H(h^a) for attacker controlled a. That's true regardless of whether
or not a genuine DDH oracle exists, or just one for the key.

Sincerely,
Watson Ladd

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

---

From: Dan Brown <[email-masked]>
Date: Wed, 7 May 2014 17:41:32 +0000

Kiltz suggests

http://eprint.iacr.org/2007/036.pdf

to use a gap-group, albeit in the context encryption (KEM), and cites
earlier proposals.

So, at least, the idea to use a gap-group has been around for a while.

Kiltz mentions one of the benefits: public verifiability.  I have not quite
followed with what this means, but for now, I am guessing that it means
third parties can verify whether a ciphertext is valid (or, perhaps even a
key agreement session).  That sounds a bit like a signature.  Not sure if
that is a huge benefit, since one can instead just add on a signature, as
TLS servers do in TLS-DHE.

From: Cfrg [mailto:[email-masked]] On Behalf Of Dan Brown
Sent: Monday, May 05, 2014 3:39 PM
To: [email-masked]
Subject: [Cfrg] GapDH groups: a long-term research question

Dear CFRG List,

Best regards,

Daniel Brown