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

## Sunday, January 15, 2017

### 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.

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

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

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

## Saturday, January 14, 2017

### 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?

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.

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

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

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

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

Subscribe to:
Posts (Atom)