0
$\begingroup$

I am having a hard time grasping the perfect secrecy concept. (I have already tried solving a couple of similar problems, so please don't think I am trying to get you guys to do my work, I really am stumped on this).

Consider a shift cipher with plaintext, key and cipher-text space is $[0..7]$ i.e.

$$ P = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}\\ K = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}\\ C = \{0, 1, 2, 3, 4, 5, 6, 7, 8\} $$

plain-text's even alphabets have twice the probability of odd alphabet i.e.

$$ \forall p \in P: \Pr_P(p) = \begin{cases} \frac{2}{12} & \textrm{ if p = 2(b) for some b $\in$ Z } \\ \frac{1}{12} & \textrm{ if p = 2(b) + 1 for some b $\in$ Z } \end{cases}\\ \\ \forall k \in K: \Pr_K(k) = \frac{1}{8} $$

From here I have calculated that $\Pr_C(c) = \frac{1}{8}$.

  1. How do I calculate $\Pr(y|x)$
  2. How do I use Baye's theorem to calculate $\Pr(x|y)$
  3. How do I show whether $\Pr(x|y) = \Pr(x)$ or $\Pr(x|y) \neq \Pr(x)$ (thereby determining whether this cipher has perfect secrecy or not).
$\endgroup$
  • 1
    $\begingroup$ $P(y|x) = P(x \cap y)/P(x)$. $\endgroup$ – fkraiem Oct 20 '16 at 5:22
  • $\begingroup$ actually you are specifying the general formula for probability, in crypto it's $P(y|x) = \sum_{(k: x = d_{k}(y))}\Pr_{K}(k)$, and it comes out as $\frac{1}{8}$. the formula for Baye's Theorem is $\Pr(x|y) = \frac{\Pr_P(x).\Pr(y|x)}{\Pr_C(y)}$, this is where it gets tricky, since $\Pr_P(x)$ has two different probabilities (for even and odd alphabets). $\endgroup$ – ishaq Oct 20 '16 at 6:14
  • $\begingroup$ and someone downvoted me, I have no idea why someone might think the question is bad. $\endgroup$ – ishaq Oct 20 '16 at 6:16
  • $\begingroup$ I am not sure, but my guess would be: Because it isn't a question about crypto. Your questions are basic probability theory. Also there is no difference to the probabilities in crypto. In the case of assuming independent $k$ and $x$(or independent $k$ and $c$) allows the multiplication of probabilities instead of summing up. That's pretty much the basic rule for conditional probabilities. $\endgroup$ – tylo Oct 20 '16 at 9:50
  • $\begingroup$ you do have a point (re: question being more about probability than crypto), i stand corrected. $\endgroup$ – ishaq Oct 20 '16 at 12:57
1
$\begingroup$

In the definition of perfect secrecy, no assumption about the distribution of plaintext is made - and it is not necessary.

Informally: If you are given any $p$ and a uniformly distributed $k$, then $p+k$ (with the according modulus) is also distributed uniformly , regardless of what $p$ actually was.

Your questions are a little surprising, because you seem to know about Bayes theorem. But on the other hand, it seems you are not familiar with the basic rules of conditional probability. For example, that for independent events $A$ and $B$ (in this case: $P(A \cap B) = P(A) \cdot P(B)$), the following holds:

$P(A|B) = \frac{P(A \cap B )}{P(B)} = \frac{P(A) \cdot P(B)}{P(B)} = P(A)$

Then, Bayes theorem is simply the combination of the very definitions of conditional probabilities, for both $P(A|B)$ and $P(B|A)$, regardless if they are independent or not:

$P(A|B) \cdot P(B) = P(A \cap B) = P(B|A) \cdot P(A)$

All your questions can be answered, if you just apply the rules and definitions for conditional probabilities.

$\endgroup$
  • $\begingroup$ you are right, may be I have been over-thinking the problem, I need to take a step back and think about it in terms of probability. $\endgroup$ – ishaq Oct 20 '16 at 12:58
2
$\begingroup$

For any ciphertext $c \in C$ and message $p \in P$ we have $$P(c|p) = \frac{P(p\cap c)}{P(p)} = \frac{P(p\cap k)}{P(p)},$$ where $k = c-p$. This is because if the plaintext is $p$, the ciphertext is $c$ if and only if the key is $k$. Now, if the key is chosen independently of the plaintext we have $P(p\cap k) = P(p)\cdot P(k)$, and so finally $P(c|p) = P(k) = 1/8$ if the key is chosen uniformly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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