Okay, this is my second attempt at coming up with a blinded signature algorithm that (attempts to) solve what I consider two problems with Oleg Andreev's algorithm. The first is the fact that the nonce is determined at the time the public key is determined (which I discussed in my previous post). The second is the unsolicited fund problem (which means that the balance remains unprotected by two-factor authentication from the time the sender sends it until the time the receiver moves it into a new balance that is protected by the public key derived from the blinded signature algorithm).
I believe I have come up with a solution (although for all I know it might be flawed like my
first attempt which allowed colluding attackers to gain access to the user's private key) that solves both of those problems while generating a standard
Schnorr signature. I had to give up on ECDSA since I'm not sure if it is even possible to do a blinded signature algorithm that satisfies these two requirements. Schnorr signatures have a lot of advantages over ECDSA anyway, like making threshold signatures really easy.
Again I assume there are three parties: Alice, Bob and Carol. Carol is sending unsolicited funds to Alice and Bob is Alice's designated blind signer.
This time Bob does not need to have a public key specific to each of his customers. (
Not true. See edit.) I believe the protocol I lay out below allows Bob to protect his private key even though it is being used to service all customers (meaning his customers cannot trick him to generate and return values that allow them to recover his private key... I hope). Bob's blind-signing private key is b and his published blind-signing public key is B = b*G. Alice's blind-receiving private key is a and her published blind-receiving public key is A. (Note I use blind-signing and blind-receiving rather than just active as an added security precaution. If I am wrong and there is a way to determine Alice's or Bob's private key, at least the damage is contained only to balances designated for blind signing rather than everything. This of course assumes that the blind-signing/blind-receiving private keys are determined through hardened child derivation from the corresponding active private keys, rather than normal child derivation.)
When Carol wants to send funds to Alice all she needs is the share secret z derived from Diffie-Hellman key exchange, Alice's blind-receiving public key A (which is published in her account metadata), and the blind-signing public key B of Alice's blind signer (Carol looks up in Alice's account metadata that Alice's blind signer is Bob, and then looks up in Bob's account metadata that his blind-signing public key is B). Carol then computes f = HMAC256(z, SHA256("blind")), and then the public key T = A + B + f*G. She sends the funds to a balance that can be withdrawn using a Schnorr signature corresponding to public key T (the full public key T is included rather than the address since Schnorr signatures do not allow recovering the public key from the signature) and also includes in the transaction the one-time public key that Alice needs to derive the shared secret z. When Alice receives the transaction, she can compute the shared secret z, then f, and then T, and verify that the transaction is valid before accepting it as payment for goods and services.
Later, when Alice wants to actually withdraw the funds, she creates a withdraw transaction which has digest h. She then connects to Bob with a secure connection, authenticates herself to Bob, and then they go through the following procedure (all operations are modulo the group order):
- Bob generates a random value r. Then, he computes P = (b + r)-1*G. Then, he sends (r, P) to Alice.
- Alice computes u = HMAC256(a, SHA256(h || r || P || "one")), v = HMAC256(a, SHA256(h || r || P || "two")), Q = P + u*G - v*(B + r*G), e = SHA256(h || Q), and w = -(e + v). Then, she sends w to Bob.
- Bob computes y = (b + r)*w + (b+r)-1. Then, he sends y to Alice.
- Alice computes s = y + u - e*(a + f - r), and she verifies that SHA256(h || (s*G + e*T)) == e.
Then (s, e) is the Schnorr signature on digest h with public key T. The blockchain can verify the signature is valid by verifying that SHA256(h || (s*G + e*T)) == e.
Bob only has access to r, P, w, and y. Since v is a pseudo-random number that Bob does not know, he cannot relate w to e. If Bob suspects a particular spent balance belongs to Alice, he can compute F
1 = s*G + e*T - P - (w+e)*(B + r*G) which should be u*G if it is in fact Alice's balance. He can also compute F
2 = s*G - y*G + e*A - e*r*G which should be u*G - e*f*G. Therefore, even though Bob cannot know the pseudo-random number u, if e
-1*(F
1 - F
2) == f*G, then Bob can know the balance does in fact belong to Alice. However, Bob also does not know f because he does not know the shared secret z. While Carol does know the shared secret z, if Bob and Carol were colluding, she could just trivially tell Bob that the balance does in fact belong to Alice. I don't believe there is any way for Bob alone to link the balance to Alice by following this protocol.
The remaining questions are: if Bob and Carol colluding together can generate a valid Schnorr signature on an arbitrary digest or even discover Alice's private key a; and, if Alice can trick Bob into revealing his private key b. While I don't have any proof that these two things are impossible, I haven't yet been able to figure out a way that it could be done. Of course, a review of the protocol is highly appreciated.
Edit: Once again a flaw. Though I still think users cannot trick Bob into revealing his key with the above protocol, it is still broken because users sharing the same blind signer essentially are not protected by two-factor authentication with respect to each other. Eve can legitimately authenticate with Bob and get him to blind sign a digest that allows her to steal Alice's balances
if she also knows Alice's private keys. The whole point of this is to provide two-factor authentication so the above protocol is broken if they use a universal public key B (and Bob uses the corresponding universal private key b). Instead B should be specific to each customer where its private key b is for example determined using hardened child private key derivation with SHA256(A) as the index. Alice could have Bob generate that public key for her once and then she would post it on her public metadata. Unsolicited transactions would still work fine. I will have to update the details of this protocol more formally to reflect these changes, but I have other changes planned with this protocol such as:
- Incorporating multiple blind signers (basically an n-of-n multisig) but with still only one final signature.
- Blind threshold signatures (of the t-of-n variety where t and n are both integers) with of course again one final signature. (A combination of item 1 and item 2 should also be possible where there are m different ti-of-ni threshold public keys for i = 1, ..., m, and the requirement is that all m of those produced a valid partial threshold signature.)
- Blind weighted signatures in which the sum of the prescribed weights of each key (these can also be t-of-n style threshold public keys à la item 2) in the set of signers needs exceed the prescribed threshold in order to be valid, but done in a way that doesn't reveal to the public or to the blind signers who the keys actually belong to and without revealing the weights nor threshold values, thus better protecting privacy (however it does necessarily reveal some structural information like the total number of keys in the set of possible signers and the indices of the signers in the set of possible signers that make up the subset of actual signers). This is done through the use of Pedersen commitments and range proofs from the blinded amount cryptography. Transaction size requirements are not trivial but are typically smaller than existing alternatives trying to do the same thing without blinding: one final signature on the overall transaction is necessary and only one range proof is necessary and can usually be very small since it only needs to hide the delta amount of (sum of weights of signers - threshold value) and even then may not be all that important to privacy, and roughly somewhere between (66+34*t) to (66+54*t) additional bytes are needed where t is the number of actual signers (which is quite good when you consider that a regular t-of-n multisig would have 20*n bytes for the n addresses and then t*64 bytes for the t signatures). The compactness comes from the fact that only one final signature is necessary and from the fact that the sender commits to the transaction withdraw condition the list of (public key, weight) commitments as a Merkle tree.
- Allowing the blind signers to force certain assertions (like setting a maximum allowed dollar value of funds transferred in the transaction and/or that the difference between the expiration time and the timestamp of the TaPoS referenced block be less than some prescribed value) to exist in the transaction they are blind signing while still not knowing the exact transaction they are signing. This is incredibly useful to people using blind signatures whose clients might be compromised. The user can verify out-of-band (say through an SMS, or via the class of one-time code they used to authenticate with the blind signer) the assertions that the blind signer is applying to their signature. So, if using SMS, they will know something is wrong if the assertion class displayed in the SMS doesn't match what their client UI said it was telling the blind signer to apply and thus the user won't type in the one-time code. If they are using a one-time code generated on a separate device and sending it with their request to the blind signer, they can know that worst case the attacker can only do the damage allowed by that assertion class and not any more. This way a hacker can't just wait until the user enters the one-time code for a transaction that is meant to be of the <$50 class and use it to steal their entire balance which is worth much much more than $50. Keep in mind that although this is still blind signing, adding unique assertions on transactions can compromise privacy with respect to the blind signer. For this reason, it is best if people followed a policy that kept the number of unique assertion class variations to just a handful of popular ones and if the client waited before broadcasting the final signed transaction until a random number (selected uniformly from some client-prescribed interval) of transactions with the same assertion class were confirmed in the blockchain starting from the time when the last blind signer sent their partial signature to the user (these are statistics the wallet host can provide to the wallet client).
So I will eventually post an upgraded version of the protocol some time later with all of those changes included.
Show Posts
). 
