But actually another solution is much simpler, which is to do blinding as just h * g^b, without a y factor. That works fine as long as the bank is known not to be misbehaving. Ben's paper shows how the bank can use a ZK proof to show that it is raising to the same power k every time, basically again that same ZK proof regarding discrete logarithms. If the bank uses such a proof then you can use simpler blinding without a y factor, and you can recover the signature on the product of your h values by dividing by g^k^(sum of b's).
Somewhere I got the idea that that was patented, but looking at undeniable signatures, they're actually much closer to (h^y)(g^b), so your suggestion should work great. Thanks! Anybody know of other patents which might get in the way? I'm worried about Chaum's blind signature and undeniable signature patents, and want to present as patent-free a system as possible. One more thing. If the issuer returns the signature: (h1*g^b1 *h2*g^b2 *h3*g^b3...)^k Can I separate out any of the h^k values? My system relies on that being hard. If I replace h1 with (g^b0) and get the issuer to sign: ((g^b0)*g^b1 *h2*g^b2 *h3*g^b3...)^k I should be able to divide the two results and get h1^k. But part of the cut-and-choose protocol will be to require that the n/2 checked documents are all valid and different from any previous instances of the protocol. So it should be extremely hard for the user to sneak lots of previously used values and fake h's (which are really blinding factors) into the unrevealed documents. But are there other ways to separate out signatures on individual h's? -J