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.
DLEQs can serve an additional purpose, Alice can still be sure the bank hasn't constructed the coins in a way that is distinguishable, DLEQs constrain it so that there are no degrees of freedom in the minting of coins, which provides an assurance of unlinkability in a later redemption even if Alice must trust the bank to honor that redemption
See also Privacy Pass:
The main differences are, sticking to your variable naming:
If redemption hijacking is desirable, then I suppose$R$ should probably be an ephemeral public key provided by the shop in the original setting, and it would sign the request for new coins with that key? Should it commit anything more for some reason I can't think of? If the latter, then selective disclosure is probably desirable too... See also these proposed modifications
They reduce this to one-more-decryption on El Gamal,
Unlinkability is proven by uniformity of blinding, and showing independence of the issuance and redemption phases through this, and the DLEQ requirement is discussed in section 5.5 Key Consistency.