Author [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] Topic: $500 BitUSD Bounty - ECC Blinded Signatures  (Read 1493 times)

Offline bytemaster

$500 BitUSD Bounty - ECC Blinded Signatures
« on: June 30, 2015, 02:23:50 PM »

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.

Offline bytemaster

Re: $1000 BitUSD Bounty - ECC Blinded Signatures
« Reply #1 on: June 30, 2015, 02:35:51 PM »
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 arhag

  • Hero Member
  • *****
  • Posts: 1213
    • View Profile
    • My posts on Steem
  • BTS: arhag
  • GitHub: arhag
Re: $1000 BitUSD Bounty - ECC Blinded Signatures
« Reply #2 on: June 30, 2015, 07:17:22 PM »
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

Re: $1000 BitUSD Bounty - ECC Blinded Signatures
« Reply #3 on: June 30, 2015, 07:51:23 PM »
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: 1213
    • View Profile
    • My posts on Steem
  • BTS: arhag
  • GitHub: arhag
Re: $1000 BitUSD Bounty - ECC Blinded Signatures
« Reply #4 on: June 30, 2015, 08:27:19 PM »
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

Re: $1000 BitUSD Bounty - ECC Blinded Signatures
« Reply #5 on: June 30, 2015, 08:45:31 PM »
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: 1213
    • View Profile
    • My posts on Steem
  • BTS: arhag
  • GitHub: arhag
Re: $500 BitUSD Bounty - ECC Blinded Signatures
« Reply #6 on: June 30, 2015, 10:42:28 PM »
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 arhag

  • Hero Member
  • *****
  • Posts: 1213
    • View Profile
    • My posts on Steem
  • BTS: arhag
  • GitHub: arhag
Re: $1000 BitUSD Bounty - ECC Blinded Signatures
« Reply #7 on: July 01, 2015, 01:51:46 AM »
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 Ander

  • Hero Member
  • *****
  • Posts: 3488
    • View Profile
  • BTS: Ander
Re: $500 BitUSD Bounty - ECC Blinded Signatures
« Reply #9 on: July 01, 2015, 09:35:52 PM »
Glad to see this is being discussed, even if technically it is a bit over my head. +5%
Arhag's post was more than just 'a bit' over my head.

:D
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads

Offline arhag

  • Hero Member
  • *****
  • Posts: 1213
    • View Profile
    • My posts on Steem
  • BTS: arhag
  • GitHub: arhag
Re: $500 BitUSD Bounty - ECC Blinded Signatures
« Reply #10 on: July 03, 2015, 03:56:00 AM »
Is anyone actually working on this bounty? Here are my thoughts on how this bounty should be restructured.

I think wrapping the crypto primitives from secp256k1-zkp in a nice friendly C++ interface that we can use to intuitively do crypto math (adding/multiplying 256-bit numbers modulo order of the curve, adding curve points together, and multiplying a 256-bit scalar with a curve point, etc.) is a project of its own that could act as a prerequisite to this blinded signature project. It should also implement or wrap HMAC-SHA512 as that is needed for BIP32, which as far as I am aware libsecp256k1 does not implement but OpenSSL might. (By the way, why do we bother with a choice in the fc library between an OpenSSL implementation for the ECC math versus the libsecp256k1 one? At this point can't we just commit to the libsecp256k1 one? The secp256k1-zkp dependency is needed anyway for the Confidential Transaction stuff, right? It's also a bit frustrating seeing the public_key and private_key implementations depend on OpenSSL's bignum while libsecp256k1 apparently implements its own bignum stuff in order to do the ECC math.)

Then after that, those crypto primitives could be used to build extended_private_key and extended_public_key which can be used for proper BIP32 hierarchical deterministic wallets (honestly I was surprised to find out that wasn't already implemented in BitShares).

Then finally, the crypto primitives and extended_private_key/extended_public_key classes can all be used to implement Oleg's algorithm in a pretty straightforward and easy way. In fact at that point I would be interested in implementing my own modified version just to see how it works.

So I see this bounty broken down into those three separate projects. I think it would make this task more accessible for people. And in my opinion, the first one should be worth more than the second, and the second worth more than the third.

Offline bytemaster

Re: $500 BitUSD Bounty - ECC Blinded Signatures
« Reply #11 on: July 03, 2015, 04:52:21 AM »
Now that fc defaults to libsecp256k we might as well embrace it and clean up the wrapping of it.
I am also in favor of using libsec256k bignum support where possible.   

We had extended public/private keys but they were in bitshares not fc.   I would like to keep fc "application neutral" and general purpose.

Generally speaking I don't have the money to improve something that isn't broken, but I will award major BROWNIE.PTS for anyone who wants to take on these tasks. 
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: 1213
    • View Profile
    • My posts on Steem
  • BTS: arhag
  • GitHub: arhag
Re: $500 BitUSD Bounty - ECC Blinded Signatures
« Reply #12 on: July 03, 2015, 05:07:38 AM »
We had extended public/private keys but they were in bitshares not fc.   I would like to keep fc "application neutral" and general purpose.

Oh no wonder I couldn't find it. It isn't in the Graphene toolkit first of all. And while it is in the old BitShares codebase, it isn't in fc like you said. Are you guys planning on adding hierarchical deterministic wallet support into Graphene?

Well if you don't want to put that in fc, then either there is a weird dependency issue if you want this blinded signature algorithm in fc OR the interface of the algorithm needs to change to not depend on extended private/public keys OR the blinded signature algorithm should just be put into the Graphene toolkit and not fc (but if you go that route I would argue you should strip all ECC out of fc).
« Last Edit: July 03, 2015, 05:10:07 AM by arhag »

Offline pc

  • Hero Member
  • *****
  • Posts: 996
    • View Profile
    • Bitcoin - Perspektive oder Risiko?
  • BTS: cyrano
  • Witness: cyrano
  • Payrate: 100%
Re: $500 BitUSD Bounty - ECC Blinded Signatures
« Reply #13 on: July 03, 2015, 08:35:10 PM »
Is anyone actually working on this bounty?

I am, but at a very low pace.
Please vote for my BitShares witness "cyrano" and for my STEEM witness "cyrano.witness"!
Bitcoin - Perspektive oder Risiko? ISBN 978-3-8442-6568-2 http://bitcoin.quisquis.de

Offline arhag

  • Hero Member
  • *****
  • Posts: 1213
    • View Profile
    • My posts on Steem
  • BTS: arhag
  • GitHub: arhag
Re: $500 BitUSD Bounty - ECC Blinded Signatures
« Reply #14 on: July 03, 2015, 09:29:57 PM »
Is anyone actually working on this bounty?

I am, but at a very low pace.

Glad to hear someone is working on it.  :)

 

Google+