The Gateway to Computer Science Excellence
+19 votes

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

  1. $2N$
  2. $N(N-1)$
  3. $\dfrac{N(N-1)}{2}$
  4. $(N-1)^{2}$
in Computer Networks by Boss (30.8k points)
edited by | 2.7k views

4 Answers

+35 votes
Best answer

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$


C choice.

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


by Veteran (431k points)
edited by

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.

@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$?

+10 votes

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      NC2   = N(N-1)/2 

by Loyal (6.9k points)
+4 votes

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

by Loyal (9.9k points)
+1 vote
Option C
by Active (1.2k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,302 answers
105,008 users