Problem $2.$ Committing encryption. A common mistake is to assume that encryption commits the

encryptor to the encrypted message. Let $(E,D)$ be a cipher defined over $(K,M,C).$ Suppose

Alice chooses some kinK and minM and publishes $c$:$=E(k,m).$ This ciphertext $c$ is then

stored in a system that prevents any modification to $c.$ Later, Alice is asked to decrypt this $c$ by

revealing her key $k.$ We say that the encryption scheme is committing if Alice cannot produce a

$k^{\text{'}}$inK such that $D(k^{\text{'}},c)=m^{\text{'}}$ where $m^{\text{'}}m$ and $m^{\text{'}}$ reject.

a$.$ Give a complete game based definition for committing encryption. Your game need only

capture the commitment aspect of the scheme, not confidentiality. Hint: in your game, the

challenger does nothing, and the attacker should output two keys $k$ and $k^{\text{'}},$ along with some

other data.

b$.$ Let CTR denote counter mode encryption with a random IV$,$ with key space $K_e.$ Let $(S,V)$

be a secure MAC with key space $K_m.$ Let $(E^{\text{'}},D^{\text{'}})$ be the derived CTR$-$then$-$MAC cipher

whose key space is $K_e{K}_m.$ We know that $(E^{\text{'}},D^{\text{'}})$ provides authenticated encryption. Show

that $(E^{\text{'}},D^{\text{'}})$ is not a committing encryption scheme.c$.$ Let's show that any cipher can be made to be committing. Recall that in homework #$3$ we

defined the concept of a commitment scheme. Such a scheme has a commitment algorithm

commit : $KR{C}_{\text{c}\text{o}\text{m}}$ used to commit to a key kinK using randomness $rlar{r}^{R}R.$ The scheme

must be hiding and binding. Show that any authenticated encryption cipher $(E,D)$ defined

over $(K,M,C)$ can be converted into a committing encryption scheme $(E^{\text{'}},D^{\text{'}})$ defined over

some $(K^{\text{'}},M,C^{\text{'}})$ by using a commitment scheme. Your answer should describe algorithms $E^{\text{'}}$

and $D^{\text{'}}$ as well as the key space $K^{\text{'}}$ and ciphertext space $C^{\text{'}}.$ Briefly explain why your $(E^{\text{'}},D^{\text{'}})$

is committing and provides authenticated encryption.

d$.$ We can extend our discussion of committing encryption to public$-$key encryption. The only

modification to your game based definition from part $($a$)$ is that the adversary must also

output a single public key pk along with the ciphertext $c,$ and the released secret keys must

be compatible with this pk$.$ Show that ElGamal encryption is a committing encryption

scheme.