Probability and Information Theory - Cryptography and Network Security Video Lecture - Computer Science Engineering (CSE)

so welcome to today's class on
probability and information theory now
this is an extremely important field of
study and a huge field so today we shall
be trying to kind of concentrate on some
of the basic principles which are
necessary to understand the design and
analysis of ciphers so in today's talk
we shall be talking about the importance
of probability in cryptography and then
discuss about computational security now
and then follow it up with some
discussions on binomial distributions
and its applications and but the very
important birthday paradox and then
conclude with some concepts of entropy
and information theory now as we have
been discussing that you know if you
remember in our first class that we
essentially we are trying to understand
rather answer the questions to the I
mean we are trying to answer questions
of this nature like how probable is the
insecure event okay so you remember that
or in our example on the coin flipping
over telephone the question was like
what is the probability of a lease to
create X which is not equal to Y such
that FX and fi are essentially the same
so if you remember that we were I mean
the question was like worth Dallas
whether a lease is able to choose two
different x and y values such that the
outcome which is denoted by FX and FY
are the same the other question that we
tried to address was that what is the
probability that Bob can guess the
parity of X so that was the important
information and the question was that
further from the value of FX Bob is able
to extract out the information of the
parity of X so therefore these type of
questions will again and again appear in
the in the choir in I mean in the in the
course of when we are trying to design
and and also analyze the ciphers and
therefore the theory of probability is
quite central to the development of this
field so a good crypto system as we
discussed in the last last classes was
that it should produce a cypher text
which has got a random distribution that
that means that we should kind of look
as much random as possible to a
distinguisher
so therefore I mean it should not be
kind of detectable it should not be kind
of easily distinguished from a random
distribution so therefore it is I mean
in the interest so it has to be random
in the entire space of the cipher
next message and the thing is that if it
is perfectly random so let us remain I
mean leave it like perfectly random we
will try to make this notion more and
more concrete as we proceed and the
thing is that they there should not be
any information leakage okay though so
therefore a lot of terms are being
coined out here like information and
also the notion of perfect randomness we
will try to make these things more
concrete and more mathematical as we
proceed so but I mean now you just try
to kind of understand them intuitively
so it means that when it something is
like it's perfectly random so then
essentially it's like it's not giving us
any extra information right so therefore
the idea is that it has got zero
information content okay so like the so
therefore if you remember that we had we
talked about the magic function FX and
therefore if the function FX does not
leak any information or any or rather
any fact about the parity of X then it
we say that it does not blink any
information I mean it does not leak any
information okay and therefore this
information or rather the lack of
information is sometimes also referred
to as uncertainty of ciphers so we try
to kind of measure these terms like
perfect randomness information and also
uncertainty okay and we essentially rely
heavily on the theory of probability and
also develop the theory of information
using these probabilistic notions okay
so another important concept although we
shall will not be really going deep into
this is something the concept of global
security okay so something we just
called a semantic security is very
central and it is defined as follows
so remember Alice and Bob right so
therefore the idea is that Alice
essentially encrypts either 0 or 1 with
equal probability so therefore Bob knows
that either 0 is encrypted or 1 is
encrypted and the probability of
choosing is 0 and 1 is half okay now now
so therefore I mean Alice encrypts these
either 0 or 1 and since the result
inside Part C to Bob as a challenge so
now the now Bob has to essentially guess
from the channel from the challenge
without the decryption key then whether
0 was encrypted or 1 was encrypted okay
so if bob is not provided with a
ciphertext then what will what will Bob
do Bob will simply guess right
so now when we are when bob is provided
the ciphertext he is he I mean he should
not be able to guess any better than the
random guess okay so that's the idea I
mean if it is I mean if he is not able
to get I guess any better than the
random guess then we say when the
encryption algorithm which alice is
using is semantically secure okay so
therefore if we consider like I mean if
you just consider a simple kind of
stream cipher like for example you just
see that there is a kind of message
right and if I just and what Alice does
is that it chooses randomly a key value
and it creates a ciphertext
okay so therefore this message can
either be 0 or 1 okay so the key also
can be either 0 or 1 and in randomly
chosen so now this particular cipher
text is being provided to Bob and Bob
from this notion of from this ciphertext
value has to guess whether 0 was
encrypted or whether one was encrypted
so Bob knows from this if this is the
encryption algorithm with Alice uses
that Bob is either receiving him or it
is either receiving m bar okay because
the key can either take zero value or
one value yeah this comes in a very
simple case okay so now bothers to guess
whether 0 has been encrypted or whether
one has been encrypted and if Bob does
not have any information of the cipher
tape then Bob would have simply guessed
so in this case also I mean when Bob is
even provided with the cipher text the
probability of Bob being able to guess
whether the message is 0 or 1 if you'd
even then be close to half okay so
that's the idea of semantic security so
now
so therefore Bob is Bob or any topper
does not have any advantage over towards
the idea I ensure you should not have
any advantage over the random gates
okay so semantic security tries to
encapsulate or capture this particular
notion so we essentially have been
discussing about something just called
messages in distinguishability that is I
mean I mean the idea is very I mean
semantic security and messaging mystic
visibility at the same notions okay that
is these notions say that you are I mean
the attacker is not able to distinguish
between the encryptions of either a 0 or
a 1
okay but open I mean we essentially talk
about
or something which is called a
computational I mean computational
security so if you remember I mean we
will see that there are two ways you can
actually kind of model the attacker okay
you can either assume that the attacker
is kind of an unbounded adversary that
is all-powerful it has got large access
to large amount of resource and it can
do kind of large large computations okay
so that's the notion of an unbounded
attacker so you can make your security
algorithms which are protected against
an unbounded a target you can try to do
that the other thing which you can do is
that you can assume that in today's
computational power or today's world the
maximum computations which a part which
an adversary can do okay like what is
believed in today's thumb rule is that
if there is an NP is if there is any
algorithm because which requires more
than two power of eighty computations
then it is termed as infeasible okay so
for example if they can limit or bound
the attacker of today's world by say to
power of eighty computations and if you
can prove that a particular attack for
an encryption algorithm requires more
than two power of eighty computations
then we are happy as a designer okay so
that's the idea of it of a computational
security analysis okay that is I'm not
trying to really give you guarantees of
and security against an unbounded
attacker but we are trying to give you
security against a bounded adversary
okay anniversary which is bounded by
computational power and the advantage
the other advantage that you arrive I've
been apart from the simplicity is that
often you will find that when you are
trying to give security guarantees
against an unbounded adversary you may
end up in an encryption algorithm or a
technique which is not practical okay
but as we discussed that we also need
practical security that is the cipher
should be practical okay so therefore
for in order to make it practical it is
often advantageous to assume that the
adversary is actually not unbounded but
it is kind of bounded okay so therefore
that is the notion on the importance of
computational security analysis so you
try to make this idea I mean more clear
as we proceed so so therefore we define
a crypto system to be computationally
secured if the best algorithm for
breaking it requires at least n
operations where n is a very large
number
now another approach is to reduce the
problem so therefore this is another
approach which is often take
is to reduce the problem of breaking a
crypto system to a known problem like
factoring a large number to its prime
factors okay so therefore it is often
assumed that factoring a large number to
its prime factors the difficult problem
is they're quite hard problem okay
so although we do not have real proofs
for proving this fact but the idea is
that this particular problem has
withstood large number of analysis and
with to the long period of time and this
believe that it is fairly hard ok so the
approach which is taken is that when and
when a given crypto system is given I
mean for example if I just take the
example of an asymmetric crypto system
called RSA and somebody asks me to prove
the security of this system the approach
which is adopted is that is to kind of
reduce this problem of proving I will
reduce this problem of breaking this RSA
cryptosystem to this known problem ok
that is we do a reduction prove and show
that if this problem and the idea is
that if this problem is a difficult
problem then so is the problem of
breaking this RSA cryptosystem ok so
that's so these kind of proofs are
essentially kind of relative and they
are not absolute ok and there something
sometimes called prove by reduction so
we also see some examples of such kind
of security proofs in our class also so
probability is a good tool ok and it's a
kind of proof I mean tool is which is
kind of helps us to analyze the ciphers
ok so let us try to make the concepts
little bit more well-defined so imagine
that I mean there are some important
definitions one of them is probability
space ok so the priority space is kind
of a fixed set of points which is
arbitrary but it is kind of denoted by s
Oh open ok so let us consider the I mean
an example like suppose there is an
unbiased coin okay so the unbiased coin
can take two possible values so
therefore we define its sample space to
be the values like head and tail so it
can take either head value or it can
take either tail value okay and then we
define an experiment so the experiment
is defined for example as follows like
experiment t 1 is nothing but the
outcome of a toss ok so if you assume
that this is an unbiased coin then this
experiment what it does is that it
essentially chooses or samples out a
point from
sample space okay so therefore this
result can either be a head or it can be
a tail okay so I just choose this a
point from this head and tail okay so
similarly you can actually make this
example a little bit more complicated
and for even for this simplistic I mean
so the simple example I think we can
actually understand the concepts we can
understand the concepts quite well so
therefore I mean if I just make it kind
of a little general general then it will
look like this that is the probability
space is arbitrary but fixed set of
points okay for example the head and
tail it would be more than that also and
we denote that by s and what the
experiment does is that it's an action
of taking a point from s okay so it just
chooses a random point I mean to do the
point from this sample space
I mean if I'd I mean this is a sample
point which is called it's commonly
called the outcome of an experiment so
you toss a coin it's either head or a
tail where the head of the tail is a
sample point of the experiment
okay so let us try to make it a little
bit more kind of complicated so you have
got I mean not only I mean two
possibilities like hail or tail but what
you do is that you toss the coin for ten
number of times okay so therefore if you
toss the coin for ten number of times
then there are I mean several possible
outcomes right so therefore you know
that if you toss the coin for ten number
of times then it could be like it's a
sequence of heads and tails right it can
be head tail tail tail and so on deer
head or something like that right so
even you know all I mean the head by
zero or the tail by one you know that
there are actually how many possible
enumerations or possible outcomes there
are to power of ten possible outcomes
okay now if I'd if I denote in a
particular kind of event as saying that
the event is like five times head and
five times still there it means that
from all these sample points I am
interested in the probability of one
particular event okay so this particular
event like this head and tail can occur
actually in sudden possible ways right
so therefore it can be essentially we
can actually compute the number of times
exactly five times head Falls by simply
computing ten choose five okay so
therefore the probability of this event
that is the probability of this event
that there are five heads well
essentially nothing but 10 choose 5/2
power of 10 okay so this way of
computing the probability is something
that we have quite seen okay so
therefore if I kind of make it a rather
define it this is the classical
definition of probability that is if
there is an experiment which can have a
I mean which essentially yields one out
of n possible equally probable points
and that every experiment must in a
point of course and let M be the number
of points which form even e that the
probability of an event E is defined as
the ratio of M and n okay so there is a
statistical definition also now why do
we require the statistical definition is
something we can easily understand that
for example if I tell you that there is
an unbiased coin and if I tell you that
the probability of a head is 1/2 right
then that means that that does not mean
that if I toss the coin for 2 number of
2 times then one of them will be a head
it does not mean that what it means that
is that if you keep on tossing the coin
for a large large number of times then
the half of that number of times you
toss will be I mean at least
approximately half will be half we will
be head right so therefore the notion of
probability actually holds in reality
when you kind of repeat the experiment
for a large number of times so there is
actually a notion of statistics involved
in the way of in the way we are defining
probability okay so therefore suppose
there are n experiments and these are
carried out under the same conditions in
which the event E has occurred mu times
okay so for a large value of n so that
means this is important that is if I
repeat the experiment for a large number
of times then the even e is said to have
the probability which is denoted by
probability of e approximately equal to
MU by n okay so therefore what I do is
that instead of computing the
probability by finding out the outcomes
and the number of possible ways these
outcomes can come but we are what we can
do is that we can keep on repeating the
experiment okay so we find that if we
have actually repeated the experiment
for a large number of times and out of
them you number of times a particular
event has occurred then we can fairly
approximate its probability by the ratio
of MU by n so this is a statistical
definition and often useful for D&I for
analysis some of the very elementary
probability
rules are as follows now you know this
but is the kind of repeat recapitulation
that is probability of a union B is
equal to probability of a plus
probability of B minus probability of a
intersection B okay and if they are
mutually exclusive then we know that
probability of a intersection B works
out to 0 and therefore probability of a
union B is equal to probability of a
plus probability of B now this
particular rule is often handy in giving
us upper bounds of the probability of a
union B because we can say that
probability of a union B with a result
than equal to probability of a plus
probability of B okay because this
probability is definitely greater than
equal to 0 so and then we define the
corner we know the definition of
conditional probability where
probability of a given B so this
probability means that the event B has
occurred if the event we know that the
event B has occurred what is the
probability of a okay and the way it is
being computed is probability of a
intersection B divided by probability of
B now if a and we are independent then
what is the probability of a given B
that is its same as probability of a
right because in a does not really
depend upon the upon the outcome of B so
the probability of a intersection I mean
either a given me becomes equal to
probability of a when they are
independent and therefore probability of
a intersection B becomes equal to
probability of a multiplied by
probability of B so that is this receive
a and B are independent the probability
of a intersection B is nothing as
probability of a multiplied by
probability of B then there is a very
important law which is known as a law of
total probability if there are a I I
mean if there are s I mean any events
like a 1 in 2 and so on till en and if
the union of them is the sample space s
and if I know that kind of they are
mutually I mean non intersection
accepting that is C I and EJ cannot take
place together and therefore the
intersection of AI and EJ is equal to
the null set and and then for any event
a we can say probability of a is equal
to so what we do is that we take
probably multiplied probability of e I
that is the probability that the other
iith event has occurred with probability
of a given AI that is priority of a
given
that the und is occurred and then take a
sum over all possible I values okay so
the I runs from 1 to n okay
so this is also very handy rule for
bringing about computations so then we
know that in when we are talking about
cryptography we are essentially not
talking about a continuous probability
space we are actually talking about
discrete space okay so therefore in this
case the total possible sample points
can actually take some discrete possible
outcomes okay so it can run from x1 to
say x2 like till X hash yes okay hashes
is nothing but the number of elements in
the sample point okay and what we do is
that for each of these sample points we
actually define probability okay so
first of all we define something which
is called a random variable and so and
then we say that that this particular
random variable can take certain such
possible values and then we try to
assign a probability for this random
variable okay so you see that so if
there is a biscuit space s we have got a
countable number of points like X 1 X 2
and so on till X hash yes and then a
discrete variable what we do is it
nothing but I mean a numerical result of
an experiment okay so it is a function
which is defined on a discrete sample
space okay so for example I mean if I
say that for example of a discrete
variable could be like if there are some
points like X 1 X 2 and X hashes so
suppose we define a function like
suppose the value of x 1 I'm supposed to
imagine that all of them are binary
values like suppose there are four bit
binary values so there could be 16
possible such numbers like 0 0 0 0 0 0 0
to all ones to all 4 ones and we say
that we are interested in finding out
the probability that all of the that
what is I mean that is the numbers are
for example even okay so we know that we
will what we will do is that from all
these possible values we will try to
find out those binary values which end
with 0 okay so we define an experiment
and therefore this is the function is
defined on the discrete sample space
from sample space okay so what we do is
that now I mean let s be a discrete
probability space and X be a random
variable so X is a random variable and
we actually actually start finding
probability values for these random
variables okay so this random variable X
can actually take some what are the
possible values this random variable X
can take it can either take X 1 value X
2 value or till have X of X hashes okay
and what we do is that for each of these
possible values of the random variable
we assign a probability okay so we say
that X can take a value say the random
any well X can take the value of x1 with
the probability of say p1 the random
variable X can take the value I mean
take the value of x2 with the
probability of p2 the random variable X
can so on so like I mean so on take the
value of say X hash s with a probability
of P hashes okay so we can define the
probabilities like this so these
probabilities will be d skip
probabilities and you need to satisfy
two important properties one of them
means that each of this probability
values will be greater than equal to 0
that is they should not be negative and
the other thing is that the summation of
all these probabilities should be equal
to 1 okay
so therefore this probability is Italy's
I mean this should satisfy these two
properties ok and we can actually say
that these probabilities are I mean I
mean are essentially a map from the
sample space s to the set of real
numbers because the real I mean the
probability values are essentially
nothing but real numbers which lies
between 0 & 1 both sides included okay
so this is so so these are actually the
individual probabilities and this should
satisfy these two important properties
so I mean one of the very frequently
used distribution is something is called
a uniform distribution and we know that
in in this case all the probe all the
values like x1 delay x hashes are
equally probable so the random variable
X can take x1 or x2 or x3 or x hashes
with the same probability and the
probability is nothing but 1 divided by
1/2 s okay the next is said to follow a
uniform distribution and it is often
denoted like this that is suppose I say
that P choosing uniformly from s so
therefore it means that choose P
uniformly from s okay so this is a very
common notation which is useful so then
we actually define a very important
distribution which is called a binomial
distribution so it says suppose there is
an experiment and it
got two possible values or possible
outcomes like it could be either a
success or it could be either a failure
or a head or a tail and then we repeated
a repeat the experiments I meet the
imminently such experiments and these
are called Bernoulli's trials ok
Bernoulli trials and if I denote the
probability of a head to be P and the
probability of a tail to be 1 minus P of
course because the head and the tail
together if I add these two
probabilities should be equal to 1 and
what is the probability that there are K
successes in n trials okay so therefore
there are I repeat the experiments and
the question is what is the probability
that among the n trials there are
actually k number of successes and we
know that this quechua li works out to
this that is n choose K which means that
we choose the case access points and
then for I mean for case access points
the probability will be actually P
multiplied I mean P to the raised to the
power of K and the other since the other
points are failure points so there
should be also multiplied by 1 minus P
whole to the power of n minus K because
there are n minus K failure points ok so
this gives us the number of ways of to
having our number of way and what is
this gives us the number the probability
that there are K successes in n trials
ok now if a random variable Y takes
values like 0 1 to n ok so therefore 0 1
to n means if I say that this success
that is the number of successes in n
trials and I denote there that by a
random variable then this random
anywhere can take values from 0 that is
it can be that there are no success to n
that is all of them are successes okay
so therefore the random variable can
take random anywhere Y can take values
from 0 to n and and for values which
lies between 0 to 1 raise for P the
probability that Y and we say that the
probability that Y is equal to K which
means that there are K success is given
by n choose K P to the power of K
multiplied by 1 minus P whole to the
power of n minus K if this random
variable satisfies these probability
distribution then we say that Y follows
binomial distribution and this is a very
common and useful distribution okay and
then we define then we talk about
something is called a law of large
numbers very useful so it says that if
we repeat a trial
large number of times where n is suppose
infinity I mean intends to infinity and
we note the number of successes okay so
after the point the number of successes
will actually remain a constant and will
be actually computed by something which
is called the expectation and the
expectation is nothing by the number the
number of times you are repeating the
experiment multiplied by the probability
of success okay the P is the probability
of success so in that case I mean this
is often referred to the expectation of
the random variable so as it is told you
are the limit n tends to infinity the
probability that epsilon n by n minus P
is lesser than a very small number small
but fixed number and this problem this
probability is equal to 1 okay so
therefore this is something you just
call the law of large numbers which says
that if you defeat the experiment for a
large number of times then essentially
you will find that the number of times
you you get the Nemean the number of
successes will actually be found out by
computing the expectation of the random
variable okay so the expectation of the
random variable is x out gives us an
estimate about the number of times of
success of an experiment will occur if I
repeat the experiment for a large number
of times now this particular law and the
concept of binomial distribution has got
a very important application in the
field of cryptographic analysis okay so
for that let us kind of consider this
particular result okay so therefore it
says that let epsilon be an event in a
probability space X with probability of
epsilon is equal to being equal to P and
P is greater than 0 and what we do is
that we repeat we repeatedly we perform
the random experiment X independently ok
so what we do is that so what we are
saying here is this that is there is an
event epsilon so epsilon either the
event and there is a probability space X
okay so what we are doing is we are we
know that the probability that epsilon
occurs that is this particular event
occurs is actually given by P where P is
some nonzero value it's greater than 0
so what we then do is that we kind of
repeat this experiment okay again and
again so we repeat I mean we do the
experiment X once we do the experiment X
twice
and we need what we need is that we need
to find out we need to find out the
expected number of experiments the
expected number of experiments of X
until epsilon occurs the first time okay
so what we need is that we need the
expected number of experiments of X
until epsilon occurs the first time so
what we are interested is that we are
interested in a particular event okay
and what we know is that we know the the
the we know the probability of this
event okay and we need to find out the
number of times we would like to repeat
the experiment until we first get the
success okay the success is defined as
the fact that this event epsilon occurs
okay so what is I mean how do we I
compute that okay and we what we say is
that if this G is nothing but a but the
random variable it says that this is the
expected number of times this is the
expected number of experiments of X okay
until epsilon occurs the first time
okay and we what we will do is that we
will try to give you a proof or
developing proof that this expectation
EJ is actually given by the reciprocal
of P now what is the impact of this
result okay so suppose there is an
attack okay suppose you develop an
attack and you say that the probability
that this attack works has a complexity
of say 2 to the power of minus n okay so
that means you say that you can actually
find out the the fact that you can
actually find out the particular kind of
a particular key is a to power of minus
n okay so then these particular results
gives us a kind of indication that I if
I repeat the experiment or if I repeat
the attack for 1 by 2 to the power of
minus M number of times that is 2 to the
power of n number of times then I should
get the attack working at least once
okay that is after to the power of n
operations I should get the attack to
work so therefore that means that if for
example if I say you that for example in
AES if I say you that there has got
128-bit security and if I tell you that
okay therefore the probability that you
can actually make the attack work is to
power of minus 128 then immediately you
know that if I repeat the experiment for
2 to the power of 128 number of times
which is very huge you will get 1
success okay so therefore this actually
gives us and nice indication to find out
the experiment I mean so if there is a
kind of property which you can exploit
for an attack it gives you an estimate
about the number of times you need to
repeat the experiment to get a success
once okay and the proof of this is
actually quite simple and it follows
from the binomial distributions notions
and the idea is as follows like what you
do is that you find out probability of G
equal to the value of that G is equal to
T and you know that G equal to T means
that the I mean what we are what we are
can computing here is that the success
occurs at the th number of times okay
that is it occurs at the th instance
which means that the previous in
previous experiments right like till t
minus 1 has been
so therefore this probability can be
computed by 1 minus P bar I mean raised
to the power of t minus 1 because they
were all failures multiplied by P okay
and therefore the expectation of a G I
mean expectation of G by using the law
of large numbers can will be equal to
this probability multiplied by the
number of times you are repeating the
experiment okay so therefore you are
what you are doing is that you are
repeating this for T number of times and
therefore you multiply this by 1 minus P
to the power of t minus 1 and multiply
that by P now you note that this
particular T can be anything right it
can it can go from T equal to 1 then the
first time when you are doing the
experiment to T equal to infinity okay
so it can be a summation like this okay
and then we are actually not going in to
prove this but even you can follow that
this is actually equal to minus P
differential with respect to P of Sigma
1 minus P whole to the power of T okay
so this will work out like this where T
runs from 1 to infinity ok you can check
this that it actually gives you the same
value ok so then that read that for us
from simple differential calculus ok if
you differentiate this we will get this
right so now this means that if I take
this Sigma then this is nothing but
minus PD DP ok and I would like to add
this Sigma so there is 1 minus P to the
power of 1 plus 1 minus P to the power
of 2 plus 1 minus P to the power of 3 so
on till 1 minus P to the power of
infinity ok so you know that note that
since this value is less than 1 this
Sigma actually converges I mean the
summation actually converges and what we
get is GDP of 1 by P minus 1 ok and this
actually works out to 1 by P okay so
therefore from here we actually get an
estimate about the number of times we
have to repeat the experiment so that we
actually get we actually get this we get
this experiment to work ok so therefore
it is important to note this result
because the
actually gives us an idea about if there
is an experiments success define prime
exists experiments success probability
define then from there to get an
estimate about the number of times we
need to repeat the experiment to get
that to get that success or to get that
event okay so then we come to the next
important concept in today's class we
just call the birthday paradox okay and
birthday paradox is actually is again
quite central to the idea of analysis of
ciphers so consider a function f which
is a mapping from X to Y where Y is a
set of n elements and consider that this
class of students form X ok that is let
Y do you know what the birthday say 15
September is about the other person X
thus Y is the 3 I mean so therefore I
mean there are two there are two things
here I'd love one of them is X and the
other one is y ok so there's essentially
we are essentially considering a mapping
from X to Y so let us consider this
class of students from X like let us
consider that in this class there are X
2 ins
ok there is their experience and let us
consider that that there are possible
number of birthdays can be 365 so there
are 365 possible days of birthday ok so
let us choose a person say a and we know
that a will be mapped to a one of these
dates from this 365 ok so if there is
another person he will also you or she
will be mapped to another particular day
in among these 365 ok so the question is
that is if you consider for example what
we are essentially considering is that
we are considering the fact that there
can be two persons or six another person
so who essentially are born on the same
day ok so that is the collision of these
two birthdays so we can say that the
problem is like this that is we can
abstract out this problem and they as
this there is choose K pairwise distinct
points from X uniformly and define
coalition to be the event for I not
equal to GA where F X I is equal to fxj
and we check for the corresponding f x
i's when a collision occurs and clearly
the probability of a collision increases
if K is increased that is if I choose
large number of points that is if I
choose large number of students from the
class
then the probability of that they are
born on the same day also increases
right the question is now what is the
least value of K so we are actually
interested in the least value of K so
not the probability of a collision is
more than say epsilon so we would not
like to give a lower bound of the
probability okay so first of all you
understand there are two important
things one of them is this list value
and then we are actually giving a lower
bound of the probability okay so why are
we choosing the least value of K because
if I start increasing this K and if this
K is quite large then this probability
will obviously increase the probability
of collision will obviously increase but
what we are interested is in finding out
what is the least value of this K okay
so that this probability of these
collision occurs and then we are
actually also trying to give a lower
bound of this probability and is the
probability should be at least this much
okay so we do we would like to give an
answer to this question okay so in
talking about in the bird s term like we
are actually interested in finding out
what is the number of students which
should be in that class okay that is
what is the least number of students
which should be in that class so then
throw the probability that two of them
are born on the same day is say more
than half okay so that is I'm interested
in finding out that what is the least
size of the class so are there are two
students at least who are born on the
same day and the probability of this
fact is more than half okay it's more
than are greater than or equal to half
so we can actually compute this quite
easily and we can do this as follows
like the probability of no collisions
let us find that first in among this K
persons okay so we know that if there
are K persons okay that is if there are
kind of K persons in that class and let
us consider that this person is mapped
to a particular date that is his bicycle
basically born on the same day so if you
are considering the probability of no
collisions then it means that the second
person should not be born on this date
right so that means from 1 by 360 from I
mean from 365 days he can be born on 364
days okay so that is this is 364 divided
by 365 or that is 1 minus 1 by 365 okay
what about
the second person and third person the
second person cannot third person cannot
be born on this state or these states so
therefore his probability will be 1
minus 2 divided by 365 ok similarly if I
consider the last person that is that
this person then his probability will be
1 minus K minus 1 divided by 365 because
they are K persons in this set ok I'm
considering this list size of the same
okay so therefore this probability and
all of them are independent events so
that therefore the probability of no
collision among these K persons can we
find the found out by this by by this
right that is I multiplied 1 minus 1 by
365 with 1 minus 2 by 365 with 1 minus K
minus 1 by 365 and so on and therefore
this is like nothing by the product of
these probabilities okay now for a large
N and a small X ok we have got this
approximation that is 1 plus X by n is
nothing but e to the power of X by n so
therefore a large N and s 1 X this holds
so if I use this approximation then this
product R this is this product of I mean
a 1 minus I by 365 can be approximate it
as each of these terms is substituted by
e to the power of minus I divided by 365
and then we tried to find out the
product of these terms okay and this
actually works out to e to the power of
minus K into K minus 1 divided by 730
because when we are doing a product of
these terms because I mean the I mean in
the powers we are doing actually a Sigma
so if I do this Sigma then this Sigma of
- I to the power of 365 minus I by 365
will work out as this right see what we
are doing is this right that is I equal
to 1 to K minus 1
and we are multiplying like 1 minus I by
365 so that approximately I mean by
using the approximation is like I equal
to 1 to K minus 1 in to the power of
minus I by 365 okay so now when we are
doing in this product and this means
that what we are doing is e to the power
of minus I by 365 and then actually we
are doing a summation here right so that
means that it is kind of like e to the
power of 1 by 365 you take
it is like one plus two plus so on till
K minus one okay so that means that this
is nothing but e to the power of 1 by
365 into K into K minus 1 by 2 okay
there is a minus out so this minus will
come out so minus minus 1 by 365 into K
into K minus 1 by 2 okay so that is
nothing but e to the power of minus K
into K minus 1 divided by 730 ok so
suppose we say this probability so this
is the probability of that there is no
collision so what is the probability
that there is a call that is at least
one collision that is simple right there
is 1 minus e to the power of minus K
into K minus 1 divided by 730 and if I
say that this probability should be at
least equal to 0.5 then we can actually
get an estimate of this K by computing
or rather equating this to 0.5 ok that
means we are trying to say this
probability actually should be greater
than equal to 0.5 but in order to
compute the value of K let us assume
that this K I mean it has required
equate this to 0.5 and find out the next
period I find out an estimate of K we
can actually see this and I'm not really
going into this that is you can find out
like can do these calculations like this
that is 1 minus e to the power of minus
K into K minus 1 divided by 730 is equal
to 0.5 and therefore K into K minus 1
divided by 730 will be equal to Ln 2
okay so therefore you can actually do
this right so therefore what you can do
is that you can bring this like this
that into the power of minus K into K
minus 1 by a 730 will be equal to 0.5
and then if you take a log on both sides
then it works out to like K into K minus
1 by 730 is nothing but Ln of 2 and
therefore you can actually get K square
minus K will be equal to 730 into Ln 2
okay and therefore your if you neglect k
with k squared then k will be rough
equal to square root of 730 Ln 2 and
that will be approximately 23 so which
means that if there are I mean if there
are there's a random room of 23 people
then the probability that there are 2
persons with the same birthday is 0.5 so
this actually seems to be a paradox wine
and because one if I ask you like what
is the probability that there are two
people who are born on the same date is
actually very small right it is actually
1 by 365 so that's very small number but
we see that in a random room of 23
people the probability that there are
two persons which are born in the same
birthday is actually quite high it
actually is 0.5 and we will see that if
I increase this 23 people to little
larger then actually this probability
shoots up quite fast so that so now this
is a very kind of specific example but
you can actually work out a more general
case ok that is instead of 365 you can
have maybe 2 to the power of n possible
outcomes and then try to find out the
estimate of K but what we will find is
that this K will roughly be being
proportional to the square root of
proton number of possible ways so which
means that if you kind of need to do a
brute-force search of site 2 to the
power of n possible values then if you
apply the birthday paradox then this
gives you an estimate that after 2 to
the power of n by 2 random searches
there should be I mean so there is a
high probability that two of them will
actually result in a collision so this
particular paradox or this particular
analysis is used again and again do the
analysis of ciphers and develop with
security proofs and other other stuff so
there are a lot of applications like
deciding the bit length of the hash
function digital signature schemes are
have to be kept more than say 128 bits
it is use for doing crypt analysis like
index computation probably which
algorithms to solve something just call
the discrete logarithms problems this
will our these problems so we will
actually I mean try to find out a very
interesting application of the birthday
paradox
so it's something which is called cycle
finding algorithms ok so suppose there
is a kind of a linked list which is very
large and I am interested in finding out
a cycle in the in the linked list ok so
this is one question that is
that may appear okay so one way of doing
that is kind of take I mean go through
the entire link knees and kind of store
a huge amount of data and then you once
you see a reputation you report a kind
of cycle okay but can we do better than
that because what a bad or but the
birthday paradox says is that if you're
if you choose the elements in this list
at random and if there are kind of two
to the power of n possible elements okay
then after two to the power of n by two
possible searches or possible points
there is a quite high probability that
two of them will actually lead to a
collision okay and this what I'm saying
is this that is so con I mean suppose
you actually keep on just arbitrarily
randomly choosing up choosing the points
okay then we'll find that after some
point it may happen in the next I mean
you keep on kind of computing and you
will find and there will be a resulting
collision okay the moment you get a
collision you know that there is a cycle
so consider the function f from s to
itself okay that is you what you do is
that you start from X then what you do
is that you start from X 0 so a store
could be here and then you generate a
sequence by recursively last follows
like X I plus 1 is equal to F F X I and
you just keep on computing this value
the goal is to find a collision such
that X I and X they are same okay that
is X I and s they are resulting in the
same value so we can actually have a
birthday prior approach that is not if F
is random then the birthday paradox
comes into play and we expect a
collision after two to the power of n by
two points if s has got n points to the
power of n points so assume that the
cycle structure is like this that there
is a tail from X 0 to X s minus 1 and
there is a loop from XS to XS plus L ok
that is from X 0 to X s minus 1 you come
here this is the tail and then from the
next one that is XS to XS plus L there
is a kind of cycle okay so that means
this cycle has got a length of L ok so
now the question is how do you detect
this cycle so one way of doing in this
could be a tree based approach so what
you do is that you start storing the
sequence elements in a binary search
tree as long as there is no duplicate ok
so you keep on adding them to the tree
and as long as there is no duplicate now
therefore the first duplicate occurs
when x s plus L is to be inserted
because there
already excess to use insert into the
tree and the moment you get to insert X
s + L you know that there is a kind of
duplication and therefore you report a
collision now what is the time
complexity here we know that if you are
using a binary search tree then the
complexity will be around OS + L log of
s + L but whatever the space complexity
the space complexity is still OS plus L
so that means that that although the
runtime is optimal because actually you
cannot do better than this in terms of
time but the space requirement is quite
high
ok that is this could be an exponential
and large and this could be quite a
large value okay so therefore the so the
question is can I make the space
requirement place a very interesting
technique is being adopted for finding
out the cycles and very simple algorithm
I will discuss here it's called fluid
cycle finding algorithm and it works out
as follows and we will see an
application of this in context to
factorization when we discuss about
factorization so you see that what we do
is that we set y 0 is equal to X 0 and
we compute another sequence Y I plus 1
as F of f of Y I so instead of applying
once F I am applying twice F so the
input initial sequence is X 0 and we
said the maximum iterations is M so what
we do is that we start X is equal to X 0
and Y is equal to X 0 so we start at the
same point and then from all for all
these possible iterations that we have
set as the maximum value we compute X is
equal to FX and we compute twice for y
ok so that is we apply F twice and we
obtain the points so if we get a
coalition at some point like if x and y
is same then we say that there is a
collision between in2 i because you see
that what if we say that this X
sequences at a point
I know Y sequence is actually a point to
I okay and if you get so then you
actually say that ok there is a
collision otherwise you say that there
is a failure ok and you will feel see
that actually you have got quite good
chance of actually getting a collision
because of the simple fact that this
particular length that is the length of
the cycle will actually divide - I - I
okay we will actually divide this - I -
I
so this is actually a very useful
algorithm and it is often useful I mean
the often useful for doing analysis and
one of the reasons is that I mean I mean
again for example if you consider the
cycle lights like this right it looks
like a row so if you start from x0 and
you come till X s so this is suppose
this point is X s minus 1 and this is X
s and you keep on obtaining and then
this is again X S Plus L so therefore
the length of the cycle is L okay so
therefore there are some L successive
points here and therefore you know
immediately that there must be from the
L sub 3 points there must be 1 point
here call it I - ok which is divisible
by L so there are L successive terms so
therefore there must be one term I - ok
which L divides ok so therefore if L
divides I - then that means that L
divides - I - - I - ok so that is I -
itself so that means that if you kind of
compute the series of X like this that
is you compute X I - and if you compute
X - I - then that means that you will
essentially find out if you are
basically computing these values then
you may not be able to find out the
first time this particular collision
occurs but you will find out a succeed
point when the collision occurs okay so
therefore you will definitely get it you
will know that that will necessarily
give you this collision which will lead
to the direction of the cycle okay so we
will see this in one of our future
classes when we discuss about
factorization of factor when we discuss
about factorization so then we conclude
our talk with some notions of
information measurement so let us
consider a language of n different
symbols a 1 to a n and let us assign
assign independent probabilities like
probability of a 1 probability of a 2
and so on - probability of a n now these
probabilities must satisfy that Sigma of
these probabilities will be equal to 1
ok so what is the entropy of the source
is the entropy of the source s is
defined as H s is equal to Sigma or
probability of AI multiplied by log of
mean
logarithm of 1 by probability of AI base
2 okay so this actually gives us the
number of bits which are required per
source output okay so therefore this is
that this notion of entropy is often
useful for computing the information
content so let us consider some examples
if s outputs a are a 1 with probability
of 1 then HS will be equal to 0 because
your probability is equal to 1 so
therefore if I plug in probability 1
here then this logarithm computes to 0
and therefore this HS is 0 ok but if s
outputs anything works with equal
probability that is the probabilities
are 1 by n that is the source of uniform
distribution then this HS will compute
to 1 by n Sigma of logarithm in base 2
and that is nothing but logarithm in
base 2 ok so therefore HS can be thought
of as the amount of uncertainty or
information in each output from s so
consider like if you have got kind of a
C as a binary sequence of values like if
there is an N bit length ok then there
are to be part of n possible values here
and all these 2 to the power of n
possible values can can take Gangamma
can can be chosen okay and therefore the
probability of a particular sequence is
nothing but 1 by 2 to the power of n so
in that case the number of in that case
the number of number of kind of number
of kind of number of bits which are
there are in order to find out the value
of x is actually n so therefore you need
to kind of ascertain these n bits in
order to find out the value okay so
therefore you do not your so that is
essentially the amount of uncertainty or
the amount of information you need to
find out the value okay so therefore and
if we I mean if we think of the previous
example that is if s outputs a
particular a 1 with a probability of 1
that means you know that there is no
information there is no uncertainty okay
so therefore the uncertainty is 0 so
therefore in this case the uncertainty
was 0 but here the uncertainty is slower
than in base 2 okay that means if I say
that in this M right then I mean if is
outputs n symbols and if n is equal to
say 2 to the power of capital n then
which are denoted by n bits then this
logarithm will work out to be n so that
means that
I need to I mean there is an uncertainty
of Mbits which is there in HS okay so
there is an uncertainty of capital n
bits in the source s okay so therefore
this notion of entropy gives us an idea
about uncertainty or the more
information now I will leave you with a
question that is suppose that there are
four digit there is a four digit pins
and which are randomly distributed how
many people must be in a room such that
the probability that two of them have
got the same pin is at least half okay
so you can immediately understand that
you should have be applying but the
paradox to solve this problem so the
references that I have used are when
more mouse modern cryptography theory
and practice and some of the things we
have taken from algorithm kryptonite's
is by anti looks and by Bookman and
introduction to cryptography spring is a
swing y our book so next day's topic we
will take up the topic of classical
crypto systems and discuss about some
classical methods of doing cryptography
you