Thread: Diffie Hellman

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    1
    Rep Power
    0

    Diffie Hellman


    Hello,

    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!

    Regards,
    J.
  2. #2
  3. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    11
    Rep Power
    0
    Originally Posted by Jobb
    Hello,

    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!

    Regards,
    J.
    Hi J,

    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?)

IMN logo majestic logo threadwatch logo seochat tools logo