Ffffff

Slide $12$

DEFINITION $12\mathrm{.}1$

A public$-$key encryption scheme is a triple of proba$-$

bilistic polynomial$-$time algorithms $($Gen$,$ Enc, Dec$)$ such that:

The key$-$generation algorithm Gen takes as input the security parameter

$1"$ and outputs a pair of keys $($pk$,$ sk$).$ We refer to the first of these as the public key and the second as the private key. We assume for convenience that ph and sk each has length at least n$,$ and that n can be determined from ph$,$ ski.

The public key pli defines a message space Mpk$.$

The encryption algorithm Enc takes as input a public key ph and message mE Mpk$,$ and outputs a ciphertext c; we denote this by c $+$ EnCpk$($m$).$

$($Looking ahead, Enc will need to be probabilistic in order to achieve meaningful security.$)$

The deterministic decryption algorithm Dec takes as input a private key ski and a ciphertext c$,$ and outputs a message m or a special symbol $1$ denoting failure. We write this as m:$=$ Decsk $($c$).$

Slide $14$

The eavesdropping indistinguishability experiment PubKA,$($n$)$:

$$Gen$(1)$ is run to obtain keys $($pk$,$ sh$).$

$$Adversary A is given pl$,$ and outputs a pair of equal$-$length messages mo$,$ m$1$ Mpk$.$

$$A uniform bit b e $\{0,1\}$ is chosen, and then a ciphertext c$+$ EnCpk$($mb$)$ is computed and given to A$.$ We call c the challenge ciphertext.

$$A outputs a bit b$\text{'}.$ The output of the experiment is $1$ if b$\text{'}=$ b$,$

and $0$ otherwise. If b$\text{'}=6$ we say that A succeeds.

DEFINITION $12\mathrm{.}2$ A public$-$key encryption scheme II $=($Gen$,$ Enc, Dec$)$

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

Pr$|$PubKAn$($n$)=1|<=$

$=+$ negl$($n$).$

Question $1.$

$[$S$]$ Definition $12\mathrm{.}1$ of a public$-$key encryption scheme $($slide $12$ of module $12\mathrm{.}1)$ asserts in its item $2$ that $$Enc will need to be

probabilistic in order to achieve meaningful security.$$ Consider the eavesdropping indistinguishability experiment in slide

$14$ of module $12\mathrm{.}1.$ Explain how the adversary will succeed with $100\%$ probability if Enc is deterministic, so that in step $3$ of

slide $14$ we have c :$=$ Encpk$($mb$).$

Question $2$

$[$S$]$ Assume that Enc in Definition $12\mathrm{.}1$ is indeed probabilistic. Suppose the randomization is O$($n$2)$ where n is the security

parameter. Explain how a PPT adversary in the experiment of slide $14$ of module $12\mathrm{.}1$ will succeed in polynomial time.

Assume the adversary knows the randomization scheme used in Enc.

$($ Plz plz plz do not use chat gpt i ll do upvote $)$