Skip to content

Instantly share code, notes, and snippets.

@RubenSomsen
Last active June 27, 2024 17:34
Show Gist options
  • Save RubenSomsen/be7a4760dd4596d06963d67baf140406 to your computer and use it in GitHub Desktop.
Save RubenSomsen/be7a4760dd4596d06963d67baf140406 to your computer and use it in GitHub Desktop.

Blind Diffie-Hellman Key Exchange (blind ecash)

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.

@moonsettler
Copy link

moonsettler commented Jul 11, 2023

Taxonomy: User Bob, Mint Alice (really screws my mind)

Same :( I hate it.

So it seems to me that this blind signature scheme is protected against blinding attacks by using hash_to_curve.

Yes.

@Semisol
Copy link

Semisol commented Jul 11, 2023

As long as you can ensure the point P that is used for verification is not influencable to be s * S where s is any scalar and S is a point the client already has a signature for, I don't think anyone can fabricate additional signatures.
Trying to find an s value for a known P (you cannot control P except brute forcing, due to a cryptographically secure hash function being used) and S would be impossible, since that would mean breaking EC security.

@moonsettler
Copy link

moonsettler commented Jul 11, 2023

An other way to put it is if there was no hash_to_curve but you used a Y = x*G way of "lifting" x to the curve from a "signature" (x, C) anyone could produce arbitrary number of (x", C") where x" = x*k and C" = C*k. one "signature" would generate any number of tokens.
But finding the preimage for Y" = Y*k is not really feasible.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment