Understanding Stream Ciphers: Encryption with Short Keys Using Pseudo-Random Generators

[Music] hello everyone welcome to lecture nine the plan for this lecture is as follows

in this lecture we will consider the notion of stream cipher where we will see how to encrypt long messages using

short keys with the help of pseudo-random generators and we will also see the restrictions imposed by

stream ciphers namely we will see that stream ciphers does not support key reusability for this we will also

introduce the notion of multi message security so on a very high level stream cipher you can imagine as if it is a

pseudo one-time pad so just quickly recall the one-time pad scheme where the message space key space and ciphertext

space all consist of bit strings of length big L bits the key generation algorithm outputs a uniformly random key

of size L bits and to encrypt a message of size L bits you simply perform the XOR of the message with the uniformly

random key and the decryption operation is just the XOR of the ciphertext with the key now in this stream cipher the

key space is going to be set of all possible strings of length little L we are little L is going to be much much

smaller than the Big L so the we have now two different spaces here the key space is different and the message space

and the cipher text base are different the message space and the ciphertext space consists of all strings of length

bigger bits your Big L is significantly larger than little L so the first change that we are going to make in the stream

cipher compared to the OTP is that the key generation algorithm is now going to output a key which will be of size

little L bits instead of Big L Brits and to perform the encryption operation we will actually XOR the message with the

output of a PRG invoked on the key generated by the key generation algorithm so in the stream cipher we

assume that we also have a secure PRG extending or stretching little L bits to an output of Big L bricks so by running

the pseudo-random generator on the seed K L on key on the key K we generate the mask and that mask is exhorted with the

message and that produces the ciphertext the same operation we perform at a decryption rate so in stream cipher we

have different nomenclature followed in the literature the we have few sources which says that the entire encryption

process is called a stream cipher whereas we have other sources which says that the instant Asian of the

pseudo-random generator is called a stream cipher now irrespective of whether we are

following definition 1 or definition two the important thing is that the message M is actually exhort with the outcome of

the pseudo-random generator on a uniformly random seed which is of much smaller size compared to the message

size now the reason that this whole encryption process or this whole system is called a stream cipher is that the

bits of the plaintext all the bits of the plaintext need not be known in advance that means for moment imagine

that your capital L is say thousand right that means you want to design an encryption process which can encrypt

messages of thumbs length thousand bits and for instance imagine that you have got a message you have got you have

obtain only say the first hundred bits of your message right so since you have only the first hundred bits of the

message what you can generate it you can actually run the algorithm G and produces the first hundred output bits

of your algorithm G on the input K and that actually constitutes the stream with which you can actually exhort the

first hundred bits of the message and send it to the receiving end next if you receive the next few bits of the message

you can produce the next few output bits of the algorithm G on the same input K to produce the next sequence of pads

which can use with which you can exhort the next sequence of bits of the message and so on so you can imagine that

actually your algorithm G is producing the sequence or a stream of pads depending upon the sequence of bits of

the message which are available to you and that's why it is called as stream cipher the whole message need not be

available to you in at once so now let's analyze that why this stream cipher is secure so the claim that we want to make

here is that if your algorithm G is a secure PRG then the stream cipher that we have designed is semantically secure

that means it is computationally indistinguishable in the cipher text only

that model and the proof intuition for proving disclaim is as follows what exactly is the difference between the

one-time pad encryption scheme and encryption scheme that we are following in stream cipher well the only

difference is in the stream cipher the pad or the pad with which we are actually masking the message is actually

pseudo-random whereas the pad which is used in one-time pad is truly random that's the only difference between the

two encryption process that means we already we have already proved that in the context of one-time pad no

distinguisher can distinguish a part whether the ciphertext C is an encryption of m0 or m1 except with

probability 1 by 2 we expect almost the same to hold even for the stream cipher that means no polynomial time

distinguisher should be able to distinguish a part whether it is seeing an encryption of m0 or whether it is

seeing an encryption of m1 because if we have a distinguisher who can distinguish a part and encryption of m0 from an

encryption of m1 with a significant probability better than half that means that adversary knows how to distinguish

G of K from a uniformly random key which is again a contradiction to the claim we are making about the security of the

algorithm G so we formally capture establish this intuition through a reduction based proof so we are given

the public lis known pseudo-random generator and we consider two encryption process 1 the stream cipher and the

second encryption process is the one time pad process assume for the moment you have an algorithm a write who can

actually win the indistinguishability game in the ciphertext only attack model against your stream cipher that means we

are making an assumption that our stream cipher is not semantically secure by that we mean we have an adversary a who

can win the ciphertext only attack model indistinguishability game with probability 1/2 plus non-negligible

using the help of the algorithm a we want to design another algorithm d who can distinguish apart a pseudo-random

sample produced by G from a truly random sample which will contradict the claim that we are making about the algorithm G

right so the algorithm D participates in an instance of the indistinguishability

based game for the PRG G where it is given a sample Y of size big L bits and it has to find out whether Y is

generated uniformly randomly or whether the sample Y is generated by running the algorithm G now what D does is it

actually participates in an instance of the COA indistinguishability game against the adversary so my

distinguished Rd is now playing a dual role here on the left-hand side part of the experiment of the reduction it is

actually participating as the distinguisher and trying to distinguish apart whether Y is pseudo random or

truly random whereas in the right hands are part of my reduction D is actually participating as a verifier of the COA

indistinguishability based experiment so as part of the COA based indistinguishability based experiment

adversary is throws a pair of sample of throws a pair of plaintext messages m0 or m1 as for the choice of the adversary

and the distinguisher d has to randomly encrypt one of these two messages either m0 or m1 so it decides the index of the

message which I denote by capital B and with probability 1 by 2 it could be either 0 or 1

now to encrypt the message m of B it has to actually select a pack right so what the distinguisher D does it uses the

sample Y which is given as a challenge for the distinguisher as the pad and it masks the message MB with the challenge

Y and produces the ciphertext C and gives it to the adversary a so now if you see what exactly is happening here

is if the challenge sample Y which is given to the distinguisher D is uniformly random then what the

distinguisher D has created here for the adversary is an instance of the OTP based indistinguishability experiment

because in that case the challenge ciphertext would be an encryption of the message MB

as per an instance of one-time pad because Y would be truly random on the other hand if the challenged sample y is

pseudo random in that case d basically has created an instance of indistinguishability coa based

indistinguishability experiment as per thus as per the stream cipher because in that case the challenged ciphertext C

would look like a challenge ciphertext which adversary would have seen by participating in an instance of coa

indistinguishability experiment against the stream cipher right notice that the distinguisher D does not

know whether it has created an instance of OTP experiment or whether it has created an instance of stream cipher

experiment right now in respect depending upon what type of ciphertext C is given to the adversary adversary a

gives an output that means it tells whether the ciphertext C is an encryption of message m0 or whether it's

an encryption of m1 now using the response of adversary a D has to find out what exactly is the type

of Y whether it is truly random or whether it is pseudo-random so here is the decision output of my algorithm D if

it sees that the adversary a has correctly identified what is encrypted in C that means the index B Double Dash

is equal to the index Big B then the distinguisher D labels the sample Y as if it is generated by a pseudo-random

generator otherwise it labels the sample Y as if it is generated by a truly random generator that's what is the idea

of this distinguishes now let's calculate the distinguishing advantage of the distinguisher

let's first calculate what's the probability that the distinguisher D we have constructed labels a truly random

sample Y as an outcome of a pseudo random sample well this is exactly the same probability with which an adversary

a participating in the COA indistinguishability experiment against one-time pad would have won the

experiment because if B little B is equal to 0 that means the sample Y is truly

dumb then the challenge ciphertext C which is given to the adversary is a spur and instance of OTP and with

whatever probability the adversary a would have won the indistinguishability game against OTP only in that case the

distinguisher D would have output B - equal to one because remember the strategy of D outputting B - equal to

one is if my adversary a can win the indistinguishability game so if a can win the indistinguishability game

against an instance of OTP then D would have labelled a truly random sample as a pseudo random sample right on the other

hand and and we know that the probability with which the a could win the COA indistinguishability game

against an instance of OTP is half on the other hand the probability that d outputs b - equal to 1 given that B is

equal to 1 is exactly the same with which my adversary a can win the COA indistinguishability game against an

instance of stream cipher and as per my assumption it is 1 by 2 plus some non-negligible probability right so

overall the distinguishing advantage of my distinguisher that we have constructed is the distinguishing

advantage or the difference in the absolute probability with which the adversary a could win the

indistinguishability coa indistinguishability game against an instance of OTP and against it from an

incident against an instance of stream cipher and if we take the absolute difference of these two probabilities it

turns out to be epsilon so if I assume my epsilon to be non negligible probability then it implies that I have

constructed a distinguish a D who can distinguish apart a truly random sample from a pseudo random sample with the

same probability and that will contradict my assumption that algorithm G is a secure PRG so even though we have

now solved one of the problems or the limitations of perfect secrecy namely we have seen a mechanism namely Simms

trifle where we could encrypt arbitrary long messages using short keys it turns out that we cannot get rid of the second

restriction that means cannot encrypt multiple messages using the same key with the help of stream

cipher so for this recall the single message semantic security so in the single message semantic security the

goal was that sender encrypted a single message using a short key and by eavesdropping the ciphertext we wanted

to ensure that adversary could not compute any function of the underlying plaintext whereas for the multi message

semantic security the requirement is that now sender would like to encrypt a sequence of messages using the same key

and the ciphertext are you obstruct by the adversary and we want to capture the noise intuition that seeing the

ciphertext does not help the adversary to compute any function of the underlying plaintext with a significant

probability and we can model this requirement as an indistinguishable T game so in this indistinguishability

game which we call as price KC or a mult because we want to capture the multi message security experiment the rules of

the games are almost identical as well as it was in the single message indistinguishability game the difference

now is instead of sending a pair of messages to the verifier the adversary will now submit a pair of vector of

messages of polynomial size and this basically captures the scenario that the adversary would like to distinguish a

part where the sender has encrypted one vector of message or the other vector of message right so the there is no

restriction on what type of messages adversary can put in these two vectors the only restriction is that the overall

size of the vectors is sum should be a polynomial function of your security parameter and if we consider the first

message in the zero vector and the first message in the first vector they should be of the same length and the same holds

for the I it message in the zeroth vector and diet message in the first vector and so on now what the verifier

is going to do is it will run the key generation algorithm out and obtain a uniformly random key and with the help

of the key it's going to encrypt all the messages in one of the vectors that means it will randomly choose one of the

vectors with probability 1 by 2 it could be either the 0 vector or the first vector and it's going to encrypt all the

message in that victim and the challenge for the attacker is to find out by saying the

ciphertext which vector has been encrypted whether it's our messages in the zeroth factor or whether it's the

messages in the first vector and the definition of our multi message securities we will say that our

encryption process is multi message secure in the COA attack model if for any polynomial time adversary

participating in this experiment there exists a negligible function such that the probability with which the our

adversary a could output be equal to B - that means it can correctly identify which vector has been encrypted is upper

bounded by some half plus negligible probability function in the security parameter again y1 by 2 because there is

always a guessing adversary who can just guess which vector has been encrypted and the extra negligible function here

is to model the fact that we are in the computationally secure world so are we are willing to give the adversary a

negligible X extra additional negligible chance that it can break our scheme write an alternate security definition

for the multi message security defin is multi message security in the COA attack model is that the distinguishing

advantage of any polynomial time algorithm participating in this experiment should be upper bounded by a

negligible function that means irrespective of whether it was the zero vector which is encrypted or whether it

is the first vector which is encrypted in the challenged ciphertext C the response of the adversary should be

almost the almost the same except with some negligible probability so either we can use this definition or we can use

this definition it turns out that both these conditions are equivalent to each other so now let's quickly see that why

stream cipher is not multi message secure right so here you are given a stream cipher and the main reason that

your stream cipher is not multi message secure is that the encryption process in the stream cipher is a deterministic

algorithm right that means if you encrypt the same message I am using the same key multiple times you are going to

get the same ciphertext C and that's basically loophole which any adversary could exploit in the multi message

security experiment right so what I'm going to show you is an instance of an experiment where any

adversary can break the notion of multi message security against your stream cipher so what the adversary is going to

do is it's going to submit a pair of vectors wherein the zero vector it has actually submitted two messages both

consisting of strings of length all zeros all zeros and in the second vector he has actually produced it has

submitted two messages where the first message is all zeros and the second message is all ones right and as per the

rules of the experiment the verifier is going to randomly encrypt one of randomly going to encrypt the messages

in one of these two vectors by using a key generated by the key generation algorithm and once the adversary sees

the challenge ciphertext is very simple for the adversary to pinpoint whether it is seeing the encryptions of the message

in the zero vector or whether it is seeing the messages in the first vector basically strategy will be to just

compare the first ciphertext with the second ciphertext and if they are same then it implies that he has actually

seen the encryption of the message in the zeroth vector otherwise it has seen the messages in the first vector and

this basically actually coming from the fact that in your sim trifer is deterministic so an encryption of the

message all zeroes is always going to produce the same ciphertext if it is encrypted multiple times with the same

key right so that brings me to the end of this lecture so in this lecture what we have seen is we have seen that using

the help of pseudo-random generator we can actually encrypt arbitrary long messages using short keys and this is

done to the help of stream ciphers however stream cipher does not gives us the security against multiple messages

that means it does not allow you to reuse the same key multiple times right so I hope you enjoy this lecture thank

you