An example that is not Semantic Security

We suppose that there is an algorithm A that can always deduce LSB of plaintext from ciphertext. We describe the statement as below formula,

LSB (m) = A (c) 
where 
m is a plaintext
c is a ciphertext
A is the algorithm.

It is an example of the Stanford on-line course, Cryptography I, that describes the stream cipher is not semantically secure.

I explain it in my way as the below picture.

An adversary input m0 and m1 to attach the challenger. There are two worlds of the challenger, World 0 and World 1.

In World 0, the challenger picks m0 and returns c = E (k, m0).
In World 1, the challenger picks m1 and returns c = E (k, m1).

The adversary accepts the c and determines if the c comes from m0 or m1. The adversary defines an algorithm B,

If LSB (mb) == 1, then output "1"

For World 0, the probability of the algorithm that outputs "1" is 0.
Pr [EXP(0) = "1"] = 0

For World 1, the probability of the algorithm that outputs "1" is 1.
Pr [EXP(1) = "1"] = 1

ADV [B, E] = |0 - 1| = 1

It means that the adversary can fully distinguish the c comes from m0 or m1.

The adversary can also use another algorithm B2 to distinguish the c.

If LSB (mb) == 0, then output "0"

Pr [EXP (0) = "1"] = 1
Pr [EXP (1) = "0"] = 0
ADV [B2, E] = |1 - 0| = 1

-Count

The 1-bit PRP is not a secure PRF

The Stanford on-line course, Cryptography I, describes that the following 1-bit PRP is secure,

X = {0, 1}
E: E x X ---> Y
E (k, x) = x xor k
E is a secure PRP

but it is not a secure PRF. How do we explain it? We can imagine that there are two worlds as the below picture, World 0 and Word 1. World 0 is for 1-bit PRP and World 1 is for truly random function.

There are two permutations in World 0. and four functions in World 1. An attacker wants to find an algorithm to distinguish both worlds.

The attacker uses the algorithm A1,
if f(0) == f(1), then output "1"

The attacker inputs x = 0 and x = 1 to distinguish both worlds.

For World 0, the probability of the algorithm that outputs "1" is 0.
Pr [EXP(0) = 1] = 0

For World 1, the probability of the algorithm that outputs "1" is 1/2.
Pr [EXP(1) = 1] = 1/2

Adv [A1, E] = |0 - 1/2| = 1/2

The attacker uses the algorithm A2,
if f(0) != f(1), then output "1"

The attacker inputs x = 0 and x = 1 to distinguish both worlds. We just use the below formulas.

Pr [EXP(0) = 1] = 1
Pr [EXP(1) = 1] = 1/2
Adv [A2, E] = |1 - 1/2| = 1/2

In conclusion, no matter the attacker uses A1 or A2, the Adv is always 1/2. It means that the attacker can easily distinguish both worlds, 1-bit PRP and truly random function. Therefore the 1-bit PRP is not a secure PRF.

-Count

Why is 1-bit PRP with XOR secure?

The Stanford on-line course, Cryptography I, describes that the following 1-bit PRP is secure.

X = {0, 1}
E: K x X ---> Y
E(k, x) = x xor k
E is a secure PRP

How do we understand it?

Permutation.

A function f: X ---> Y is a permutation means that it is an one-to-one and onto function, and the domain X is equal to the codomain Y.

Pseudo Random Permutation (PRP)

The function E(k, .) is a PRP means that E(k, .) is a permutation and k is a random variable that defines the permutation.

Secure PRP.

The function E(k, .) is a Secure PRP means that it is indistinguishable from a random function in the set of all permutations.

The above 1-bit PRP is secure.

We can imagine that there are two worlds as the below picture, World 0 and Word 1. World 0 is for 1-bit PRP and World 1 is for truly random permutation for the 1-bit.

There are two permutations in World 0 and they are same in World 1. We can say that World 0 is equals World 1. An adversary cannot distinguish both worlds.  Therefore the 1-bit PRP is secure.

-Count