Re: Blum-Micali construction reverse order

On 26 Feb., 21:42, longf...@xxxxxxxxx wrote:
Hi Kristian,

On 26 Feb., 21:09, Kristian Gjøsteen <kristiag+n...@xxxxxxxxxxxx>
wrote:> <longf...@xxxxxxxxx> wrote:
I am trying to figure out why one has to output the bits in the
reverse order in the Blum-Micali pseudorandom generator construction.

Are you sure you haven't misunderstood? I think some security proofs
first reverse the output sequence before proving that it is pseudorandom.

Yes, it's true that because of the fact that
unpredictability=indistinguishability the output order doesn't matter.
However, the proof of security in the original paper explicitly says
that the bits have to be output from right to left (!!!). In fact, I
also found a lecture note which states the same:http://www.cs.bu.edu/fac/reyzin/teaching/cryptonotes/notes-2.pdf
(Section 2.4 & Discussion section).
What I forgot...Does somebody know the reason for this?

.

Relevant Pages

  • Re: Blum-Micali construction reverse order
    ... reverse order in the Blum-Micali pseudorandom generator construction. ... I think some security proofs ... first reverse the output sequence before proving that it is pseudorandom. ...
    (sci.crypt)
  • Re: Blum-Micali construction reverse order
    ... reverse order in the Blum-Micali pseudorandom generator construction. ... first reverse the output sequence before proving that it is pseudorandom. ...
    (sci.crypt)
  • Blum-Micali construction reverse order
    ... reverse order in the Blum-Micali pseudorandom generator construction. ... Let f be a one way function and h a hardcore predicate. ...
    (sci.crypt)