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