2
$\begingroup$

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 :

  1. 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)$.

  2. 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$ & $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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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 & paper to see if something's wrong.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for your answer, I have another question, can we use reduction to prove any of the 2 schemes, or there's a particular case in which we use reduction ? $\endgroup$
    – dev
    Sep 22, 2016 at 23:35
-2
$\begingroup$

I had some quite similar problems for homework recently, what helped me through was considering special cases. For the first one note that when $\mathcal{C}=\{0,1\}^l$ $$Pr[M=0^l|C=1^1]=0 \wedge Pr[M=0^l]=\dfrac{1}{2^l}$$ so the scheme is not perfectly secure. As for the second part, check what happens for $m=c=0$. Cheers!

Edit 1: Now $\mathcal{C}\neq\mathcal{M}$. My bad.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is incorrect. Check the encryption algorithm for the first case. The ciphertext $1^\ell$ can never occur. $\endgroup$
    – Maeher
    Mar 30, 2018 at 19:49
  • $\begingroup$ Edit, my bad. Though I know what you mean, since I had to ask for a specific $\mathcal{C}$, because I was told that it actually works if $\mathcal{M}=\mathcal{C}$. Thx $\endgroup$
    – Cristian Baeza
    Mar 31, 2018 at 1:36
  • 2
    $\begingroup$ No, your answer is incorrect. You cannot freely choose the ciphertext space. The ciphertext space is defined by the plaintext space and the encryption algorithm. The presented scheme is perfectly secure. $\endgroup$
    – Maeher
    Mar 31, 2018 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.