Revisitting Blum-Macali "digital signatures"

[Wei Dai]

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