# Efficient parameters for group Diffie-Hellman

I want to implement a basic version of Diffie-Hellman key agreement for groups.

So, my key is $K=g^{abc} \mod p$. Following this, the parameters I would need to transfer would be $K_a = g^{bc}$ etc. The group may become large (up to 100 member), so I don't want to calculate every parameter anew and reuse $K$. Is there an efficient way to do this? I tried multiplying $K$ with $(g^a)^{-1}$ but that did not create a valid parameter since the resulting key was not correct.

Another idea I didn't have implemented yet is to calculate the key as $K=g^t$ with $t=abc \mod p$. I think, that in this case I could compute the inverse $a^{-1}$of $a$ in $Z_p^*$ and get my parameters as e.g. $K_a=K^{a^{-1}}\mod p$. Do you think this would work? Are there possible security issues in this approach?

• "up to 100 member" $\:$ Wow, that's huge! $\:$ \end{sarcasm} $\;\;\;$ – user991 Nov 18 '13 at 11:09
• You'd need to compute $K^{(a^{-1})}$. Only those who hold the private key $a$ can do this. Multiplying with $(g^a)^{-1} = g^{-a}$ would subtract $a$ from the exponent, not divide the exponent by $a$. – CodesInChaos Nov 18 '13 at 11:13
• @CodesInChaos Sorry, error in the equation. $K^{a^{-1}}$ – LostAvatar Nov 18 '13 at 11:16
• @RickyDemer It's large enough to make group DH annoying since you need one round of communication for every member in the group. – CodesInChaos Nov 18 '13 at 11:19
• @CodesInChaos Thanks, just tested it and works fine for me. Maybe convert this to an answer so I can accept it? – LostAvatar Nov 18 '13 at 11:21

You'd need to compute $K^{(a^{-1})}$. Only those who hold the private key $a$ can do this. Multiplying with $(g^a)^{-1} = g^{-a}$ would subtract $a$ from the exponent, not divide the exponent by $a$.
• To emphasize what CodesinChaos has said: given an Oracle that, given $g$ and $g^a$, computes $g^{-a}$, then you can solve the computational DH problem. Hence, if your (LostAvatar's) protocol could be done, it would also show that the shared secrets it generated was insecure. – poncho Nov 18 '13 at 17:38
• Refer to jmiller.uaa.alaska.edu/csce465-fall2013/papers/bao2003.pdf; the summary is: use the Oracle to compute $g^{a^2}$, $g^{b^2}$ and $g^{(a+b)^2}$ (using the Oracle to square is straight-forward). Obtain $g^{2ab} = g^{(a+b)^2} / (g^{a^2}g^{b^2})$, compute a modular square root, and $g^{ab}$ pops out. – poncho Nov 18 '13 at 19:15
• @poncho I guess in your first comment you meant: "given an Oracle that, given $g$ and $g^a$, computes $g^{a^{-1}}$"?, then you can solve the CDHP. – DrLecter Nov 18 '13 at 21:57