Blind-DH-ecash.md

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.

Could we extend the DLEQ proof in such a way that if the mint uses a1 and a2 private keys (making a random decision at signing) for a given amount in a given keyset? The user should be able to verify that either one of the keys was used, but not specifically which one was used to produce C' from B'.

Very naive attempt:

Alice picked a1 randomly to sign with:
C' = B'*a1
D' = B'*a2

Alice creates DLEQ:
 r = random nonce
R1 = r*G
R2 = r*B'
 e = hash(R1,R2,A1,A2,C',D')
 s = r + e*(a1 + a2)
return e, s, D'

Bob:
R1 = s*G - e*A1 - e*A2
R2 = s*B' - e*C' - e*D'
e == hash(R1,R2,A1,A2,C',D')

If true, a1 or a2 must have been used to create C'?

Bob has no idea if he has to subtract r'A1 or r'A2 (where r' is Bob's blinding factor), so he will calculate both. Token is now (x, C1, C2).
C2 is not a valid signature for either a1 or a2, but C1 is.

While both C1 = C' - r'A1 and D2 = D' - r'A2 would appear valid signatures to Alice they belong to the same Y = hash_to_curve(x), therefore spending both of them is impossible.

Is there a better way to do this? Can we somehow deal with a1' + a2' = a1 + a2 secret tagging?

How about?

Alice picked a1 randomly to sign with:
C' = B'*a1
D' = B'*a2

Alice creates DLEQ:
 r = random nonce
R1 = r*G
R2 = r*B'
 e = hash(R1,R2,A1,C',D')
 f = hash(R1,R2,A2,C',D')
 s = r + e*a1 + f*a2
return e, f, s

Bob:
R1 = s*G - e*A1 - f*A2
R2 = s*B' - e*C' - f*D'
e == hash(R1,R2,A1,C',D')
f == hash(R1,R2,A2,C',D')

If true, a1 or a2 must have been used to create C'?


Alternative (compressed) DLEQ:
 ...
 w = hash(R1,R2,C',D')
 e = hash(w,A1)
 f = hash(w,A2)
 s = r + e*a1 + f*a2
return w, s

Since A1 and A2 are known, e and f thus R1 and R2 can still be reconstructed.

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:

Choose x′ and r′ such that Y′+r′G=Y+rG⟹Y′=Y+(r−r′)G

To find such an 'r you need to solve Y + rG = B_ - Y’ = r’G for r'. 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 desired Y' but you need its appropriate x' 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 outcome Y, 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:

• Alice (mint) gives Bob: C' = a*B'.
• Bob unblinds and has legitimate coin (Y, C)
• Bob also can use (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?

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.

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.

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.