$(((((($Slide $4.$

$|$K$|<|$M$|,$ so no perfect secrecy$.$ Ideally $|$ K$|<<|$ M $.$

$$Efficient adversary: will equate to Probabilistic Polynomial Time $($PPT$)$

$$Single cipher text c leaks information about plaintext

def

M$($c$)=\{$m$|$m $=$ Deck$($c$)$ for some k $$ K$\}.$

$()$

Such brute force computation requires O$|$ K$|)$ time so not efficient$)\}\}\}\}\}\}\}\}$

Question $1.$ In slide $4$ of module $3\mathrm{.}1$ it is claimed that $|$M$($c$)|<=|$K $|.$ Explain why we cannot replace $<=$ by $<$ in this assertion.

Slide $9$

DEFINITION $3\mathrm{.}14$ Let G be a deterministic polynomial$-$time algorithm such that for any n and any input s E $\{0,1\}$n

$",$ the result G$($s$)$ is a string of

length l$($n$).$ G is a pseudorandom generator if the following conditions hold:

$($Expansion$.)$ For every n it holds that ln$)>$ n$.$

$($Pseudorandomness$.)$ For any PPT algorithm D$,$ there is a negligible function negl such that

Pr D$($G$($s$))=1]-$ Pr$[$D$($r$)=1||<$ negl$($n$),$

where the first probability is taken over uniform choice of s $\{0,1\}$n and the randomness of D$,$ and the second probability is taken over uniform choice of r $\{0,1\}$e$($n$)$ and the randomness of D$.$

We call l$($n$)$ the expansion factor of G$.$

Question $2.$ A pseudorandom generator is defined to be a deterministic algorithm $($slide $9,$ module $3\mathrm{.}3).$ Consider the use case for pseudorandom generators in Figure $3\mathrm{.}2($slide $5,$ module $3\mathrm{.}3).$ For this use case would it be appropriate to consider pseudorandom generators to be randomized rather than deterministic? Explain.

Question $3$ The pseudorandomness criteria $($item $2)$ in the definition of a pseudorandom generator is defined with respect to a PPT distinguisher D $($slide $9,$ module $3\mathrm{.}3).$ Slide $12$ of module $3\mathrm{.}3$ shows that an exponential time distinguisher can carry out a brute force search. What can you say about the value of the security parameter n to make this attack computationally infeasible?

Slide $23$

CONSTRUCTION $3\mathrm{.}17$

Let G be a pseudorandom generator with expansion factor l$($n$).$ Define a fixed$-$length private$-$key encryption scheme for messages of length l$($n$)$

as follows:

$$ Gen: on input $1"$

$,$ choose uniform ki E $\{0,1\}"$ and output it as

the key.

$$ Enc: on input a key ki $\{0,1\}"$ and a message m $\{0,1\}($n$),$ output the ciphertext

c:$=$ G$($k$)$ Om$.$

$$ Dec: on input a key k $\{0,1\}"$ and a ciphertext c $\{0,1\}($n$),$ output the message

m:$=$ G$($k$)$ @ c$.$

A private$-$key encryption scheme based on any pseudorandom generator.

Question $4$ Consider Construction $3\mathrm{.}17($slide $13,$ module $3\mathrm{.}4)$ and the indistinguishability experiment on slide $14,$ module $3\mathrm{.}4.$ Suppose we relax the requirement of fixed length in Construction $3\mathrm{.}17$ and allow messages of length $<=$ l$($n$).$ Further we allow adversaries in slide $14$ to choose messages m$0$ and m$1$ of unequal length. Explain why such an adversary can succeed with probability $1.$

PLZ ANS BY QUESTION $1,2,3,4$ THANK YOU