Symmetric Exchange Key Sharing

Question:

Suppose that there are 10000 = 10^4 banks and 10 payment card organisations (PCOs).

1. How many secret keys will be needed if each PCO shares a unique secret key with each bank?
2. How many extra secret keys will be needed if every two banks share a unique secret key?

For question 1, I figured that if there are 10,000 banks and 10 PCOs:

10,000 * 10 = 100,000.

For question 2, I need to calculate the number of keys if every 2 banks share a key (so I guess for 10,000 banks there would be 5,000 keys?)

5,000 * 10 = 50,000, right?

I recall that the solution could be calculated differently, something along the lines of 5,000(5,000-1)*10/2 but I don't understand the logic of this.

Could someone please explain?

(I would appreciate explanation of logic or a direction for research to understand because I feel like this should be quite straightforward and I am unsure).

Thank your for taking the time to read this!

• This is more of a pure math question. Your mistake is that 10,000 banks would not mean 5,000 keys. Let's take 3 banks, A, B, and C. If every 2 banks share a key, then you need a key for (A,B), (A,C), and (B,C). 3 not 3/2. If you play around with small numbers, you should be able to see how you get to the real solution. – Aman Grewal Dec 14 '20 at 19:17
• This might also help: en.wikipedia.org/wiki/Arithmetic_progression#Sum – cisnjxqu Dec 14 '20 at 19:18
• Each key between the banks represents a selection of 2 elements from a set. Do you know how to calculate the possible different selections? – kelalaka Dec 14 '20 at 19:22
• Analogy (pre-covid-19): $n$ persons meet. Each shake hands with all the others. How many handshakes? Hint: each of the $n$ persons does $n-1$ handshakes, and one hanshake serves two persons. – fgrieu Dec 15 '20 at 16:04

The underlying principle here is that of combinatorics. Think of banks and PCOs as abstract parties. Party $$A$$ has $$|A|$$ many members and party $$B$$ has $$|B|$$ many respectively. For each $$x \in A$$ we have $$|B|$$ secret keys which $$x$$ shares with members of $$B$$ meaning we have $$|A| \times |B|$$ keys.

In your first question, we assumed that for all $$x \in A$$ and $$y \in B$$, we know that $$x \neq y$$. I. e., The two parties $$A$$ and $$B$$ don't share any members! In your second question however, that assumption is not true since $$A = B$$ which means the party of banks sharing keys with the party of banks, id es, among themselves.

The question here is then how many ways to pick unique $$\{x, y\}$$ combinations from a set $$A$$. Well, this is just an $$n$$ chose $$k$$: $$\binom{n}{k}$$ problem. In this case $$k = 2, n = |A|$$.

How many secret keys will be needed if each PCO shares a unique secret key with each bank?

$$|A|\times |B| = 10^4 \times 10 = 10^5$$

How many extra secret keys will be needed if every two banks share a unique secret key?

$$\binom{10^4}{2} = \frac{10^4!}{2!(10^4-2)!} = \frac{10000!}{2(10000-2)!} = \frac{10000!}{2(9998)!} = \frac{9999 \times 10000}{2}$$