3
$\begingroup$

I have done a google search for "multi-party key agreement", and there doesn't seem to be anything more recent than about 2005.

Are there any practical multi-party key agreement protocols known?

To be more precise, I want a protocol which:

  • Allows multiple individuals to agree a single shared secret
  • An adversary cannot tell what the shared secret is by listening to the communications.
  • It should be authenticated so an active adversary cannot persuade a participant to communicate with a secret the adversary knows.

Note: I am aware of Multi-party Key Exchange protocol from lattice but a) that doesn't have any answers; b) I am not only interested in lattice cryptography (in fact, I would prefer something based on ECC or factoring).

Edit: Background I want a system for encrypting a conference call. If each caller sends their audio to every other participant with separately agreed keys, then the total amount of work required is $O(n^2)$ (and the work done by each participant is $O(n)$). If everyone agrees a single shared secret, then we might be able to reduce the amount of work required.

$\endgroup$
4
  • $\begingroup$ The first part of your question has the same problem as the other question: it is not a specific question and therefore largely off topic. I think generally cryptographers don't care about the date of protocols nor if they are famous or not. Additionally, asking for lists is explicitly off topic. The second part of your question is much better. You fail however to mention why lattice based crypto is not acceptable. Those kind of unexplained exclusions tend to put people off (such as the famous: "but I cannot use any libraries" on StackOverflow). $\endgroup$
    – Maarten Bodewes
    Aug 1, 2018 at 9:55
  • $\begingroup$ I don't need a list - I just need a good one. What I meant about the dates was there were a few papers proposing and knocking down proposals, and then silence. There are no blog posts "this is how you do multi-party key exchange". $\endgroup$ Aug 1, 2018 at 20:30
  • $\begingroup$ My preference for factoring/ECC is just that those are much better understood systems. If no-one has found a problem with an ECC-based protocol, it probably means it is secure. If no-one has found a problem with a lattice-based protocol, it may just mean that they haven't looked hard enough. $\endgroup$ Aug 1, 2018 at 20:32
  • $\begingroup$ @MaartenBodewes OTOH, if there is a good lattice-based protocol, I'll take that. $\endgroup$ Aug 1, 2018 at 20:33

3 Answers 3

5
$\begingroup$

Historically, both the difficulty and the risks involved in securely establishing shared keys in large networks has led to the invention of public-key cryptography. So you might first want to consider using digital signatures/asymmetric encryption instead of sharing the same secret between parties.

If you need all (or some) of the parties to collectively sign or encrypt a message, consider using threshold signature schemes with a Distributed Key Generation protocol. That will produce a key pair that is distributed among $N$ participants such that at least $k$ of them need to collaborate for performing a key operation. For discrete-log cryptosystems there's a paper by Gennaro et al that describes such a setup.

Edit: If you only need to establish a common secret (instead of a key pair) between all the parties, a simpler solution would be to use a generalized Diffie-Hellman key exchange instead. This works for honest participants with insecure communication channels. If the participants can be malicious, a more robust solution is described by Tseng, 2005.

$\endgroup$
1
  • $\begingroup$ Thanks. That's a couple of useful links. I think we will stick to pairwise key-agreement. $\endgroup$ Aug 8, 2018 at 12:51
2
$\begingroup$

I would recommend looking on the following protocols:

  • Burmester Desmedt
  • MD+P
  • Asynchronous Ratcheting Tree (bleeding edge)

All of them are called Group Key agreements and most of them assume that each participant is in a circle or are applied on a tree. The security of them is based upon Computational Diffie Hellman but in some cases can be used with Elliptic Curve Diffie Hellman.

$\endgroup$
0
$\begingroup$

What ia the problem with doing O(N^2) communication for key exchange. If after that everyone has the same key. The actual data can be sent only once.

A simple option would be: Everybody publishes a public key. Everybody picks a random key and encrypts it with everybody elses public key and shares.

Final key is XOR of all sub keys.

only the setup phase uses multiple communication.

Alternatively appoint a dealer which will coordinate a key among all parties.

$\endgroup$
1
  • $\begingroup$ This assumes secure communication channels and honest participants (i.e. issues with man in the middle attacks or participants learning other participants' keys). $\endgroup$ Aug 8, 2018 at 16:03

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.