The goal of this protocol is for Bob to get Alice to perform a Diffie-Hellman key exchange blindly, such that when the unblinded value is returned, Alice recognizes it as her own, but can’t distinguish it from others (i.e. similar to a blind signature).
Alice:
A = a*G
return A
Bob:
Y = hash_to_curve(secret_message)
r = random blinding factor
B'= Y + r*G
return B'
Alice:
C' = a*B'
(= a*Y + a*r*G)
return C'
Bob:
C = C' - r*A
(= C' - a*r*G)
(= a*Y)
return C, secret_message
Alice:
Y = hash_to_curve(secret_message)
C == a*Y
If true, C must have originated from Alice
I unearthed this protocol from a seemingly long forgotten cypherpunk mailing list post by David Wagner from 1996 (edit: perhaps not as forgotten as I thought, as Lucre is an implementation of it). It was devised as an alternative to RSA blinding in order to get around the now-expired patent by David Chaum. As in all ecash protocols, the secret_message
is remembered by Alice
in order to prevent double spends.
One benefit of this scheme is that it's relatively straightforward to perform in a threshold setting (only requires curve multiplication). One downside is that validation is more involved than simply checking a signature, as this step requries repeating the Diffie-Hellman Key Exchange.
The protocol also has one additional weakness that can be addressed. Bob can't be certain that C'
was correctly generated and thus corresponds to a*B'
. Alice can resolve this by also supplying a discrete log equality proof (DLEQ), showing that a
in A = a*G
is equal to a
in C' = a*B'
. This equality can be proven with a relatively simple Schnorr signature, as described below.
(These steps occur once Alice returns C')
Alice:
r = random nonce
R1 = r*G
R2 = r*B'
e = hash(R1,R2,A,C')
s = r + e*a
return e, s
Bob:
R1 = s*G - e*A
R2 = s*B'- e*C'
e == hash(R1,R2,A,C')
If true, a in A = a*G must be equal to a in C' = a*B'
Thanks to Eric Sirion, Andrew Poelstra, and Adam Gibson for their helpful comments.
Taxonomy: User Bob, Mint Alice (really screws my mind)
Since we've been talking about this in the background, I'll add my thoughts to this:
To find such an
'r
you need to solveY + rG = B_ - Y’ = r’G
forr'
. This is equivalent of finding the private key of a public key.On top of that, you still need to invert
hash_to_curve
because now you only know your desiredY'
but you need its appropriatex'
value in order to fulfill the mint's verification requirement. Both are practically impossible tasks.On a vaguely related note, we were discussing blinding attacks on ordinary signature schemes and realized that if this scheme didn't use
hash_to_curve(x) (= Y)
but only its outcomeY
, it would be trivial to generate an infinite number of valid pubkey, signature pairs(Y', C')
from only a single one by providing the blinded message and blinded signatures:C' = a*B'
.(Y, C)
(B', C')
as a coin (in fact every multiplicative of the legitimate coin).So it seems to me that this blind signature scheme is protected against blinding attacks by using
hash_to_curve
. I just learned something!General question: is this a normal way of protecting signature schemes against blinding attacks?