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.

@moonsettler thanks for spotting it, fixed now!

In my notes you'd have to make 2^24 queries to bring security down to 116 bit (on secp256k1) so I think it's fine for this.

I'd be interested to note how you got to those numbers.

necro reply. Can't remember how I got it but here's the table I made:

so set u = 2^6 * 3 * 149 * 631 and you get log2 of n as 116.

I'd like to introduce a doubt which make me reflect on a cunning exploitation of the malleability in the protocols, a subtle deception that could be seen as a type of 'blinding' attack.

Our protagonist, Bob, craftily manipulates his own blinding factor in a Diffie-Hellmann key exchange. He creates a seemingly valid but illegitimate token pair, which can then pass through the protocol undetected. This undermines the protocol's intent, potentially leading to inflation of token supply.

Scenario: Bob (Attacker)

Choose $x'$ and $r'$ such that $Y' + r'G = Y + rG \implies Y' = Y + (r - r')G$

This equation means that for a specific difference $(r - r')$, Bob can compute an $x'$ which will result in a $hashToCurve(x') = Y'$ that is equal to $Y + (r - r')G$.

Given:
$$B' = Y' + r'G$$

Substitute $Y'$:
$$B' = Y + (r - r')G + r'G $$

$$B' = Y + rG = B$$

Bob manages to create a $B'$ that is actually equal to the legitimate $B$, but derived from a different secret $x'$. He sends $B'$ to Alice.

Alice:
$$C' = aB' $$

$$C' = a(Y + rG) $$ $$C' = aB $$

Alice sends $C'$ back to Bob.

Bob:
$$C = C' - r'A $$
$$C = aY' $$
$$C = a \cdot hashToCurve(x') $$

Bob returns $C$ and $x'$ as the token pair.

Alice:
$$Y' = hashToCurve(x') $$
$$C = aY' $$

If true, $C$ must be a valid Alice signature. But in this case, $C$ was created by Bob manipulating the protocol to create a $C$ that appears legitimate but corresponds to an illegitimate $x'$. This attack is successful because of the commutative property of addition in the elliptic curve group, allowing Bob to choose an $r'$ that makes his illegitimate $B'$ indistinguishable from a legitimate $B$.

This scenario emphasizes the importance of ensuring Bob can't manipulate his random blinding factor $r$ in a way that lets him forge a seemingly valid $B'$ and the corresponding token pair $(x', C)$.

Indeed, this scenario reveals the critical necessity of mitigating Bob's ability to manipulate his random blinding factor $r$, thereby averting him from forging a seemingly legitimate $B'$ and corresponding token pair $(x', C)$.

There are several potential strategies to counter this attack. These are, however, not without their trade-offs and should be analyzed considering the specific requirements of your system:

1. Use of Commitment Schemes: Before the key exchange, Bob could be required to commit to his secret and blinding factor using a cryptographic commitment scheme. Later, when the protocol has been executed, he can reveal the secret and blinding factor. Alice can then verify that the values match the commitment. This way, Bob cannot change his values midway through the protocol. However, this might introduce an additional complexity and require multiple rounds of communication.

2. Cryptographic Nonces: Bob's blinding factor could be generated as a cryptographic nonce that follows a specific rule set or pattern that Alice can verify without knowing the exact value of the nonce. However, this could potentially reduce the randomness of the blinding factor and hence weaken security, if not done carefully.

3. Secure Randomness Generation: Ensuring that Bob uses a securely generated random blinding factor could make it computationally unfeasible for Bob to find an alternative pair $(x', r')$ that gives a legitimate-looking $B'$. However, it might be challenging to enforce this in practice.

4. Zero-Knowledge Proofs: Bob could provide a zero-knowledge proof that shows he generated $B'$ according to the protocol, without revealing his secret or blinding factor. Implementing zero-knowledge proofs can be complex and might require additional computational resources.

UPDATE

I’ve tried to calculate the probability of finding a correct pair (x’, r’) to exploit this attack. While it’s indeed not computationally feasible to find the value of x’ it might be very important to ensure that both the value 'x' and the blinding factor 'r' are chosen from a space of a big enough size. For example if 'x' is constrained to be the utf-8 encoding of a small word as “test”, an attacker has a much easier task in trying to manipulate it to perform the attack. Anyway, after carefully evaluating and reflecting on the feasibility of such attack, I agree with what you guys said. It’s indeed almost impossible. It’s been interesting to delve deeper into this type of attack. 🙏

@V0nMis3s thanks for thinking it through, glad you came to the conclusion that it's secure on your own👍

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.