2
$\begingroup$

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$$ Have a look at the Image also, which provides the analogy

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The answer is correct for the situation where all parties need to communicate and where each party must be authenticated or send authenticated messages. Other use cases are possible. For instance, we're communicating here over a TLS connection where only the server is authenticated with a key (I used a cookie with token or password to authenticate). Web shops don't authenticate users at all (until they buy something), still the TLS connection is - hopefully - secure. $\endgroup$ – Maarten Bodewes May 20 at 23:59
1
$\begingroup$

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.
These keys are mathematically linked.

If you have 5 users, there are 5 Private keys and 5 Public keys.
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).

$\endgroup$
1
$\begingroup$

I spent about 400 hours in paint to make an illustration of this, hope it helps!

illustration

$\endgroup$

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.