Jason Holt writes:
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.
There was extensive discussion on coderpunks about possible patent implications of Wagner blinding. Using the g^b blinding makes things potentially a little worse, because it requires the server to publish g and g^k. This can be considered a public key, and brings the situation closer to the blind signature patent. Wagner blinding can be thought of as a blinded undeniable signature. It is like a blind signature in that the server doesn't see what it is "signing". And it is like an undeniable signature in that the validity can only be checked with the aid of the server. It seems likely that Wagner could have patented his blinding along these lines if he had wanted to. So the problem is, if this is a blind + undeniable signature, doesn't that suggest that it infringes on both the blind and the undeniable signature patents? To answer this you have to look at the claims in detail. You can differentiate from the undeniable signature patent in that there is no repudiation protocol in the ecash system - no way for the server to prove that a purportedly signed value is actually bad. (Of course this lack is a weakness in an ecash system, since the bank might like to be able to prove that bogus cash is just that; but if it were remedied then Wagner blinding would almost certainly infringe the undeniable signature patent.) Differentiation from the blind signature patent is done simply by asserting that this is not a signature. That's why we are always careful to put "sign" into quotes when referring to server operations. It's not a signature because there is no way to independently verify it, which one can argue is a de facto requirement for something to be considered a signature. But of course, by this definition the undeniable signature is not a signature either. Yet we call it a kind of signature. If the undeniable signature is a signature, then so is the Wagner blinding, and so it is covered by the blind signature patent. As you can see, the situation is murky. One salvation is that the blind signature patent will expire in about 3 years, and it is unlikely that you will be successful enough in any project that it would be worthwhile to sue you within that time frame. Besides, everyone who takes control of the blind sig patent soon goes broke, so they probably can't afford a lawyer to sue you anyway. You should be aware too that there are a number of credential patents, which you can find by searching on the word credential.
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.
Seems safe by the DDH assumption, which is that it is hard to recognize that (g, g^a, g^b, g^ab) have the DH relationship. If we let m = g^b then this is (g, g^a, m, m^a). In other words, we can't tell whether two different values g and m are both being raised to the same power. In your case, you know h1, h2, (h1h2)^k. If you could then find h1^k, you could construct a DDH tuple (h1, h1^k, h1h2, (h1h2)^k), so you could violate the DDH assumption. This is a little hand-wavy and only deals with the two element case, but an argument along these lines will probably work.
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?
You're really going to remember all the discarded h values from all the previous instances of credential issuing? Seems like it might be a lot of data. How many h values do you typically expect? Maybe you could say more about the details of your credential system. Such a system built on Wagner blinding might be very interesting.