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.

Reiterating something @AdamISZ and I discussed on mastodon as followup:

The ROS attack does not seem to apply, because with only one round of interaction there is no meaningful distinction between parallel vs sequential composition in the protocol for issuing these tokens.

The ROS attack requires the client to initiate $l$ sessions in parallel, and only after obtaining the nonce commitments for all of these from the prover, adverserially choose challenges so that the resulting signatures from these sessions can be combined to obtain the $l+1$th signature/forgery.

Thanks for the analysis, @AdamISZ and @nothingmuch. Good to hear the ROS attack does not seem to apply.

Note that this blind DH scheme also has a potential use case in Silent Payments + coinjoin where coinjoin participant are asked to perform blind DH with the same key that they use to sign their coinjoin input. @LLFourn shared some concerns at 20m42s in this online discussion that this could slightly degrade the discrete log problem, though I can't say I fully understand this.

Thanks for the analysis, @AdamISZ and @nothingmuch. Good to hear the ROS attack does not seem to apply.

Note that this blind DH scheme also has a potential use case in Silent Payments + coinjoin where coinjoin participant are asked to perform blind DH with the same key that they use to sign their coinjoin input. @LLFourn shared some concerns at 20m42s in this online discussion that this could slightly degrade the discrete log problem, though I can't say I fully understand this.

The problem is actually in the privacy pass scheme too. As @nothingmuch mentions they reduce to one more security of ElGamal -- but this is known to be easier than DL and CDH. Very pessimistically it offers around ~86 bit security on secp256k1 (roughly cube root of the group order) if you can make 2^84 decryption queries! See Brown and Gallant: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.76.4917&rep=rep1&type=pdf. I'd say this is still very practical since you can't practically make 2^84 issuance sessions. 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.

IIRC when I first saw this gist I thought that it was something like PP but didn't have the time to see what the differences were. @nothingmuch has kindly done this for us and it looks to me like PP is something like the proved secure version of what is originally proposed. Are there any limitations of PP for this application?

Very pessimistically it offers around ~86 bit security on secp256k1 (roughly cube root of the group order) if you can make 2^84 decryption queries! See Brown and Gallant: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.76.4917&rep=rep1&type=pdf.

Nice, that's really interesting. Basic concept for those who won't get round to reading the paper: in a case where you can ask for repeated DH key exchanges with the same key (they call it 'static diffie hellman problem'), like this one (where the bank has some publically known key K), the security is notably different from the general case (intuitively: you're trying to solve the DLP, but you get to query something from the actual DL holder, whenever you like) . They have a method to extract a DL in something like u+ 2sqrt(v) operations (handwaving 'operations' here), where N is the group order and we write N = uv + 1, i.e. uv is the factorization of (N-1). The paper notes that this will be optimal (smallest) when u is roughly the cube root of N.

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. I can see that for secp256k1, we don't have the statistically "optimal" case (as per noted in the paper: "the largest prime factor of random integers is typically ~ N^(log2) which is about N^(1/3), i.e. again cube root of N). But for secp:

sage: E.order()                                                                 
115792089237316195423570985008687907852837564279074904382605163141518161494337
sage: factor(E.order()-1)                                                       
2^6 * 3 * 149 * 631 * 107361793816595537 * 174723607534414371449 * 341948486974166000522343609283189
sage: (E.order()-1)/341948486974166000522343609283189                           
338624364920977752681389262317185522840540224

assuming I didn't get it wrong (very possible! please check!), then: the biggest prime factor of N-1 is actually around 3.4 x 10^32 which is quite a bit off from being one third the size in bits, of N, which is around 1x10^77. The 'ideal' case would be if it were around 10^26. It should mean the security is notably above the theoretical worst case of ~86 (i.e. ~256/3).
Edit: I see now that we can indeed get close to the best case, because 107361793816595537 * 174723607534414371449 is indeed close to 10^26.

But anyway I guess part of your point in saying 'this is still reasonable' is that this is not all adversary side calculation, it requires queries to the 'oracle', that is actual protocol instantiations, which is very different and not practical to do exponential numbers of them. i.e., this is not something like Wagner where even though you need not just protocol execution, but parallel execution, that still isn't OK because you only need 10s or at worst 100s to crack it.

My impression from reading privacypass is: differences aren't too great, except that using a MAC with the key derived from the token, on some binding data, makes more sense than just transmitting the token directly. Reasoning as per @nothingmuch's statement above.

The difference between additive ( $T = Y + rG$ ) and multiplicative ( $T = rY$ ) tweaking - that is less clear to me whether one is better than the other (performance: trivially the former looks like an extra step, but I don't know about that), and the fact that the latter requires a mod inverse in unblinding.

The security proof in the privacypass paper linked above, for reduction to one-more-ElGamal decryption, make sense (although it's a little terse, e.g. about the DLEQ part), I think that basically exactly the same proof would carry over for this scheme; because in both cases the purported $(l+1)$ one-more-token-forgery adversary:

• can have its $Y$ value as per above come from a programmed RO where you set $Y$ to be a linear combination of $l+1$ $C$ values in pairs $(C, D)$ as El Gamal message encryptions
• can ask for token signatures (i.e $Q$ ( $=kP$ ) values), from $P$ ( $=Y + rG$ ) values from the El Gamal decryption oracle (this happens up to $l$ times, according to the rules of the game), which can be gotten by adding a random curve point $F$ and sending $(P, F)$ to the decryption oracle which returns $M$ such that $F - M = kP = Q$. (to emphasize, what I'm saying here is that I think this is the same for both schemes - basic idea is you can convert a token signing request into an ElGamal decryption request, because at heart they're both just a computational diffie hellman challenge - given $A$ and $B$, can you give me $abG$).
• in the Wagner scheme, if at the end the purported one-more-token adversary can output $l+1$ valid tokens $(t_i, Z_i)$ then each $Z$ should equal $kY$, and as per above that's k*(linear combination of C values). Thus you have $l+1$ equations in $l+1$ unknowns ( $kC_i$ ); invert it go get all the $kC_i$ values (this part is a bit tricky because we're in EC land, but I think that's right) - and these are the CDH solutions that let you calculate the decryptions as $D_i - kC_i = m_i$.

The only extra bit in the proof for the privacypass case is, because of the use of the MAC, you have to make an RO lookup table for that. Other than that I think it's the same - please correct me if I'm wrong!

To switch to (much!) more practical considerations - I think a switch from this scheme to a privacypass or variant would not be that big of a deal for developers - using a HMAC is hardly difficult, and multiplicative instead of additive tweaking is similarly available from libsecp256k1 libs. I would be inclined to do that, even if I believed my own reasoning above (which is trying to claim that we have the same one-more-forgery reduction proof, more or less), since the former is more studied and analyzed (and has at least one extra feature).

There is a sign error in the verification, Step 2. (confirmed it with waxwing)

R1' = e*A - s*G = -r*G
R2' = e*C'- s*B'= -r*B'

So the DLEQ proof would fail. To easily correct it, we can switch the operands in the subtractions.

Alice:
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'

@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.