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