Sunday, January 15, 2017

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

18 comments: