2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "up to 100 member" $\:$ Wow, that's huge! $\:$ \end{sarcasm} $\;\;\;$ $\endgroup$ – user991 Nov 18 '13 at 11:09
  • 1
    $\begingroup$ 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$. $\endgroup$ – CodesInChaos Nov 18 '13 at 11:13
  • $\begingroup$ @CodesInChaos Sorry, error in the equation. $K^{a^{-1}}$ $\endgroup$ – LostAvatar Nov 18 '13 at 11:16
  • $\begingroup$ @RickyDemer It's large enough to make group DH annoying since you need one round of communication for every member in the group. $\endgroup$ – CodesInChaos Nov 18 '13 at 11:19
  • $\begingroup$ @CodesInChaos Thanks, just tested it and works fine for me. Maybe convert this to an answer so I can accept it? $\endgroup$ – LostAvatar Nov 18 '13 at 11:21
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – poncho Nov 18 '13 at 17:38
  • $\begingroup$ @poncho Could you describe how to use that oracle to break CDH? $\endgroup$ – CodesInChaos Nov 18 '13 at 17:55
  • 1
    $\begingroup$ 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. $\endgroup$ – poncho Nov 18 '13 at 19:15
  • 1
    $\begingroup$ @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. $\endgroup$ – DrLecter Nov 18 '13 at 21:57
  • $\begingroup$ @DrLecter: oops, you are correct. Call me fumble-fingered... $\endgroup$ – poncho Nov 18 '13 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.