Re: Blum-Micali construction reverse order

<longfu84@xxxxxxxxx> wrote:
What do you think about this argumentation?

The argument seems correct enough. The only point is that even though
you for practical purposes reverse the string in the proof, there is no
point in doing it in practice.

Obviously, you can also do the proof without reversing anything.

Define x_1,x_2,...,x_n,x_{n+1} by x_1 being sampled uniformly at random
and x_{i+1} = f(x_i). Let y_i = B(x_i) be the output bits, let z_i
be uniformly distributed random bits. The problem is, given x_{n+1},
distinguish y_1,y_2,...,y_n from z_1,z_2,...,z_n.

By a standard hybrid argument, the attacker must be able to
distinguish A_i = z_1,z_2,...,z_{i-1},y_i,...,y_n from A_{i+1} =
z_1,z_2,...,z_i,y_{i+1},...,y_n.

Given any w = f(v) and bit b that is either B(v) or uniformly distributed,
we can construct the sequence

z_1,z_2,...,z_{i-1},b,y_{i+1},...,y_n

by setting x_{i+1} = w and proceeding. If b is B(v), we have something
that is distributed exactly as A_i, otherwise we have something that is
distributed exactly as A_{i+1}.

QED.

--
Kristian Gjøsteen
.