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?

Improve this question
$\endgroup$
6
  • $\begingroup$ "up to 100 member" $\:$ Wow, that's huge! $\:$ \end{sarcasm} $\;\;\;$ $\endgroup$
    – user991
    Nov 18, 2013 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, 2013 at 11:13
  • $\begingroup$ @CodesInChaos Sorry, error in the equation. $K^{a^{-1}}$ $\endgroup$
    – LostAvatar
    Nov 18, 2013 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, 2013 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, 2013 at 11:21

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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