Why are in asymmetric cryptography as many keys as people involved needed?

Question

The question: "10 friends wish to establish secure communications between themselves using asymmetric-key cryptography. How many keys need to be known by each user?" was posed by my teacher. He says 10 keys are needed. I say only 2 keys are needed. As long as they have copies of the same keypair (keypair=2 keys, a public and a private), they don't need more than two. Why in the WORLD would you need more than a public key and a private key?

Edit:

I have already seen a few questions of this type by googling. Turns out this kind of question never specifies that the people of the group must be able to talk individually to each other. Nevertheless, the student must always assume they want to talk individually and secretly. That makes no sense to me, but that's reality. Ie: In public key cryptography, how many keys are required for secure communication between n parties?

In other words, in criptography, when they say communication between N entities, it is not actually communication between N entities, it's more like N private communications between each of the N entities.

Answer 1

Depends if "between themselves" means that they are sort of in a simple group-chat scenario. Then one private-public-key pair (i.e. RSA) would theoretically suffice (not factoring in the security), because they can all encrypt messages with the public key and decrypt messages with the private key that they all have an identical pair of it. In actual group-chat messaging applictions that's not the case due to security. You can look at this answer for more information how it actually works in group-chats.

If they all want to send / receive messages between them individually then they would have to know 10 keys in total. Their own private key (and their public key for other people to use) and 9 public keys from each other member. Alice would i.e. send a message to Bob using Bob's public key and (only) Bob can then decrypt it because he's the only one that has the corresponding private key to his public key.

Answer 2

Actually you are both wrong, assuming that each user wants to authenticate themselves individually and / or establish private conversations between pairs. Unfortunately this is assumption is missing from the question. If everybody is using (EC)DH then they need a key pair each to setup communication by establishing a session key. That means 10 times 2 keys = 20 keys. However, quite often key and key pair are confused, so the professor is really talking about the latter, only counting the private keys / key pairs, making 10 the correct answer.

If you establish a "master" user that you trust, and no entity authentication is required then you are correct. You need just one private key pair known to all, initially distributed by the master setting up the group. Then you can e.g. encrypt a session key with the public key and only those that have the private key can decrypt. Arguably this is not a good example of asymmetric cryptography though: the private key is now a shared secret, something that is common for symmetric cryptography rather than asymmetric cryptography. The sharing of the private key is required in this scheme, otherwise an adversary can join by identifying as one of your friends.

Note that just having 10 key pairs is not enough to authenticate all the users and setup 1:1 communication. It is also required to trust the public keys. Authentication is about proving you have (access to) a private key that belongs to a public key known to belong to you by the other user.

---

Note that I've talked about (EC)DH rather than RSA in the first section. It is common to setup (multiple) session keys in transport protocols rather than encrypting directly with the public key and decrypt with the private key. Of course, this requires a set of temporary keys in addition to the asymmetric keys.

It is possible to perform encryption / signature generation with just 10 key pairs, so session keys are not necessary. However, that's really not following good cryptographic practice. So I decided simply not to count the symmetric session keys.

Answer 3

Let's take a look at this from a higher level of view.

In asymmetric cryptography, private keys provide some form of authentication. Let $(e, d)$ be a public/private key pair respectively of a secure asymmetric encryption scheme $E$, and let $c = E_e(m)$ be the ciphertext corresponding to the plaintext $m$. If one is able to recover $m$ from $c$, then it's assured by the hardness of the underlying cryptographic scheme that $c$ is uniquely addressed to the holder(s) of $d$. Ignoring the issues arising by using an insecure medium for communication (e.g. the internet), if someone comes up to you with $m$, you have strong assurance that holder of $m$ is actually who you want it to be decrypted by, thus authentication.

In your case, if you want 10 parties in the network to be distinguishable, you would need 10 distinct key pairs because you would need to authenticate each of them separately. Otherwise, if you only want to address the group of users and you want to distribute the message to every member, you don't need separate authentication for each user, hence a single key pair held by all members is sufficient to distinguish the members of this group from the rest of the network.