More of Ben's blinding

[Anonymous]

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.