Author Topic: $500 BitUSD Bounty - ECC Blinded Signatures  (Read 10344 times)

0 Members and 1 Guest are viewing this topic.

Offline karnal

  • Hero Member
  • *****
  • Posts: 1068
    • View Profile
Glad to see this is being discussed, even if technically it is a bit over my head. +5%

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
By the way, I don't think the scheme discussed in this thread is what is typically known as "blinded signatures" in the literature. Here you are requiring that no one other than the person who blinds the digest and unblinds the signature to be able to associate the public key corresponding to the signature to the blinding signer. But in typical blinded signatures (useful in eCash and voting) that requirement isn't necessary and in fact not desirable. In those situation we would want everyone to be able to know the authority that signed the digest; we just don't want anyone (including the authority) other than the blinder/unblinder to know the association between the digest/signature and the identity of blinder/unblinder. I believe that cryptographic procedure will also be desirable to include in the future (as far as I am aware, it will be needed for voting since the alternative of ring signatures leads to large transaction sizes), so it makes it especially confusing to use the same name for the scheme described in this thread.


Any way that we could modify this to allow the signer to know that they had the private key for ONE_TIME_PUBLIC_KEY but not give them enough information to tie it back to ME?

What would be the purpose of that? If the signer knows they can sign for a particular ONE_TIME_PUBLIC_KEY then they must know that the balance is meant for one of their customers. But if they cannot know which specific customer it is for (because we don't want to leak that information), then what would they possibly do with this knowledge?
« Last Edit: July 01, 2015, 02:00:06 am by arhag »

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
Here is my attempt at modifying the protocol to fix the unsolicited sending problem. I am not sure if this change doesn't break the security (Yes it does! See Edit2) or privacy guarantees of the original protocol. I highly appreciate review of this modified protocol.

There are three parties involved: Alice, Bob, and Carol. Bob is designated as Alice's blinded signer publicly in her account metadata. Carol wants to send funds to Alice without needing any private data from Alice. Carol knows she is sending the funds to Alice, so there is no point in blinding Alice's withdraw signature from Carol. The protocol however needs to guarantee that Carol does not have enough information to get Bob to sign a digest that allows Carol to reclaim the sent funds. Bob only needs to verify that a particular user requesting him to generate a blinded signature is a customer (and verify their identity through whatever means is appropriate to provide the multisig protection) before signing with the appropriate keys meant only for that customer. No one other than Alice or Carol (this includes Bob) should be able to associate the sent balance to Alice at any time in this process including after Alice withdraws the balance using the unblinded signature.

Alice's extended public key is Ka (and corresponding private key is ka). Bob's extended public key is Kb (and corresponding private key is kb which is specific to Alice.

Carol generates a one-time private key o (corresponding public key is O). She generates shared secret s from the x-coordinate of o * Ka (which can also be derived by Alice using O * ka). The modified shared secret s' = H (s || "modified"). The index i = H(s' || "index1"), a second index j = H(s' || "index2"), and the values v1 = H(s' || "value1") and v2 = H(s' || "value2"). Comparing to the paper, v1 == a-1c-1 and v2 == d. Carol also uses index i to derive the child public keys P (represents the same P as the one in the paper) and Q', where P = ND(Kb, 2*i + 0) and Q' = ND(Kb, 2*i + 1). She also uses index j to derive the child public key B' = ND(Ka, j). Comparing to the paper, Q' = a-1Q and B' = a-1bG.

Carol then calculates kG = v1P (from the paper, kG == a-1c-1P), and r which is defined to be the x-coordinate of kG. From the paper, T (the public key in the withdraw condition) is given by T = r-1(a-1bG + a-1Q + a-1c-1dP). We can rewrite this as T = r-1(B' + Q' + v1v2P), which Carol is able to compute.

When Alice receives the funds she can verify that Carol followed the correct procedure. She is able to generate all the same values (including r) starting from the shared secret s. When Alice finally wants to withdraw the funds in another transaction she is going to need the values for a, b, c, and d. Through the index j she is able to calculate the private key for B', which is equivalent to a-1b from the paper (call that value v3). By selecting a random value for a, Alice can then calculate the remaining values: b = av3, c = a-1(v1)-1, and d = v2. This then allows Alice to generate the blinded digest of digest h: h2 = ah + b. However, Alice cannot only send h2 and i to Bob, she must also send a to Bob. As far as I am able to tell, this should not reveal any new information to Bob (would really appreciate a check on this). Also with knowledge of a, even if Bob is colluding with Carol, they cannot withdraw the funds because they are unable to derive b (Not true! See Edit2). However, if Bob and Carol are colluding, Carol can share j with Bob which along with a and h2 allows Bob to associate h2 (and thus Alice's identity) to the digest h (and thus to the balance that Carol sent Alice). But if Bob and Carol are colluding anyway, Carol could just simply tell Bob this information as she was the one who sent the funds to Alice in the first place.

Bob now takes h2, i and a provided by Alice and computes p-1 (where P == p-1G) and q' (where Q' == q'G == a-1Q == a-1qp-1G). Then he computers q = apq'. Finally, Bob computes s1 = ph2 + q, sends s1 back to Alice.

Alice can then use s1 to compute s2 = cs1 + d. The unblinded signature on digest h is then (r, s2) which is signed using a key corresponding to public key T. This signature allows Alice to withdraw her funds.

Edit: Require Bob's extended public key to be a hardened child specific to Alice or else Alice could determine Bob's master private key by getting him to blinded sign the same hash but with different indices. Even if the private keys for P and Q' were uncorrelated, the master private key could have still been computed by getting him to blind sign the same hash four times but with different indices. This also removes the requirement for Bob to track indices for which he has signed before.

Edit2: Major flaw found with the above. If Bob and Carol are colluding, they can determine ka after Alice signs the transaction that withdraw funds sent by Carol. s2 = c*p*a*h + c*p*a*(ka + j) + c*p*a*q' + d.  Carol knows a*c, d, and j. Bob knows p and q'. Together they know y1 and y2 where s2 = y1*(h + ka) + y2. After Alice publishes the transaction to the network to withdraw the funds, she also necessarily publishes h and s2, and so at that point Bob and Carol can simply solve for Alice's private key ka. :( Back to the drawing board I guess.
« Last Edit: July 28, 2015, 11:16:23 pm by arhag »

Offline bytemaster

This approach allows ME to have someone else sign SOMETHING without them being able to prove they were the one who signed it which could be useful for multi-sig / two-factor on confidential transactions.

Ah, got it. The tricky thing is that the only person who is able to derive this one-time public key is the one who can generate a, b, c, d, P, and Q (Alice in the example). But I would think for private multisig to be useful the sender of the funds needs to be able to independently specify the public key that is allowed to withdraw the funds using only public information about the receiver. So that means unsolicited funds could not be sent to Alice with this kind of blinded withdraw condition. It would require Alice to provide the sender with the one-time public key that Alice generates in order for the sender to send Alice the funds.

As an aside, for this to be really useful, it would be nice it the scheme could be augmented into a blinded threshold signature scheme (to generalize from a blinded 2-of-2 multisig to a blinded M-of-N multisig). In fact, I would be concerned with being dependent on another party to be able to access my funds. But at least that part can be solved through a convention of everyone using a 1-of-2 multisig where the 2 keys are different one-time public keys: one between ME and the regular blinded signer, and one between ME and my cold storage key acting as the blinded signer.

Worst case you have to sweep all funds you receive from "single-signature" to "multi-signature" leaving them vulnerable for a short period of time to your single private key being hacked. 
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
This approach allows ME to have someone else sign SOMETHING without them being able to prove they were the one who signed it which could be useful for multi-sig / two-factor on confidential transactions.

Ah, got it. The tricky thing is that the only person who is able to derive this one-time public key is the one who can generate a, b, c, d, P, and Q (Alice in the example). But I would think for private multisig to be useful the sender of the funds needs to be able to independently specify the public key that is allowed to withdraw the funds using only public information about the receiver. So that means unsolicited funds could not be sent to Alice with this kind of blinded withdraw condition. It would require Alice to provide the sender with the one-time public key that Alice generates in order for the sender to send Alice the funds.

As an aside, for this to be really useful, it would be nice it the scheme could be augmented into a blinded threshold signature scheme (to generalize from a blinded 2-of-2 multisig to a blinded M-of-N multisig). In fact, I would be concerned with being dependent on another party to be able to access my funds. But at least that part can be solved through a convention of everyone using a 1-of-2 multisig where the 2 keys are different one-time public keys: one between ME and the regular blinded signer, and one between ME and my cold storage key acting as the blinded signer.

Offline bytemaster

This approach allows ME to have someone else sign SOMETHING without them being able to prove they were the one who signed it which could be useful for multi-sig / two-factor on confidential transactions.

I now have a ONE TIME PUBLIC KEY that I know has been signed by SOMEONE  but that SOMEONE cannot use knowledge of the ONE TIME PUBLIC KEY to link back to ME.   

Any way that we could modify this to allow the signer to know that they had the private key for ONE_TIME_PUBLIC_KEY but not give them enough information to tie it back to ME?
« Last Edit: June 30, 2015, 07:57:32 pm by bytemaster »
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
I read the paper and it seems like if Bob does blind_sign on two different blind_digests but with the same index i, he will reveal p and q which thus reveals his parent private key due to the nature of the CKD. So Bob would need to make sure that he never signs with the same index i twice.

Also, this method seems somewhat unfortunate because there doesn't seem to be a way to prove to the public that the only signer of that public key is some specific account. I'm not sure how this plays into what you plan with privacy, but it seems this particular blind signature scheme would not be very useful for a private voting system for example.

Offline bytemaster

I am looking for ways to combine this technique with stealth addresses and confidential transactions to enable perfectly private transactions with 2-factor authentication:

It would be ideal if a blind_public_key between alice_priv and bob_pub could be derived by SAM with only a one time key and Alice's Extended public key, and Bob's Extended Public key.

For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline bytemaster

I am looking for the following algorithm to be made available in fc using libsecp256k if possible:

I remember Oleg Andreev working on an ECC blind signatures scheme.
http://blog.oleganza.com/post/77474860538/blind-signatures

It seems he has a working implementation based on obj-c.
https://github.com/oleganza/CoreBitcoin/blob/master/CoreBitcoin/BTCBlindSignature.h

Proposed/Expected API

Code: [Select]
fc::ecc::extended_private_key  bob;
fc::ecc::extended_private_key  alice;
fc::ecc::extended_public_key   bob_pub = bob.extended_public_key();

// a public key that only bob has the ability to generate blinded signatures for
fc::ecc::public_key    pub_key = fc::ecc::blind_public_key(  alice, bob_pub, i );

fc::sha256  digest;

int i = 0;

fc::ecc::blinded_hash          blind_digest =  fc::ecc::blind_hash( alice, bob_pub, digest, i );
fc::ecc::blind_signature       blind_sig      =  fc::ecc::blind_sign( bob, blind_digest, i );
fc::ecc::compact_signature unblind_sig  =  fc::ecc::unblind_signature( alice, bob_pub, blind_sig, i );
 
FC_ASSERT( fc::ecc::public_key( digest, unblind_sig ) == pub_key )


« Last Edit: June 30, 2015, 07:59:44 pm by bytemaster »
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.