Problem $3.$ ElGamal tricks. Bob's corporate mail server publishes a public$-$key $p{k}_{\text{b}\text{o}\text{b}}$ so that all

incoming emails to Bob are encrypted under $p{k}_{\text{b}\text{o}\text{b}}.$ When Bob goes on vacation he instructs the

company's mail server to forward all his incoming email to his colleague Alice. Alice's public key

is $p{k}_{\text{a}\text{l}\text{i}\text{c}\text{e}}.$ The mail server needs a way to translate an email encrypted under public$-$key $p{k}_{\text{b}\text{o}\text{b}}$

into an email encrypted under public$-$key $p{k}_{\text{a}\text{l}\text{i}\text{c}\text{e}}.$ This would be easy if the mail server had sk $b_{\text{b}\text{o}\text{b}\text{,}},$

but then the mail server could read all of Bob's incoming email, which is undesirable.

Let $G$ be a group of prime order $q$ with generator ginG. Consider a minor variation of the

ElGamal encryption scheme from lecture where encryption using a public key pk :$=u=g^{}$inG

works as follows:

$E(pk,m)=\{larr{Z}_q,vlarr{g}^{},$klarrH$(u^{}),clarr{E}_{sym}(k,m),$ output $(v,c)\}.$

Here $E_{sym}$ is the encryption algorithm of a symmetric cipher with key space $K_{sym},$ and $H$ is a

hash function $H$:$G{K}_{sym}.$

Suppose that $p{k}_{\text{b}\text{o}\text{b}}$ and $p{k}_{\text{a}\text{l}\text{i}\text{c}\text{e}}$ are public keys for this scheme with corresponding secret keys

$s{k}_{\text{b}\text{o}\text{b}}=in{Z}_q$ and $s{k}_{\text{a}\text{l}\text{i}\text{c}\text{e}}={}^{\text{'}}in{Z}_q.$ To enable private translation of ciphertexts from $p{k}_{\text{b}\text{o}\text{b}}$ to

$p{k}_{\text{a}\text{l}\text{i}\text{c}\text{e}\text{,}}$ Alice and Bob get together to compute $$:$=\frac{}{{}^{\text{'}}}in{Z}_q.$ They give $$ to the mail server.

a$.$ Explain how the mail server uses $$ to translate a ciphertext $clar{r}^{R}E(p{k}_{\text{b}\text{o}\text{b}},m)$ to a ciphertext

$c^{\text{'}}$ for $p{k}_{\text{a}\text{l}\text{i}\text{c}\text{e}}$ for the same message $m.$ Justify your answer.b$.$ Show that $$ can also be used to translate in the other direction. That is$,$ if $clar{r}^{R}E(p{k}_{\text{a}\text{l}\text{i}\text{c}\text{e}},m)$

then the mail server can construct a ciphertext $c^{\text{'}}$ for $p{k}_{\text{b}\text{o}\text{b}}$ for the same message $m.$

Note that this is an unintended consequence that Alice did not want. It is not difficult to

modify the scheme to prevent this unintended feature, but we will not do that here.

c$.$ Show that if the mail server could use $$ to decrypt messages for Bob, then this would lead

to a total break of this ElGamal encryption scheme. That is$,$ suppose there is an efficient

adversary A that given $(\{$:$p{k}_{\text{b}\text{o}\text{b}},p{k}_{\text{a}\text{l}\text{i}\text{c}\text{e}},,clar{r}^R{?}^{-}E(p{k}_{\text{b}\text{o}\text{b}},m))$ as input, outputs $m.$ Show

that there is an efficient adversary $B$ that uses $A$ to break semantic security of this ElGamal

scheme $($without knowledge of $).$

d$.$ When Bob comes back from vacation, what should he do to make sure that Alice can no

longer read his emails?