Talk:Decisional Diffie–Hellman assumption

Cryptography: Computer science High‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
High	This article has been rated as High-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as High-importance).

I find the following useful:

Decisional Diffie-Hellman (DDH) assumption: Given primes p,q such that q divides p-1. Let g be a generator of $\mathbb{Z}_p^*$ of order q. Then for sufficiently large values of p,q the tuple (g,g^a,g^b,b^ab) is computationally indistinguishable from (g,g^a,g^b,b^c) where a,b,c \in_R [0,q-1].--Bah23 15:24, 31 January 2007 (UTC)[reply]

I'm pretty sure there is an error in the section on groups in which DDH is supposed to hold. It mentions a cyclic group of order (p-1)(q-1), where p,q are safe primes which is (I think) supposed to refer to (Z/nZ)* where n=pq. However, if n=pq then (Z/nZ)* will be isomorphic to (Z/pZ)* x (Z/qZ)* and we'll of course have a subgroup isomorphic to V_4. Would the author of this content please clarify? Likely what was intended was the index 4 subgroup of quadratic residues mod p and mod q. Wes1138 (talk) 00:04, 8 February 2010 (UTC)[reply]

Incorrect claims[edit]

The article mentioned "The cyclic group of order $(p-1)(q-1)$ ", where $p$ and $q$ are safe primes.

I corrected this to "The cyclic group of order $(p-1)(q-1)/2$ of quadratic residues modulo $pq$ ".

The whole section was added in a single edit from 2007 by User:Blokhead and there are no references, so it is possible that there are other mistakes. I am not qualified to check the accuracy of this section. --Rowdyparks and sallyport (talk) 09:29, 13 July 2013 (UTC)[reply]

Good observation. It looks like the text was copied from page 2 of Boneh's paper, which clearly is wrong, since the multiplicative group modulo pq doesn't even contain a cyclic subgroup of order (p-1)(q-1). The group of quadratic residues has order (p-1)(q-1)/4 since any element has to be a quadratic residue modulo p and modulo q. Furthermore, one would also have to assume that the factorization of the modulus is unknown and hence also the group order. Thus I think it makes sense to remove the claim unless we can find reference that more clearly defines the assumption than Boneh's paper. 2A02:1205:C6BB:6880:390A:2016:3538:E4FF (talk) 14:30, 13 July 2013 (UTC)[reply]

I have to withdraw a claim I made above. I'm unsure if the factorization of the modulus can be known. 2A02:1205:C6BB:6880:390A:2016:3538:E4FF (talk) 14:44, 13 July 2013 (UTC)[reply]