Slide $6$

Direct proof:

Construct adversary A as follows:

Mo $=(0\text{'},0)$ and M$,=(0\text{'},1)$

Challenge ciphertext C $=($G$,)$

Adversary A: if $4=$C$,$ then b$\text{'}=0$ else b$\text{'}=1$

If b$=0$ then b$\text{'}=0$

If b$=1$ then b$\text{'}=1$

So b$=$b$\text{'}$ with probability $1$

THEOREM $3\mathrm{.}20$

If Enc is deterministic and stateless the encryption scheme cannot satisfy definition $3\mathrm{.}18$

Slide $3$

The multiple$-$message eavesdropping experiment PrivKA, $($n$)$:

$$The adversary A is given input $1",$ and outputs a pair of

equal$-$length lists of messages Mo $=($mo$,1,...,$ mo$,$t$)$ and M$1=$

$($M$1,1,...,$ M$1,$t$),$ with mo$,$ i $=$ m$1,$ il for all i$.$

$$A key k is generated by running Gen$(1"),$ and a uniform bit bE $\{0,1\}$ is chosen. For all i$,$ the ciphertext ci $+$ Ench $($mb$,$ i$)$ is computed and the list C$\text{'}=($C$1,..,$Ct$)$ is given to A$.$

$$A outputs a bit b$\text{'}.$

$$The output of the experiment is defined to be $1$ if $6\text{'}=$ b$,$ and

O otherwise.

DEFINITION $3\mathrm{.}18$ A private$-$key encryption scheme II $=($Gen$,$ Enc, Dec$)$

has indistinguishable multiple encryptions in the presence of an eavesdropper if for all probabilistic polynomial$-$time adversaries A there is a negligible function negl such that

Pr PrivKAH$($n$)=1<=$

$-+$ negl$($n$).$

Question $1$

Consider the following statement: Theorem $3\mathrm{.}20($slide $6)$ establishes that a necessary and sufficient condition for an encryption scheme $$ to satisfy Definition $3\mathrm{.}18($slide $3)$ is that the Enc algorithm of $$ be randomized or stateful. Discuss.

Slide $8$

Suppose $0=$ Fk$,$ for any k

Then D will always output $1$

Pr$|$DFK $()(10)=1]=1$

Question $2$

In Example $3\mathrm{.}5($slide $8)$ we have the following claim

Suppose O $=$ Fk $,$ for any k

Then D will always output $1$

Explain why this claim is true.

Slide $8$

The CPA indistinguishability experiment PrivKA,$($n$)$:

$4,($n$)$:

$$A key k is generated by running Gen$(1").$

$$The adversary A is given input $1"$ and oracle access to Enck$(),$ and outputs a pair of messages mo$,$ my of the same length.

$$A uniform bit b e $10,1\}$ is chosen, and then a ciphertext c $<$ Enck$($mb$)$ is computed and given to A$.$

$$The adversary A continues to have oracle access to Enck$(),$ and outputs a bit $6\text{'}.$

$$The output of the experiment is defined to be $1$ if b$\text{'}=$ b$,$ and

O otherwise. In the former case, we say that A succeeds.

DEFINITION $3\mathrm{.}21$ A private$-$key encryption scheme II $=($Gen$,$ Enc, Dec$)$

has indistinguishable encryptions under a chosen$-$plaintext attack, or is CPA$-$secure$,$ if for all probabilistic polynomial$-$time adversaries A there is a negligible function negl such that

Pr PrivKAa$($n$)=1<=$

$1$

$=+$ negl$($n$),$

$2$

where the probability is taken over the randomness used by A$,$ as well as the randomness used in the experiment.

Let q$($n$)$ be a polynomial upper bound on number of queries A makes to the oracle

Question $3$

Slide $8$ introduces the notation $$Let q$($n$)$ be a polynomial upper bound on number of queries A makes to the oracle.$$ Does a PPT adversary A satisfy this requirement? Explain.

Slide $4$

CONSTRUCTION $3\mathrm{.}28$

Let F be a pseudorandom function. Define a fixed$-$length, private$-$key encryption scheme for messages of length n as follows:

$$Gen: on input $1",$ choose uniform k $\{0,1\}"$ and output it$.$

$$Enc: on input a key k $\{0,1\}"$ and a message m $\{0,1\}",$ choose uniform r E $\{0,1\}"$ and output the ciphertext

c:$=($r$,$ Fk$($r$)$ em$).$

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

m:$=$ Fk$($r$)$ @s$.$

A CPA$-$secure encryption scheme from any pseudorandom function.

Question $4$

In context of construction $3\mathrm{.}28($slide $4)$ let n$=128$ so the encryption scheme can be used to encrypt a message of length $128$ bits. How many possible ciphertexts exist for a single plaintext message and a fixed key k$?$ Explain.

$($Plz ans by $1,2,3,4$ thank you $)$