The decisional Diffie–Hellman (DDH) assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. It is used as the basis to prove the security of many cryptographic protocols, most notably the ElGamal and Cramer–Shoup cryptosystems. Definition Consider a (multiplicative) cyclic group of order , and with generator . The DDH assumption states that, given and for uniformly and independently chosen , the value "looks like" a random element in . This intuitive notion can be formally stated by saying that the following two probability distributions are computationally indistinguishable (in the security parameter, ): , where and are randomly and independently chosen from . , where are randomly and independently chosen from . Triples of the first kind are often called DDH triplet or DDH tuples. Relation to other assumptions The DDH assumption is related to the discrete log assumption. If it were possible to efficiently compute discrete logs in , then the DDH assumption would not hold in . Given , one could efficiently decide whether by first taking the discrete of , and then comparing with . DDH is considered to be a stronger assumption than the discrete logarithm assumption, because there are groups for which computing discrete logs is believed to be hard (And thus the DL Assumption is believed to be true), but detecting DDH tuples is easy (And thus DDH is false). Because of this, requiring that the DDH assumption holds in a group is believed to be a more restrictive requirement than DL. The DDH assumption is also related to the computational Diffie–Hellman assumption (CDH). If it were possible to efficiently compute from , then one could easily distinguish the two probability distributions above. DDH is considered to be a stronger assumption than CDH because if CDH is solved, which means we can get , the answer to DDH will become obvious. Other properties The problem of detecting DDH tuples is random self-reducible, meaning, roughly, that if it is hard for even a small fraction of inputs, it is hard for almost all inputs; if it is easy for even a small fraction of inputs, it is easy for almost all inputs. Groups for which DDH is assumed to hold When using a cryptographic protocol whose security depends on the DDH assumption, it is important that the protocol is implemented using groups where DDH is believed to hold: The