Introduction To Cryptography
Zahra Sadat Bahri
Student No. 98110232
Homework 1
October 8, 2021
Problem 1:
I): Letter mi of m is ci ⊕ k thus
Deck (C) = Deck (c1 ||c2 ) = c1 ⊕ k||c2 ⊕ k
Proof.
∀ bit k ∈ {0, 1} : k ⊕ k = 0
ci = mi ⊕ k → ci ⊕ k = mi ⊕ k ⊕ k = mi
⇒ Deck (Enck (m)) = m
II):
P r[SKE = 1] = P r{b = 1}P r{SKE = 1 | b = 1} + P r{b = 0}P r{SKE = 1|b = 0}
1 1
= P r{SKE = 1 | b = 1} + P r{SKE = 1|b = 0}
2 2
1 1
= P r{A outputs 1 | b = 1} + P r{A outputs 0 | b = 0} (*)
2 2
A1 :
P r{A outputs 1 | b = 1} = P r{A outputs 1} = 1
P r{A outputs 0 | b = 0} = P r{A outputs 0} = 0
1 1
⇒ (∗) = × 1 + 0 =
2 2
1
⇒ P r[SKE = 1] =
2
1
|P r[SKE = 1] − | = 0
2
A2 :
1
P r{A outputs 1 | b = 1} = P r{A outputs 1} =
2
1
1
P r{A outputs 0 | b = 0} = P r{A outputs 0} =
2
1 1 1 1 1
⇒ (∗) = × + × =
2 2 2 2 2
1
⇒ P r[SKE = 1] =
2
1
|P r[SKE = 1] − | = 0
2
A3 :
1
P r{A outputs 1 | b = 1} = P r{A outputs 1} = P r{c1 = c2 } =
2
1
P r{A outputs 0 | b = 0} = P r{A outputs 0} = P r{c1 =
̸ c2 } =
2
1 1 1 1 1
⇒ (∗) = × + × =
2 2 2 2 2
1
⇒ P r[SKE = 1] =
2
1
|P r[SKE = 1] − | = 0
2
A4 :
P r{A outputs 1 | b = 1} = P r{c1 = c2 ∧ m10 = m20 | b = 1} + P r{random 1 | b = 1}
P r{A outputs 0 | b = 0} = P r{random 0 | b = 0}
For calculating P r{c1 = c2 ∧ m10 = m20 | b = 1} note that when b = 1 then m1 is encrypted
1
and hence c1 = c2 ⇐⇒ m11 = m21 → P rc1 = c2 = and this is independent from m10 = m20
2
1
which probability is again . Thus
2
1 1 1
P r{c1 = c2 ∧ m10 = m20 | b = 1} = P rc1 = c2 P rm10 = m20 = × =
2 2 4
Also
1 1 3 3
P r{random 1 | b = 1} = × (1 − P r{c1 = c2 ∧ m10 = m20 | b = 1}) = × =
2 2 4 8
In the same way
1
P r{random 0 | b = 0} = × (1 − P r{c1 = c2 ∧ m10 = m20 | b = 0})
2
Note that when b = 0 then m0 is encrypted and hence
1
c1 = c2 ⇐⇒ m10 = m20 → P r{c1 = c2 ∧m10 = m20 | b = 0} = P r{m10 = m20 | b = 0} = P r{m10 = m20 } =
2
2
1 1 1
⇒ P r{random 0 | b = 0} = × (1 − ) =
2 2 4
As a result
3 1 5
P r{A outputs 1 | b = 1} = + =
8 4 8
1
P r{A outputs 0 | b = 0} =
4
1 5 1 1 7
⇒ (∗) = × + × =
2 8 2 4 16
7
⇒ P r[SKE = 1] =
16
1 1
|P r[SKE = 1] − | =
2 16
III): The A4 idiot didn’t think that when c1 = c2 ∧ m10 = m20 then it is more probable for
m0 to be encrypted and outputting 1 is extremely irrational. We correct her algorithm this
way:
1- output 0 if c1 = c2 ∧ m10 = m20 ∧ m11 ̸= m21
2- output 1 if c1 = c2 ∧ m11 = m21 ∧ m10 ̸= m20
3- generate random uniform output otherwise.
The important thing is that conditions 1 and 2 have no intersection and for that
later when we try to calculate probability of random b, it will not require complicated
calculation.
Let’s calculate the advantage.
P r{A outputs 1 | b = 1} = P r{c1 = c2 ∧m11 = m21 ∧m10 ̸= m20 | b = 1}+P r{random 1 | b = 1}
Here m1 is encrypted so
1 1 1
P r{c1 = c2 ∧ m11 = m21 ∧ m10 ̸= m20 | b = 1} = P r{m11 = m21 ∧ m10 ̸= m20 } = × =
2 2 4
1
⇒ P r{A outputs 1 | b = 1} = + P r{random 1 | b = 1}
4
P r{A outputs 0 | b = 0} = P r{c1 = c2 ∧m10 = m20 ∧m11 ̸= m21 | b = 0}+P r{random 0 | b = 0}
1 1 1
P r{c1 = c2 ∧ m10 = m20 ∧ m11 ̸= m21 | b = 0} = P r{m10 = m20 ∧ m11 ̸= m21 } = × =
2 2 4
1
⇒ P r{A outputs 0 | b = 0} = + P r{random 0 | b = 0}
4
Now For random 0 and 1 probability:
P r{random 0 | b = 0} =
1
×(1−P r{c1 = c2 ∧m10 = m20 ∧m11 ̸= m21 | b = 0}−P r{c1 = c2 ∧m11 = m21 ∧m10 ̸= m20 | b = 0})
2
3
In the latter term m0 is encrypted so it’s impossible for c1 = c2 and m10 ̸= m20 to happen at
the same time.
1 1 3
⇒ P r{random 0 | b = 0} = × (1 − − 0) =
2 4 8
In the same way:
P r{random 1 | b = 1} =
1
×(1−P r{c1 = c2 ∧m10 = m20 ∧m11 ̸= m21 | b = 1}−P r{c1 = c2 ∧m11 = m21 ∧m10 ̸= m20 | b = 1})
2
Again it’s impossible for c1 = c2 and m11 ̸= m21 to happen at the same time.
1 1 3
⇒ P r{random 1 | b = 1} = × (1 − 0 − ) =
2 4 8
1 1 3 1 1 3 5
⇒ (∗) = ×( + )+ ×( + )=
2 4 8 2 4 8 8
5
⇒ P r[SKE = 1] =
8
1 1 1
|P r[SKE = 1] − | = >
2 8 16
(you have no idea what a nightmare typing all those equations was!)
4
Problem 2:
I): It is not perfectly secret and that is because of 0 and 13 both being in K.
Proof. For the counter example assume m = 0, m′ = 2, c = 0
m=0→c=0=0+k mod 13 → k = 0or13
Since keys are chosen uniformly and there are 14 keys:
2
P r{Enck (m) = c} =
14
m′ = 2 → c = 0 = 2 + k mod 13 → k = 11
1
P r{Enck (m′ ) = c} =
14
′ ′
⇒ ∃m, m : P r{Enck (m ) = c} ̸= P r{Enck (m) = c}
II): It is perfectly secret.
Proof. Recall Shannon’s Theorem:
Theorem 2.11. (Shannon’s theorem) Let (Gen, Enc, Dec) be an encryption scheme with
message space M, for which |M| = |K| = |C|. The scheme is perfectly secret if and only if:
1. Every key k ∈ K is chosen with (equal) probability 1/|K| by algorithm Gen.
2. For every m ∈ M and every c ∈ C, there exists a unique key k ∈ K such that Enck (m)
outputs c.
It is obvious that |K| = 2l−1 and |M| = 2l−1 hence
|K| = |M|
Now every encrypted ciphertext ends also with 0 because
c = m ⊕ k||0 = (m1 ...ml−1 ||0) ⊕ (k||0) = (m1 ...ml−1 ⊕ k)||0
Therefore |C| = 2l−1
⇒ |M| = |K| = |C|
Now let’s prove that conditions 1 and 2 are satisfied.
1- Condition 1 is already assumed in the problem.
2- As for condition 2 assume that two keys can encrypt the same message m into the cipher-
text c
Enck1 (m) = c = Enck2 (m) → m ⊕ (k1 ||0) = m ⊕ (k2 ||0)
XOR both sides of the latter equation with m
m ⊕ m ⊕ (k1 ||0) = m ⊕ m ⊕ (k2 ||0) → 0 ⊕ (k1 ||0) = 0 ⊕ (k2 ||0) → (k1 ||0) = (k2 ||0) ⇒ k1 = k2
All conditions of Shannon’s Theorem are satisfied so the scheme is perfectly secret.
5
III): It is perfectly secret.
Proof. Considering the encryption matrix c = 5 and c = 6 never happen so
∀m ∈ (M ) : P r{Enck (m) = 5} = P r{Enck (m) = 6} = 0
For all other c = 1, 2, 3, 4 we prove that P r{Enck (a) = c} = P r{Enck (b) = c} (Note that
there are only two messages)
P r{Enck (a) = 1} = P r{K = k1 } = 1
c=1 6 ⇒ P r{Enck (a) = 1} = P r{Enck (b) = 1}
P r{Enck (b) = 1} = P r{K = k4 } =
1
6
P r{Enck (a) = 2} = P r{K = k2 } = 1
c=2 3 ⇒ P r{Enck (a) = 2} = P r{Enck (b) = 2}
P r{Enck (b) = 2} = P r{K = k3 } =
1
3
P r{Enck (a) = 3} = P r{K = k3 } = 1
c=3 3 ⇒ P r{Enck (a) = 3} = P r{Enck (b) = 3}
P r{Enck (b) = 3} = P r{K = k2 } =
1
3
P r{Enck (a) = 4} = P r{K = k4 } = 1
c=4 6 ⇒ P r{Enck (a) = 4} = P r{Enck (b) = 4}
P r{Enck (b) = 4} = P r{K = k1 } =
1
6
∀c ∈ C : P r{Enck (a) = c} = P r{Enck (b) = c}
6
Problem 3:
Proof. I use notation P r{m1 , m2 } for P r{M1 = m1 ∧ M2 = m2 } and notation P r{c1 , c2 } for
P r{C1 = c1 ∧ C2 = c2 } So the the equation in the problem will look like
P r{m1 , m2 | c1 , c2 } = P r{m1 , m2 }
From the Bayes law:
P r{c1 , c2 | m1 , m2 } × P r{m1 , m2 }
P r{m1 , m2 | c1 , c2 } =
P r{c1 , c2 }
We should prove that for any scheme there exists a distribution and a pair of distinct messages
P r{c1 , c2 | m1 , m2 }
and a pair of any two cipher texts for which the fraction ̸= 1 and thus
P r{c1 , c2 }
P r{m1 , m2 | c1 , c2 } ̸= P r{m1 , m2 } for that pair.
of course it can seem a little obvious that P r{c1 , c2 | m1 , m2 } is not equal to P r{c1 , c2 }
because ciphertexts surely depend on plaintexts. However it requires a counterexample to
be precisely proved.
assume uniform distribution over M. Since c1 , c2 can be anything, they can be equal. But
m1 ≠ m2 . Here P r{c1 , c2 } > 0 because simply c1 , c2 exist in C and can be chosen together
(regardless of messages). So de-numerator is not 0 and that won’t be a problem. It is
impossible that decrypting two same ciphertexts result in two different plaintext because
that won’t be a function any more and when Enck (m1 ) = c = Enck (m2 ) then Deck (c) can
be both m1 and m2 and how could the algorithm know which one to chose? As a result:
P r{c, c | m1 , m2 } = 0
P r{c, c | m1 , m2 }
So = 0 ̸= 1 → P r{m1 , m2 | c1 , c2 } = 0 ̸= P r{m1 , m2 }
P r{c1 , c2 }
⇒ ∃c1 , c2 ∈ C ∧ m1 , m2 ∈ M : P r{m1 , m2 | c1 , c2 } ̸= P r{m1 , m2 }
