of an omnipresent factor-- Graph theory. Graph theory has been and is the
integral part of our lives. Normally, we do not observe the importance of
graph theory, but if we do, carefully, then the whole world is nothing but a
huge network. Right from people communicating from various parts of the
world to the constellations, brain mapping, neural networks, and what not?!!!
Graph theory has its own role to play. Graph theory is one such subject which
has deep rooted its existence in the field of computer security and not to
forget it has its role in most of the field’s today.
Amidst this growth, lets us pause and think for a minute—how do we feel
so secure while transacting on the INTERNET where we need to use ID's,
passwords and so on.....
Let us consider a hypothetical situation and try to learn many beautiful yet
very, very astonishing concepts in Graph theory. Along the way through this
example we shall learn many new concepts without our knowledge!!! Such is
the simplicity of this beautiful subject.
Imagine yourself to be in a situation like the one which follows:
Consider a bank, secondly the bank has an astonishingly intelligent guard,
finally but obvious the bank has a very huge client base and you are an
esteemed customer and an intelligent computer scientist.
The security guard has no aid what so ever to learn the customer's
authenticity. Each customer is given an unique id and the password is left to
choose by him/her(as of now we believe in supporting these two cases only!! ).
Since the user id is key to address/ recognize, but now how exactly the
security can come to know that the person having the id is the exact person
himself?
Since photo or etc isn’t available(the case is hypothetical), mentioning the
password is the only option.
So person who can tell the password is supposedly to be the authenticated
person!
Now, you come to the bank, security guard will stop you and ask you for your
id. Your id can be known by any one (it just requires one's smartness). So the
security asks you for your password. Now if you reveal your password ,the
whole idea of security through a password is blown away!!
Look here lies the problem :
you need to enter the bank, but to do that you need to convince the
security guard by authenticating yourself by telling him the password (which
is the only way out—remember??).
How can this be done?
Now here is a tricky solution.
In cryptography(a branch of graph theory), a zero-knowledge proof or zero
knowledge protocol is the solution. This is an effective method where in one
can prove to the other that his statement is true(by mathematics) without
revealing anything other than the truthfulness of the statement.
For zero-knowledge proof, graph theory provides an easy way by the vertex
coloring method. It is an assignment of labels traditionally called "colors" to
elements of a graph subject to certain conditions. In its simplest form, it is
a way of coloring the vertices of a graph such that no two adjacent vertices
share the same color; this is called a vertex coloring. The smallest number of
colors needed to color a graph by satisfying the above condition is called its
chromatic number.
Now for a graph having few vertices and arranged well, it’s easy to fill color
for the said criteria.
(pic)
So, here basically the pattern of edges we choose to connect them between
two vertices represents the password. Since set of vertices can be connected
in various ways, the way in which we select the number of vertices and
edges linking mechanism will form the foundation for you to create the
password. Once you are done “developing” your password, it will result in
a very complex graph which will be very difficult to decode. If the customer
is asked to reveal his password, then he has to displace the nodes of the
graph in a random fashion, but care has to be taken that no edges are broken down.
Now you show the graph ,by covering all the vertices and ask the security to
choose ,you tell him that you have filled in proper coloring, so that none of the
vertices sharing edges have the same color ( none but u can solve it easily,
method illustrated later)
The security now starts choosing , after several tries he may feel that
each time by mere coincidence or luck you have filled them correctly.
Mathematically the probability that security always lifts the correctly filled
edge is only ½. Owing to this fact there were equal chances of picking up
the wrong ones. This clearly convinces him that you have filled the colors to
the vertices perfectly.
Next question is--- What if this security sits and starts decoding and finally
figures out the correct password and turns rich?
This is practically impossible .Since this solution is an one way function, i.e.,
a function that is easy to compute, but nevertheless, it is difficult to compute
its inverse. In simple words, it means it’s easy to verify the solution but
extremely difficult to solve.
Consider a simple example of a one-way function which we do day-in and
day-out.
TYPING is actually a one-way-function.
Position your fingers on the keyboard in the natural position for typing "asdf
jkl;". Press the "Y" key on your keyboard without looking at the keyboard.
Very easy to do. Our brains are programmed to do this quickly what we call it
the learnt reflexes!
Now take your hands off of the keyboard. Point your right middle-finger down.
If your hands were on the keyboard, which key would you be pressing? Now
point your right pinky up. If you hands were on the keyboard, which key would
you be pressing? Much harder to do.
It is called the P Vs NP problem.
Another simple example is given below.
Say you are looking for a person with certain qualities such as fair,
handsome, intelligent, six-pack abs, IQ level > 140. This is an hypothetical
case, but if found its very easy to verify if he satisfies these criteria.
Now coming to the graph. Look at the graph below. As and when the vertices
and corresponding edges grow complexity increases to such an extent that it
is impossible to decode but can easily be verified.
The fig.2.(left pic) is just obtained by shuffling the vertices and their respective edges present in fig.3.(bottom-right pic)
By this way, the customer will ensure that his privacy is not curbed. If in
case, the guard is not yet satisfied with the customer, the graph is arranged
haphazardly and the above process is repeated. So by this, the guard, at
some point, will be satisfied( and exhausted!) by the customers identity.
Filling colors:(Technique now explained as to how we can do it easily, i.e.,
code our password)
Take three circles representing 3 colors , fill in the vertices to them to exhaust
all. Make complex pattern of your choice ,but not by connecting the vertices
present in the circle it self. Now pull aside the vertices in these circles to a
complex patter ensuring that no edges are broken. IT WILL RESULT IN A
COMPLEX GRAPH WHICH CANNOT BE DECODED EVEN AFTER DAYS
OF HARD WORK.
The graph show below is clear example of an one way function.
The three colouring process is easy to do one way but not the vice-versa
i.e .,it is easy to verify that if the edges have fulfilled the criteria but its
extremely difficult to colour the vertices to the said criteria.
No comments:
Post a Comment