182k views
5 votes
Let F be a pseudorandom permutation. Consider the mode of operation in which a uniform value ctr ∈ {0, 1} n is chosen, and the ith ciphertext block ci is computed as ci := Fk(ctr + i + mi). Show that this scheme does not have indistinguishable encryptions in the presence of an eavesdropper

1 Answer

5 votes

Answer:

The answer is No, it's not IND-CPA secured. because Fk is a permutation, therefore Adv ind-cda Enc (.A)=1 which is certainly non-negligible.

Step-by-step explanation:

In cryptography, a pseudorandom permutation (PRP) is referred to a function that cannot be distinguished from a random permutation (which is implied as a permutation selected at random with uniform probability, from the family of all permutations on the function's domain) with practical effort. An unpredictable permutation (UP) Fk is a permutation whose values cannot be predicted by a fast randomized algorithm. Unpredictable permutations can sometimes be used as a cryptographic primitive, a building block for cryptographic systems with more complex properties.

The idea is we can select a two-point message that allows Fk to be involved two times on the same input which can be detected. Formally, we can have a description of the attacker, A, given the challenge oracle O. The A chooses the arbitrary two messages blocks mo, m1 €{0,1}^n, such that, mo + 1= m1 + 2, it queries the oracle on the pair 2n-bit messages (mo||m1, mo||mo), and receive a ciphertext y=y1||y2. It accepts if y1=y2 and rejects otherwise.

We can now analyze the attack

If O= Eok(.,.) then by the way mo and m1 are selected.

Ctr + (1) + mo= Ctr + (2) + m2

Therefore,

Pr[y1=y2] =1, whereas, If O= E[k,1], then ctr + (1) +mo is not equal to ctr +2+mo.

Pr[y1=y2] = Pr[Fr(ctr + (1) + mo) = Pr[Fr(ctr + (2) + mo) = 0

So, because Fk is a permutation, therefore Adv ind-cda Enc (.A)=1 which is certainly non-negligible.

User Arabela Paslaru
by
3.7k points