October 1st, 2012, 08:00 AM
How do I show that the Decisional Diffie Hellman problem is not hard (with respect to) some ppt algorithm A? The outputs of the algorithm A are: the unit group of Zp, p-1 and a generator g. (p is a prime).
Hints are very much welcome!
October 2nd, 2012, 11:27 PM
Originally Posted by Jobb
Did you mean to ask how to show that DH is hard with respect to some probabilistic polynomial time algorithm A? The proof of DHKE security is based on the fact that finding the exponent of the parties' key(s) is a hard problem and is therefore computationally secure (and can only be solved with negligible probability).
Or are you showing that given a ppt adversary A running in some experiment with some kind of oracle that it's not secure? I'm not familiar with any indistinguishability game/experiment where an adversary outputs cyclic groups (I'm guessing it can query an oracle and find a generator for the groups or something?)