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

## No comments:

## Post a Comment