# Minimum number of public and private keys depending on signature?

I'm trying to make sure I understand and intuit things properly here, so I'm going to be somewhat lengthy? With this, as I did a cursory search here and couldn't find exactly the case examples I'm looking at.

As we generally know, this is how public key crypto would be working.

Asymmetric: Two key pairs on each branch, e.g., Joe and Jill must each have a public and private key. The number of key pairs is N * (N – 1)

Symmetric: One key per branch, e.g., Joe and Jill share a single key. The number of keys for N managers is N*(N-1) / 2 implying exponential growth.

Our situation is as thus, and currently ignores man in the middle and other methods of attack that would require additional keys, and we, as a head of department want to communicate with (N-1) staff members and conducting a secure conversation (N total personnel including head of department, let's call them Smith)

1) If we want to send identical information to the other (N-1) using asymmetric cryptography, but also digitally sign the communication so that the other members know it's from Smith and has not been modified. Assume no compromising of keys and the message can be sent in the clear or encrypted.

--My initial thought is, let's say we have 10 personnel including Smith (N=10). Based on the above formula, that is 10*9 or 90 public/private key pairs, however we're going to digitally sign: do I need to just add 10 to the total, or is there something else?

2) The personnel (N-1) must be able to send information back to Smith using asymmetric; assuming the keys are known only to members of the group, how many public and private keys must exist? In this case, Smith does not need to verify the actual identity of the member sending the message. The actual message must be encrypted and all messages should be private with respect to all other members of the group, i.e., no member of the group can read another members messages to Dr. Cooper.

--On this, I want to assume that, it's 9*8, so there would be a lack of need for the key pair from the 10th (Smith) because they're only sending information back to him.

3) The (N-1) members of the group must be able to send information to Smith using asymmetric cryptography. Assuming the keys are only known to member of the group, what is the minimum number of private and public keys to accomplish the task? Smith must be able to verify the identity of each group member sending a communication.

--Again, I'm thinking the same formula of N*(N-1) is still necessary, but I also feel that it needs modification for Authentication and non-repudiation, only I've been unable to find clear information regarding this.

4) The (N-1) members of the group must be able to send information to the Smith using symmetric cryptography. Assuming the keys are only known to appropriate members of the group, what is the minimum number of symmetric keys to accomplish the task? Smith must be able to verify the identity of each group member sending a communication and verify each message has not been modified using the digital signature of the message hash.

--This one is a bit different; let's assume our actual N is the N-1, so 9. 9(9-1)/2 or 9*8 = 72 / 2 = 36 keys.

Long story short, what might I be missing?

I'm having a little trouble following your reasoning. I think your difficulty comes from an invalid initial assumption.

Asymmetric: Two key pairs on each branch, e.g., Joe and Jill must each have a public and private key. The number of key pairs is N * (N – 1)

No! It is in fact the main advantage of public-key cryptography that each participant only needs one pair of keys. For $N$ participants, the number of key pairs is $N$.

More precisely, each participant needs one pair of key for each purpose. Using the same keys for encryption and for signature can be ok, but it can also lead to trouble for various reasons:

• It can lead to protocol errors where a participant is tricked into signing something, but the thing in question was encrypted with the corresponding public key, and the signature reveals all or part of the content because the signature operation uses the same key that the decryption would.
• Conversely, a participant may be tricked into decrypting something, and the result may be used to forge a signature.
• Decryption and signature keys typically have different retention policies: you shouldn't keep signature keys around when you want to stop using them, but you often need to keep decryption keys for a long time to decrypt old messages.

Still, that's only two pairs of keys per participant if each participant both signs and decrypts messages. The point is that the number of keys does not grow super-linearly with the number of participants.

1) If we want to send identical information to the other (N-1) using asymmetric cryptography, but also digitally sign the communication so that the other members know it's from Smith and has not been modified.

When Alice sends a message, she encrypts it $N-1$ times, once with each recipient's encryption public key. Each recipient will decrypt their copy with their decryption private key. Alice signs the message only once, with her signature private key. Each recipient will verify the signature using Alice's verification public key.

That's a total of $N$ key pairs: $1$ signature key pair and $N-1$ encryption key pairs.

2) The personnel (N-1) must be able to send information back to Smith using asymmetric; assuming the keys are known only to members of the group, how many public and private keys must exist? In this case, Smith does not need to verify the actual identity of the member sending the message.

For $N-1$ participants to send encrypted data to Smith, only one key pair is necessary: the senders encrypt with Smith's encryption public key, and Smith decrypts with his own decryption private key.

3) The (N-1) members of the group must be able to send information to Smith using asymmetric cryptography. Assuming the keys are only known to member of the group, what is the minimum number of private and public keys to accomplish the task? Smith must be able to verify the identity of each group member sending a communication.

Each of the $N-1$ senders signs their own message with their own signature private key. Smith verifies using the sender's verification public key.

4) The (N-1) members of the group must be able to send information to the Smith using symmetric cryptography. Assuming the keys are only known to appropriate members of the group, what is the minimum number of symmetric keys to accomplish the task? Smith must be able to verify the identity of each group member sending a communication and verify each message has not been modified using the digital signature of the message hash.

Here, $N-1$ symmetric authenticated encryption keys are needed, or $2 (N-1)$ if you count encryption keys and authentication keys separately. There's the AE key that Alice shares with Smith, the AE key that Bill shares with Smith, the AE key that Charlie shares with Smith, etc.

• Huh, yeah, it seems like maybe I may have also put out some incorrect information, perhaps? The instruction/notes I have that I am reviewing puts it forth as I mentioned for the Asymmetric, which seemed, indeed, at odds with later information and information such as this. Is there ever a situation where that formula, the N*(N-1) is valid? – Jeffrey Johnson Sep 16 '18 at 22:08
• @JeffreyJohnson The only situation that comes to mind is if everybody wants to be anonymous with everybody. That is, when Alice talks with Bob, she doesn't want to reveal that she's Alice, and when she talks with Charlie, she doesn't want to reveal that she's Alice, and she also doesn't want to reveal to either that she's talking with the other guy even if Bob and Charlie compare notes. In such a scenario, each participant effectively has different identities, and each identity has its own keypair (or its own pair of keypairs). But there's still a single keypair per persona per purpose. – Gilles 'SO- stop being evil' Sep 17 '18 at 11:30

You would never need N(N-1) key pairs. The most you would need is 2(N-1) key pairs and only if you were going construct an ephemeral key exchange when communicating with each individual. And those keys would be deleted so they wouldn't be taking up space and would do very little in terms of increasing complexity. Honestly, for signatures you would only need N signing key pairs and if you don't care about forward secrecy you could also get away with N encryption key pairs. If all you care about is how few keys you can get away with, you can use a PGP-RSA style scheme and get away with N total.