[Cfrg] Extra ECC desideratum: hard static DH and q-strong DH problems

[Dan Brown <[e-mail]>]

Three reasons that static ECDH key agreement should still be considered in
the CFRG curve recommendation:

1. Existing versions of TLS allow static DH for sever authentication, and
allow ephemeral re-use in DHE, and if I understand, these allowance would
carry if implemented with ECC.  Also, IKE allows ephemeral reuse.  
2. Other IETF protocols using ECC, e.g. CMS, may require static DH keys, due
to less interaction being available.  Perhaps JOSE uses static ECDH too?
3. Perhaps future versions of TLS will drop signature uses for
authentication, and instead use static DH keys for authentication.
(Something like in MQV or some other key agreement scheme.) Or, maybe IETF
will later adopt protocols that use the esoteric blinding properties of raw
static DH.

So, I think it desirable for the choice of curve to be one that fares well
static DH keys are used.  

In particular, there are two variants of the Diffie--Hellman problem related
to static DH keys whose difficulty potentially varies with the curve:

1. The static DHP from (http://eprint.iacr.org/2004/306)  If the static DHP
is easy for a given target public key, then the static DH applications above
are insecure for the target public key.
2. A variant (*) of the q-strong DHP from (http://eprint.iacr.org/2004/171)
If the q-strong DHP is hard, then static DH applications above resist a
total break attack in the sense that it is infeasible the adversary to
extract the static DH private key.

(*) the variant I have in mind is one in which that adversary succeeds when
it recovers the static private key, rather than performing some special
operation with it.

An algorithm from the 2004/306 eprint, and extended by Cheon, has opposite
effects on these two problem: making the q-strong easier, but providing
evidence that the static DHP is hard.  This effectiveness algorithm depends
on the factorization of n-1 and n+1 where n is the large prime factor in the
order of the group. I think it is desirable for both of these problem to be
hard, and I think that if n has the right properties, then we can get good
assurances for both problems.

If I had to choose which of the two problems to accommodate, I'd choose the
q-strong DHP, because one can just make a strong, but plausible assumption
that the static DHP is hard.  In other words, instead of assuming that the
DHP is hard, as usual, we further assume that the DHP is hard for every
single key, i.e. the DHP has no negligible fraction weak keys.  Assuming
this covers that case that your static DHP has enough entropy to be
unguessable, but not enough to escape falling into a subset that is
negligible fraction of all keys.  E.g. suppose your 256-bit key has only
128-bits of entropy (but is pseudorandom of course).

I also add that one of the security proof for TLS
(http://eprint.iacr.org/2013/339) relies on some assumptions PRF-ODH and a
similarly-named problem Strong DH from (http://eprint.iacr.org/1999/007)
which may have may relationship with the q-strong DH problem.  For example,
I've got a hunch that if we assume the variant of the q-strong DHP is hard,
then I think that imply the hardness of PRF-ODH and the ABR StrongDH
problems.  Because of the short time frame, I sharing this thought before
really confirming it.

Of course, this desideratum is a theoretical one, but some of the other
desiderata seem to be better-safe-than-sorry or helpful to make
implementations more robust, so I wanted to add it the list.

Also, Certicom has some IPR around the method.

Best regards,

Daniel Brown
Research In Motion Limited