$(10$ Points$)$ The following scheme encrypts a plaintext by simply reordering its bits, according

to the secret permutation $k$ :

Describe an attack demonstrating that the scheme does not satisfy one$-$time perfect se$-$

curity.

$(10$ Points$)$ Consider the following variant of one$-$time perfect security, where Eve can ob$-$

tain two ciphertexts $($on chosen plaintexts$)$ encrypted under the same key, called two$-$time

perfect security

We say that an encryption scheme is two$-$time perfectly secure if $AA{m}_{11},m_{12},m_{21},m_{22}$inM

chosen by Eve, the following distributions are identical:

$D_1$:$=\{c_1$:$=$Enc$(k,m_{11}),c_2$:$=$Enc$(k,m_{12})$;klarrKeyGen$(1^n)\}$

$D_2$:$=\{c_1$:$=$Enc$(k,m_{21}),c_2$:$=$Enc$(k,m_{22})$;klarrKeyGen$(1^n)\}$

Describe an attack demonstrating that one$-$time pad does not satisfy this security definition.

$(15$ Points$)$ Let KeyGen ${?}_1,$ Enc ${?}_1,$ Dec $\{$:${?}_1)$ and KeyGen ${?}_2,$ Enc ${?}_2,$ Dec $\{$:${?}_2)$ be two encryption

schemes such that only one of them satisfies one$-$time perfect security, but you don't know

which one. Using both $E_1$ and $E_2($but no other encryption scheme$),$ construct an encryption

scheme with one$-$time perfect security and prove its security.

$($extra credit, $15$ Points$)$ Prove that if an encryption scheme has $|K|<mi\; id="EditorElement\_3439487">|</mi><mi\; id="EditorElement\_3439489">M</mi><mi\; id="EditorElement\_3439491">|</mi><mtext\; id="EditorElement\_3439242"></mtext><mi\; id="EditorElement\_3439243">(</mi>$i$.$e$.$ there are fewer

possible keys than there are possible messages$),$ then it cannot satisfy one$-$time perfect

security. Try to structure your proof as an explicit attack on the scheme, i$.$e$.$ a distinguisher

between the distributions $D_1$ and $D_2.$

Hint: There is no restriction on the running time of the attacker. Exhaustive brute$-$force

attacks are therefore valid.