Revisitting Blum-Macali "digital signatures"

There was some discussion on Usenet a while back about doing "digital
signatures" with the Blum-Macali public key method.

Briefly, Blum-Macali relies on the BBS generator to generate a "one-time pad".
And the pad can be reversed by taking repeated square roots on the random
number seed (assuming you know the factorization) to get back to the starting
seed.

So, the author suggested that one calculate a digest of the message, call it
D.

Then the author suggested that one calculate D^(1/2), as per the Blum-Micali
method.

Then he goes on to do the signature check by checking whether or not

D^2 == X^4

where X is the "signature".

I understand that there is some sign ambiguity involved in calculating square
roots mod B where B is a Blum integer (that causes 4 possible roots). And
that's the source of ambiguity problems in Rabin digital signatures, but if
the Blum-Micali public key method works, then this sign ambiguity shouldn't
exist (because they define a SPECIFIC root to use), and the method can be
simplified to simply calculating D^(1/2) and the check is simply D==X^2.

What am I missing here?

On Mon, 29 Jan 1996, Paul E. Campbell wrote:

> There was some discussion on Usenet a while back about doing "digital
> signatures" with the Blum-Macali public key method.
> 
> Briefly, Blum-Macali relies on the BBS generator to generate a "one-time pad".
> And the pad can be reversed by taking repeated square roots on the random
> number seed (assuming you know the factorization) to get back to the starting
> seed.
> 
> So, the author suggested that one calculate a digest of the message, call it
> D.
> 
> Then the author suggested that one calculate D^(1/2), as per the Blum-Micali
> method.
> 
> Then he goes on to do the signature check by checking whether or not
> 
> D^2 == X^4
> 
> where X is the "signature".
> 
> I understand that there is some sign ambiguity involved in calculating square
> roots mod B where B is a Blum integer (that causes 4 possible roots). And
> that's the source of ambiguity problems in Rabin digital signatures, but if
> the Blum-Micali public key method works, then this sign ambiguity shouldn't
> exist (because they define a SPECIFIC root to use), and the method can be
> simplified to simply calculating D^(1/2) and the check is simply D==X^2.
> 
> What am I missing here?

Let me see if I understand you correctly.  The scheme you describe says 
to calculate X=(D^2)^(1/4) as the signature and check D^2==X^4 for 
verification.  You are wondering why you can't just calculate Y=D^(1/2) 
as the signature and check D==Y^2 for verification.

The problem here is that some D's don't have square roots.  For a Blum 
integer n, only 1/4 of the numbers between 1 and n-1 have square roots 
mod n (they are called quadratic residues mod n).  For a D that is a 
quadratic residue, the X and Y above are equal.  But for a D that is not a 
quadratic residue, Y can't be calculated.  X can still be calculated in 
this case, but X^2 != D.

Wei Dai