Laurie's blinding w/cut and choose?

[Nomen Nescio]

Jason Holt writes:
> 	In his paper on Lucre ("2nd defence" against marking):
> http://anoncvs.aldigital.co.uk/lucre/
>
> 	Ben Laurie gives this as a (possibly patent-free) blinding technique,
> where h is the message, and g is the public generator:
>
> r = blind(h) = h^y * g^b (mod p)
>
> 	To "sign",
>
> s = sign(r) = m^h
>
> 	To unblind,
>
> (s/g^k^b)^(1/y) (mod p)
>
> 	(where k is the signer's secret exponent. Of course, nobody but the
> signer can verify the signature).  Unfortunately, this doesn't work with cut
> and choose where the signer signs the product of unrevealed documents, since 
> the 1/y exponent above would distribute to all the internal terms:

Boy, you've got a lot of faith asking this question on cypherpunks.
It's not exactly the intellectual center of the crypto freedom movement
these days, you know.  The average IQ is rapidly descending into double
digits, even not counting Choate.  But let's see what we can do for you.

First, let's fix your notation.

r = blind(h) = h^y * g^b  OK
s = sign(r) = r^k, not m^h.
unblind(s) = (s/g^k^b)^(1/y) = h^k = sign(h).

That's what you want to end up with, h^k, as the pseudo-signature on h.

Now for a credential system, you apparently want to create a bunch
of values which have some structure, and get a signature on a product
of them.  Using cut and choose, the client will prepare blinded forms
of all of the values, then the server will ask for half of the blinding
factors to be revealed.  This exposes the raw values to be signed and
the server can make sure they are in the right form.  If so, it then
signs the product of the remaining values, which the client unblinds to
get back a good signature on the product of the unblinded values.

The fundamental problem with this is that the blinding factors have to
be different for each of the values.  If they are all the same, then
when they are revealed for some of the values during cut and choose,
that will reveal them for all of them, and so none of them will be
effectively blinded any more.

But if the blinding factors are all different, we can't unblind since
we don't have a unique power 1/y to raise to.

That's your problem, right?

Here are a couple of possible solutions.  First, you could do a cut and
choose in which all but one of the blinded values are revealed, and only
the remaining (unrevealed) one is signed.  This has the problem that it
has only a 1/n security factor with n values.  That is, the client can
just guess which one the server won't ask to check, and if it sent say 100
values, it has a 1/100 chance of getting lucky, which might seem too high.

However since credential issuing usually occurs in a non-anonymous
context, you can afford to penalize people very heavily if they are
caught in this manner.  (Cutting the connection and refusing to resume
with the previous values has to count as cheating.)

Another approach is as follows.  Go back to the 50-50 cut and choose
with signature on the product.  However, use the same y blinding factor
for all of the values.  Now when the client has to reveal during cut and
choose, it keeps the y value secret but reveals all of the h and b values.
It then proves in zero knowledge that there exists a y such that the h^y
equals the required value.  This is a standard ZK proof of knowledge
of a discrete logarithm.  It is similar to the example Ben's paper gives
of how the bank can prove it is raising to the right power.

Since you don't have to reveal y, you can use the same y for all of them
and successfully perform the unblind operation, getting back the signature
on the product of the h's as required.

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).

So there you go.  A little technical for cypherpunks, but unfortunately
coderpunks, like the little old lady, has fallen and it can't get up.