Re: Blum-Micali construction reverse order

Hi,

I don't have the original paper, but the above link seems confused.
There's absolutely no reason why one should reverse the output, in fact,
any such reversal would be a nightmare from an implementation point
of view.
That it would be a nightmare and that it doesn't matter from an
implementation point of view is clear for me. However, I'd like to
understand why it is nevertheless necessary in the proof. I thought
about the following argumentation:

The proof of the BM-construction is given by a reduction argument,
that is, given $f(x)=\widetilde{x}$ we have to `design' an efficient
algorithm $A'$ that predicts $B(x)$. We can use therefore algorithm $A
$ that breaks the PRG. However, note that $A$ has to succeed in
predicting some bit: first, second, ... , i-th, ... , n-th. Our
algorithm $A'$ works as follows:
\begin{enumerate}
\item Pick $i \in [1,n]$ at random.
\item Set $x_{n-i+2} = \widetilde{x}$ and compute $x_{n-i+3} =
f(x_{n-i+2}), \ldots , x_n= f(x_{n-1})$.
\item When $A$ asks for the first bit, give it $B(x_n)$, for the
second bit, give it $B(x_{n-1})$ and so on.
\end{enumerate}
The output of this is equal to the output starting with
$log_g(log_g(\ldots (x)\ldots ))$ ($n-i$ logs here). When $A$ predicts
the $i$-th bit we output this as our output for the hardcore predicate
$B(x)$. So far it's the argumentation form the lecture note. Now what
would happen in this proof if we output the bits in order $B(x_1),
B(x_2), \ldots , B(x_n)$: if $A$ asks for the first bit we cannot
answer with the correct bit. To clarify this consider we have chosen
the $i=n$. In this case we set $x_2 = \widetilde{x}$. However, we
cannot compute the correct $x_1 = log_g(\widetilde{x})$ because
therefore we have to invert the one-way function. Thus, we cannot
answer the question of $A$ in a consistent way or we have to choose it
just randomly.

However, in my opinion one cannot assume that an adversary cannot
distinguish randomly chosen bits from bits that are consistent with
the others.

What do you think about this argumentation?

-L

.

Relevant Pages

  • Re: Please suggest a simple 8-bit cipher
    ... since it can almost certainly be reverse ... algorithm in its entirety remains hidden. ... You could use eg. Skipjack in Counter ... > Mode to get an effective stream cipher. ...
    (sci.crypt)
  • Re: Complexity/permutation based hash
    ... Run something similar to Algorithm P on the data you are digesting. ... Reverse the algorithm to obtain a pre-image of the previous step. ... representing a permutation of e.g. ...
    (sci.crypt)
  • Fwd: Solution for RubyQuiz 131
    ... So the idea is, to create an algorithm, that uses the max_subarray method within. ... In that case, the max_subarray method is not going into action (its just comparing the rows, consisting of one number) and we are comparing all possible combinations. ... I reverse the matrix when there are more rows than columns. ... I did more tell the programm which indices had to be permuted. ...
    (comp.lang.ruby)
  • Re: Source & Cipher - How Secure is this?
    ... >>that Mike Curry uses a reversible version, ... the attacker can reverse ... > spam then anything and get ditched before realizing what was removed by any ... >>The algorithm is also terribly inefficient. ...
    (sci.crypt)
  • cant play file or C00D1199: Cannot play the file
    ... window media player 10 is becoming a nightmare, it won't allow me to reverse ... to 9 and 10 is disabling my audio system please help... ...
    (microsoft.public.windowsmedia.player)