GATE CSE 2015 | Set 1 | Question: 21

Question

Suppose that everyone in a group on $N$ people wants to communicate secretly with the $(\text{N - 1})$ others using symmetric Key cryptographic system. The communication between any two person should not be decodable by the others in the group. The numbers of keys required in the system as a whole to satisfy the confidentiality requirement is

• A. $2N$
• B. $N(N-1)$
• C. $\dfrac{N(N-1)}{2}$
• D. $(N-1)^{2}$

Comments

Same Question as this one:

https://gateoverflow.in/3384/gate2008-it-70

---

Removed from current syllabus

Answer 1

In symmetric key cryptographic system, both parties have access to key.
So, the first person has $\text{N-1 keys}$ with other $\text{N-1}$ people,
second one has another $\text{N-2}$ with $\text{N-2}$ people ( $1$ we already
considered ) and so on till $1.$

So, Total number of keys required $= N-1 + N-2 +\ldots + 1$

$=\dfrac{N(N-1)}{2}$

C choice.

Had we been using Public key cryptography we needed just $2N$ keys in the system. 

Reference: https://en.wikipedia.org/wiki/Symmetric-key_algorithm

Comments

I don't understand this. My point would be like this:

As they have asked the number of keys as a whole and not summed up on individual knowledge of no of keys for each person, hence what I could think of is:

As per symmetric cryptography we can communicate with a person secretly if we have his public key, and in turn that person will use his own private key to decrypt the message and no one else.

So each person posses a Public Key & a Private Key each, and so for N persons with 2 keys each.

the total number of keys in the system would be 2*N = 2N to suffice a confidential communication.

To think of the whole system I would think like: I have a huge whiteboard on which N public keys are written and each N person possesses his own private key which is secret.

Please correct me if I am wrong somewhere.

---

You are correct but that is for Public Key cryptography.

https://en.wikipedia.org/wiki/Symmetric-key_algorithm

---

@Arjun Since both parties participating in a communication share one secret key, I assume that each party is in possession of a copy of the key.

Also, the inclusion of the phrase "as a whole" in the problem, and $N(N-1)$ as one of the option do require your comments on why the number of the secret keys used per communication not be counted as $2$?

Answer 2

IT is complete Graph of N vertex 

where each edge B/W two Vertex need Distinct Key

Total number of Edges in Complete Graph is      NC₂   = N(N-1)/2 

Comments

correct.

Answer 3

In Symmetric Key Cryptography, access of key is with both the parties. It implies every person needs to communicate N-1 other users using different keys i.e 1+2+3...N-2+N-1 This is like number of edges needed in a complete graph with N vertices is N(N-1)/2. Answer is therefore C