# 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} $\;\;\;$ –  Ricky Demer 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
@RickyDemer Thanks for valuable content. –  LostAvatar Nov 18 '13 at 11:15
@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

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$.

So your optimization isn't possible in practice. Take a look at the alternatives at Can one generalize the Diffie-Hellman key exchange to three or more parties?. Thomas Pornin describes a two-round shared key algorithm based on DH and links to an single-round scheme that uses advanced crypto.

-
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
@poncho Could you describe how to use that oracle to break CDH? –  CodesInChaos Nov 18 '13 at 17:55
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
@DrLecter: oops, you are correct. Call me fumble-fingered... –  poncho Nov 18 '13 at 22:11