Talk:Decisional Diffie–Hellman assumption
![]() | This article is rated B-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||
|
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)
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)
Incorrect claims
editThe article mentioned "The cyclic group of order ", where and are safe primes.
I corrected this to "The cyclic group of order of quadratic residues modulo ".
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)
- 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)
- 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)