Recall that in the challenge$-$response setting, the client and the server share a secret key. If somehow the key is stolen from the server then all is lost. It$$s desirable that the client and server have different keys Kc and Ks$,$ and the server key

Ks is public.

Consider the following protocol.

$$ Let $($K$,$ E$,$ D$)$ be a public$-$key encryption scheme. Run $($pk$,$ sk$)$$ K$.$ The server key Ks is pk$,$ and the client key Kc is sk$.$

$$ If the client wants to identify himself, the server picks a random nonce r $$$ $\{0,1\}$

n and sends C $$$ E$($Ks$,$ r$)$ to the client.

$$ On receiving C$,$ the client then computes r$\text{'}$ D$($Kc$,$ C$)$ and sends r$\text{'}$ to the server.

$$ The server accepts only if r$\text{'}=$ r$.$

This scheme is an attractive option for logging into a remote website from a laptop using a mobile phone as a second factor. The website displays C as a QR code on the laptop screen and the user scans the code using the phones camera. The phone decrypts C and displays the six least significant digits of r on the screen. The user then manually types the six digits into her web browser, and this

value is sent to the remote web site to be verified.

a$)$ For the scheme above to be secure$,$ the encryption scheme needs to be CCA$-$secure$.$ Explain informally why this is the case.

b$)$ Find a public$-$key encryption scheme that is CPA$-$secure$,$ but if we use it for the protocol above, a man$-$in$-$the$-$middle adversary can impersonate the client.