0
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Aman Grewal Dec 14 '20 at 19:17
  • $\begingroup$ This might also help: en.wikipedia.org/wiki/Arithmetic_progression#Sum $\endgroup$ – cisnjxqu Dec 14 '20 at 19:18
  • $\begingroup$ Each key between the banks represents a selection of 2 elements from a set. Do you know how to calculate the possible different selections? $\endgroup$ – kelalaka Dec 14 '20 at 19:22
  • $\begingroup$ 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. $\endgroup$ – fgrieu Dec 15 '20 at 16:04
1
$\begingroup$

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}$$

$\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.