[Cfrg] On Strong DH

[Watson Ladd <[e-mail]>]

Dear all,
My slides mentioned a reduction to the DDH. It's actually a reduction
to what has been called the strong DH assumption in some papers and
books, namely that calculating g^(ab) given g^a, g^b, and g is hard
even when you can check if your answer is correct. (It's this last
subtlety that I forgot about)

This is not the strong DH assumption as defined in the paper of Cheon!
That strong DH assumption is used in pairing based cryptography, and
assumes g^(ab) is hard to compute given an an oracle that calculates
it unless you feed the oracle g^b. Usually this is called the q-SDH,
or l-SDH, where l or q is the number of oracle queries allowed. It
generally shows up in the context of pairing based cryptography.

Strong DH (not the q-version), like CDH, is commonly believed as hard
as discrete log. Anyone with papers showing otherwise, please let us
know. I don't know of a reduction to CDH, although Gap DH, stronger
than Strong DH, appears true.

Sincerely,
Watson Ladd