Can you help me prove perfect secrecy? I'm actually new to cryptography and a friend of mine requested that I should read the Katz and Lindell book – “introduction to modern cryptography”.
As I read the book I found it very interesting but I'm finding some problems answering a few questions from the book,(for someone new like me I managed to to answer section 1 and almost section 2), but enough talk I'm getting straight to the questions:
First of all, I needed to prove witch of these two assumptions is perfectly secret :


The message space is $M = \{m \in \{0, 1\}^l \text{ | the last bit of }m \text{ is }0\}$.
Gen chooses a uniform key from $\{0, 1\}^{l−1}$. $Enc_k(m)$ returns ciphertext
$m \oplus (k || 0)$, and $Dec_k(c)$ returns $c \oplus (k || 0)$.

The message space is $M = \{0,..., 4\}$. Algorithm Gen chooses
a uniform key from the key space $\{0,..., 5\}$. $Enc_k(m)$ returns
$[(k + m) \bmod 5]$, and $Dec_k(c)$ returns $[(c − k) \bmod 5]$.



Suppose that we have $\pi(Gen,Enc,Dec)$.
For the first one I guess that I answered it but I need you guys to correct me since I'm not sur if my method is true or not :

$M = \{0, 1\}^l$
$n$ and $k = \{0, 1\}^{l-1}$
with $Enc_k(m)$ outputting $c = m_{[1,ℓ-1]} \oplus (k||0)$, i.e the xor of the first $(l-1)$ bits of $m$ with the key $k$.
The decryption outputs $Dec_k(c)$ as $c \oplus (k||0)$ concatenated with a random 1 bit string (0 on each of the cases $Enc$ &amp; $Dec$).
This scheme satisfies the $2^{−1}$ property that
$Pr[Dec(Enc(m)) = m] \geq 2^{-1}$ for every $m$, which means that in the first assumption the scheme is perfectly secure.

For the second case I have no idea how to put that proof on the line.
It would be good if you revisited the definition of perfect secrecy in the book. What you are proving for the first candidate scheme is a correctness property, not a security property (in general), and not perfect secrecy in particular.

Informally, what you are proving is that encrypting and then decrypting will preserve the original message. What you need to prove is that guessing $m$ knowing $c$ (where $c=Enc_k(m)$) the is as hard as guessing $m$ without seeing $c$.

As a general strategy, a good way to prove something secure is to base your proof on similar, already proven constructions. Scheme 1 is very similar to one-time pad, so the proof should be adaptable.

For proving something insecure, it's often simpler to describe a specific attack or even a counterexample. Scheme 2 for example is not perfectly secret. Since you are given small, concrete values, you can try and work out some example encryptions using pen &amp; paper to see if something's wrong.