$(15$ Points$)$ There is nothing exclusively special about strings and XOR in one$-$time pad. We

can get the same properties using integers modn and addition modn. This problem considers

a variant of one$-$time pad, in which the keys, plaintexts, and ciphertexts are all elements of

$Z_n$ instead of $\{0,1{\}}^n.$

$($a$)$ What is the decryption algorithm that corresponds to the following encryption algo$-$

rithm?

Enc$(k,m)$:$c=(k+m)modn$

Show that the resulting scheme satisfies correctness

$($b$)$ Show that the above scheme satisfies one$-$time uniform ciphertext security

$($c$)$ It's not just the distribution of keys that is important. The way that the key is combined

with the plaintext is also important. Show that a scheme with the following encryption

algorithm does not satisfy one$-$time uniform ciphertext security

Enc$(k,m)$:$c=(k*m)modn$

$(10$ Points$)$ Alice is using one$-$time pad and notices that when her key is the all$-$zeroes string

$k=0^n,$ then Enc$(k,m)=m$ and her message is sent in the clear! To avoid this problem,

she decides to modify KeyGen to exclude the all$-$zeroes key. She modifies KeyGen to choose

a key uniformly from $\frac{\{0,1{\}}^n}{\frac{?}{?}}\{0^n\},$ the set of all $n-$bit strings except $0^n.$ In this way, she

guarantees that her plaintext is never sent in the clear.

$($a$)$ Describe an attack demonstrating that the modified scheme does not satisfy one$-$time

uniform ciphertext security$(15$ Points$)$ There is nothing exclusively special about strings and XOR in one$-$time pad. We

can get the same properties using integers modn and addition modn. This problem considers

a variant of one$-$time pad, in which the keys, plaintexts, and ciphertexts are all elements of

$Z_n$ instead of $\{0,1{\}}^n.$

$($a$)$ What is the decryption algorithm that corresponds to the following encryption algo$-$

rithm?

Enc$(k,m)$:$c=(k+m)modn$

Show that the resulting scheme satisfies correctness

$($b$)$ Show that the above scheme satisfies one$-$time uniform ciphertext security

$($c$)$ It's not just the distribution of keys that is important. The way that the key is combined

with the plaintext is also important. Show that a scheme with the following encryption

algorithm does not satisfy one$-$time uniform ciphertext security

Enc$(k,m)$:$c=(k*m)modn$

$(10$ Points$)$ Alice is using one$-$time pad and notices that when her key is the all$-$zeroes string

$k=0^n,$ then Enc$(k,m)=m$ and her message is sent in the clear! To avoid this problem,

she decides to modify KeyGen to exclude the all$-$zeroes key. She modifies KeyGen to choose

a key uniformly from $\frac{\{0,1{\}}^n}{\frac{?}{?}}\{0^n\},$ the set of all $n-$bit strings except $0^n.$ In this way, she

guarantees that her plaintext is never sent in the clear.

$($a$)$ Describe an attack demonstrating that the modified scheme does not satisfy one$-$time

uniform ciphertext security