# In public key cryptography, how many keys are required for secure communication between n parties?

In public key cryptography, how many keys are required for secure communication between n parties?

In my view the answer should be $n^2$.

Reason: There are ‘$n$’ Parties. Every Party has One (1) Public Key (for Encryption). Also, every party has $(n-1)$ private keys (paired) (for Decryption). So every party has $$1 + (n-1) = n\,keys,$$ and there are $n$ parties communicating. Number of Keys required is therefore equal to $$n * n = n^2$$

Now, am I correct? (Please be specific & also show the full logic & give proper explanations).

-
Why would every party have one public key and $n$ private keys? That would mean there are $n$ public keys and $n^2-n$ private keys in the total system. Usually there is one public key for every private key, so the answer you proposed in the question is wrong. It is correct, that each user will have a total of $n$ keys, but the distribution of public and private keys will be different, and there are duplicates over all users (the questions states how many keys are required, not how many keys are in the system). – tylo Jun 23 '14 at 11:58
@tylo SO Is it correct to say there are $n^2$ keys? Or In short, What are the no of keys (total)? – DWITI K DAS Jun 23 '14 at 12:08
It feels like you are so convinced that the answer is $n^2$ that you won't believe anyone until they say you are right. If we were talking symmetric key crypto then the answer would be $n^2$. Since we are talking asymmetric key crypto, the answer is $2n$. That is one of the major benefits of asymmetric crypto. – mikeazo Jun 23 '14 at 12:10
I have absolutely no clue what that diagram shows, but your thought process is totally wrong, yes. The assumption in your question is "there are public keys". and that means "they are secure". Questioning the assumption of the question is plain wrong. – tylo Jun 23 '14 at 12:22
I'm voting for closing this thread now, because it started to become a discussion. Besides being pretty much "below homework level", this question isn't beneficial for anyone else, because the basic understanding of the question is just wrong. – tylo Jun 23 '14 at 12:30

Asymmetric keys come in pairs. The public key of a pair can be used to encrypt data so that only the holder of the private key can decrypt it. If you had one private key, you'd also have exactly one public key that corresponds to it, so your answer of one public key and $n-1$ private keys per person cannot be entirely correct.

The question is somewhat ambiguous, but the answer that is probably expected is $n$ key-pairs, so $2n$ keys altogether. Each person has a single key-pair and knows all the public keys of others' key-pairs. They can encrypt data using any public key to be decrypted using that person's (single) private key.

The number of keys each person knows is about $n$ (one private key and $n-1$ public keys, plus their own public key if you want to count that). However, the total number is not $n*n$, because the public keys are all the same $n$ keys.

However, in the real world you would use hybrid encryption. In addition to the long term key-pairs there would also be a symmetric key for either every message sent or every session (in an interactive protocol like chat). Further, depending on the symmetric primitives used, you could need a second short term key for message authentication/integrity.

-
How is it 2n? I mean If there is a public private pairing then One doesn't need to Encrypt or decrypt his own message! So it must be 2n(n-1) then! There are not in pairs, as you said! – DWITI K DAS Jun 23 '14 at 10:39
Ya, But what about the Private keys (See my explanations also)? You are correct about the Public Keys, But Private keys have their own secrecy (& pairing)! – DWITI K DAS Jun 23 '14 at 10:48
Ya But to others, same Private key wont work then, there must be total of n^2 keys – DWITI K DAS Jun 23 '14 at 10:54
@DWITIKDAS, I tweaked it some, but honestly I've gone as basic as it gets. "Paired" probably refers to fact that a private key is paired with a public key, not to any pairing of two parties. – otus Jun 23 '14 at 12:03
Thanks Everyone! for their Contribution! – DWITI K DAS Jun 23 '14 at 12:28

This is how it works..

For every user, there is 1 Private key and 1 Public key.
The Private key is used to decrypt messages from other users.
The Public key is used by everyone else to encrypt messages for that user.
Each user would have a copy of everyone else Public keys, which means $n*(n-1)$ copies of the $n$ public keys on various systems to ensure mutual communication between all users, plus the $n$ Private keys.
The unique key count is $2n$, with $n^2$ distributed keys both Private and Public on various systems (assuming a user does not keep a copy of their public key once it is distributed).