Consider the Encrypt-then-Authenticate Construction 5.6 . Assume M is strongly secure while we have no knowledge of the security of E. Consider the Authenticated Encryption Integrated Experiment in module 5.1. Explain why the Dec oracle in step 3(a) of the Authenticated Encryption Integrated Experiment will return failure except with negligible probability.

cEnckE(m)andtMackM(c) sender transmits the ciphertext c,t CONSTRUCTION 5.6 Let E=( Enc, Dec) be a private-key encryption scheme and let M= (Mac, Vrfy) be a message authentication code, where in each case key generation is done by simply choosing a uniform n-bit key. Define a private-key encryption scheme (Gen', Enc', Dec') as follows: - Gen': on input 1n, choose independent, uniform kE,kM{0,1}n and output the key (kE,kM). - Enc': on input a key (kE,kM) and a plaintext message m, compute cEnckE(m) and tMackM(c). Output the ciphertext c,t. - Dec': on input a key (kE,kM) and a ciphertext c,t, first check if VrfykM(c,t)=?1. If yes, output DeckE(c); if no, output . The authenticated-encryption experiment PrivKA,ae(n) : 1. A key k is generated by running Gen (1n). 2. A uniform bit b{0,1} is chosen. 3. The adversary A is given input 1n and access to two oracles: (a) If b=0, then A is given access to Enck() and Deck(). (b) If b=1, then A is given access to Enck0() and Dec(). A is not allowed to query a ciphertext c to its second oracle that it previously received as the response from its first oracle. 4. The adversary outputs a bit b. 5. The output of the experiment is defined to be 1 if b=b, and 0 otherwise. In the former case, we say that A succeeds