Unique Ring Signatures using secp256k1 keys - page 2.

Crowex

member

Activity: 111

Merit: 10

Quote from: andytoshi on September 03, 2014, 09:04:54 PM

Quote from: gmaxwell on September 03, 2014, 07:31:34 PM

To avoid this, you generate a random blinding key Q and sign with gP+gQ instead, proving knoweldge of P, then you forget Q. Later you cannot be coerced because you can honestly claim to have forgotten Q.

Tacotime and myself were quite confused by this ... after a long IRC conversation I believe the three of us landed on this description of how exactly the blinding is done.

That's really neat.

Quote

the signer generates q values for all signers. She proves
knowledge of each one of them

Could you simplify the protocol a little by using the same q value for all signers?
I don't really know exactly what the ring signature protocol is (any links?) so maybe there are disadvantages to doing this?

andytoshi

full member

Activity: 179

Merit: 151

-

Quote from: gmaxwell on September 03, 2014, 07:31:34 PM

To avoid this, you generate a random blinding key Q and sign with gP+gQ instead, proving knoweldge of P, then you forget Q. Later you cannot be coerced because you can honestly claim to have forgotten Q.

Tacotime and myself were quite confused by this ... after a long IRC conversation I believe the three of us landed on this description of how exactly the blinding is done.

tacotime

legendary

Activity: 1484

Merit: 1005

Quote from: andytoshi on September 03, 2014, 07:41:58 PM

I think you made a typo tacotime, because two keys are repeated. What you mean is

Code:

{
        "0":"02b631fc5e901982a8d130ea65f2966e99a51375030b3c9c64288f4631943ed194"
        "1":"032e76a7de5584eee15a23e872c08543fcca5445d844a6ce63d37c5d25ce377888",
        "2":"04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"
}

and I can indeed verify your signed message with this ring Cheesy

Ah, yes, correct, I'll fix it up above.

andytoshi

full member

Activity: 179

Merit: 151

-

I think you made a typo tacotime, because two keys are repeated. What you mean is

Code:

{
        "0":"02b631fc5e901982a8d130ea65f2966e99a51375030b3c9c64288f4631943ed194"
        "1":"032e76a7de5584eee15a23e872c08543fcca5445d844a6ce63d37c5d25ce377888",
        "2":"04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"
}

and I can indeed verify your signed message with this ring Cheesy

gmaxwell

staff

Activity: 4284

Merit: 8808

Something to watch out for here is that it's coercion vulnerable, which I think I'd addressed in my science project work.

E.g. I can go to Satoshi and Andytoshi and demand they give me they publish public keys, and then in doing so prove the message came from tacotime.

To avoid this, you generate a random blinding key Q and sign with gP+gQ instead, proving knoweldge of P, then you forget Q. Later you cannot be coerced because you can honestly claim to have forgotten Q.

Making the threshold scheme e.g. where you have a set of N of M signers where _no_ person knows who all the N (not even the members themselves) is more complicated with this blinding, however, because someone must create the Qs for the involuntary participants.

You currently don't support composing signatures but you totally could doing so results in useful applications.

tacotime

legendary

Activity: 1484

Merit: 1005

Quote from: andytoshi on September 03, 2014, 06:35:35 PM

Do you know if they are aware of our value blinding scheme described in my writeup?

Yup, the math/crypto guys that have been hired have gone over it a lot. Unfortunately, it's a rather large change in terms of core code that we'd have to make and right now we're still trying to figure out why even basic stuff in the codebase like network propagation/syncing is dysfunctional. Large, likely hardfork changes like that will be a while off to implement, although it is a really cool idea.

tacotime

legendary

Activity: 1484

Merit: 1005

Quote

Edit: Ok, looks like we have to generate the keyring manually? To make a keypair you use the -g command. There is an example keyring that comes with program

Code:

{
        "0":"024627032575180c2773b3eedd3a163dc2f3c6c84f9d0a1fc561a9578a15e6d0e3",
        "1":"02b266b2c32ba5fc8d203c8f3e65e50480dfc10404ed089bad5f9ac5a45ffa4251",
        "2":"031ea759e3401463b82e2132535393076dde89bf2af7fc550f0793126669ffb5cd",
        "3":"03320cd05f3538159693cd253c30ec4972fa06ad10f1812951923a5ea063e9748c",
        "4":"039b9033d0377e3af7fdf4369134f3ec96aa03326fd07f89d60dc3ba70d0a19956",
        "5":"03c81094edb63ba28b1e4d5556d91dc030b725e105be94fb4005bee987f80a38f0",
        "6":"032077679a3f1579acc22308f09b7d5f597cba4ea9f314b8aaf86ab2f052fa0157",
        "7":"039b9033d0377e3af7fdf4369134f3ec96aa03326fd07f89d60dc3ba70d0a19956",
        "8":"02dcdb96d05d6cd36ce7014a69ebce8b48f8d7de46ce3bfa99482af65284697e13",
        "9":"04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"
}

So I guess we will just copy the format.

My key for this thread is 02b631fc5e901982a8d130ea65f2966e99a51375030b3c9c64288f4631943ed194

Yes, this is correct. Here is a test pubkey from me:

Code:

032e76a7de5584eee15a23e872c08543fcca5445d844a6ce63d37c5d25ce377888

I will sign using this keyring:

Code:

{
        "0":"02b631fc5e901982a8d130ea65f2966e99a51375030b3c9c64288f4631943ed194"
        "1":"032e76a7de5584eee15a23e872c08543fcca5445d844a6ce63d37c5d25ce377888",
        "2":"04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"
}

(The first is andytoshi, the second is me, and the third is Satoshi (from the genesis block).)

This is the message:

Code:

The Times 03/Jan/2009 Chancellor on brink of second bailout for banks

Using the verify text feature, here's the returned signature for you to validate:

Code:

144VfXoJFBzxhFe7c4GXsCpPogkhXkkrQut5r7waHxgUv+FiH39RvZ5LSYEUFR2UXKfgcgzxZ48Dd3f2CdgycnUKHk+FFkDCK438Zdpza9RaAyh5VCMcpe5d1Yj29SP1111vZtL&5dma9x2cspgqM3TZZugDuyjVz5dmJLC9JU4JVb4frTdb&BnJdCj4DAsr6QzK22Qx5n4ts8Rzas4s23Cs5YDDirThA&+HJmdbgEnpXcQ7mDnuywXsy6bdzg5zN1RCdeYN8RLnhnm&78K3TP8PbjrMKWKEHmWM1Cf7nUsnse3EQ6owKoJFi3f3&9duvujESzXaHTKxDEJPESYoSRVYbVxHQej3FEZbysMGc&

This signature is from either me, or andytoshi, or Satoshi.

If you check the key file, you will also see that generated keys include mainnet V1 addresses (although these aren't used by the program itself).

andytoshi

full member

Activity: 179

Merit: 151

-

Do you know if they are aware of our value blinding scheme described in my writeup?

tacotime

legendary

Activity: 1484

Merit: 1005

Quote from: andytoshi on September 03, 2014, 06:20:20 PM

This is great stuff tacotime! I bet we have a lot of fun with this. Maybe I will install Go, generate a key, and post it here for us to play ringsigning games.

Are you involved with Monero?

Thanks! Admittedly I don't follow 100% of the ring signature crypto code that Hein wrote, but the usage and verification is as expected. One thing I did add was sorting to the key ring input based on the public key X and Y values, so that ordering of the keyring did not impact signature generation/verification.

The output for signatures is in Base58, in the format:

Code:

X+Y+[C_0]&[C_1]&...&[C_N]&+[T_0]&[T_1]&...&[T_N]&

I am involved with Monero as a (volunteer) member of the core team, although most of what I do is higher level consulting on how to maintain anonymity using the stock ring signature code. This has been kind of a "rabbit hole" problem of endlessly more things to consider in terms of deanonymization attack vectors, but we should have some publications and proposals out soon that further investigate this that you and gmaxwell will probably be interested in.

andytoshi

full member

Activity: 179

Merit: 151

-

This is great stuff tacotime! I bet we have a lot of fun with this. Maybe I will install Go, generate a key, and post it here for us to play ringsigning games.

Are you involved with Monero?

Edit: Ok, looks like we have to generate the keyring manually? To make a keypair you use the -g command. There is an example keyring that comes with program

Code:

{
        "0":"024627032575180c2773b3eedd3a163dc2f3c6c84f9d0a1fc561a9578a15e6d0e3",
        "1":"02b266b2c32ba5fc8d203c8f3e65e50480dfc10404ed089bad5f9ac5a45ffa4251",
        "2":"031ea759e3401463b82e2132535393076dde89bf2af7fc550f0793126669ffb5cd",
        "3":"03320cd05f3538159693cd253c30ec4972fa06ad10f1812951923a5ea063e9748c",
        "4":"039b9033d0377e3af7fdf4369134f3ec96aa03326fd07f89d60dc3ba70d0a19956",
        "5":"03c81094edb63ba28b1e4d5556d91dc030b725e105be94fb4005bee987f80a38f0",
        "6":"032077679a3f1579acc22308f09b7d5f597cba4ea9f314b8aaf86ab2f052fa0157",
        "7":"039b9033d0377e3af7fdf4369134f3ec96aa03326fd07f89d60dc3ba70d0a19956",
        "8":"02dcdb96d05d6cd36ce7014a69ebce8b48f8d7de46ce3bfa99482af65284697e13",
        "9":"04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"
}

So I guess we will just copy the format.

My key for this thread is 02b631fc5e901982a8d130ea65f2966e99a51375030b3c9c64288f4631943ed194

tacotime

legendary

Activity: 1484

Merit: 1005

As part of ongoing efforts of the Monero Project, a small program has been generated that allows you to do 1-of-N ring signatures using a secp256k1 keypair and a keyring of public keys. The program signs both binaries and text files.

https://github.com/monero-project/urs

To build and install, use this command after installation of Go:

Code:

go get -u -v github.com/monero-project/urs/...

According to the paper, unique ring signatures are anonymous except in the case of signing the same message multiple times (in which case X and Y in the signature appear to be the same).

http://csiflabs.cs.ucdavis.edu/~hbzhang/romring.pdf

A potential usage might be to sign gitian asserts from a trusted keyring anonymously that contains well known members of the Bitcoin project. Another usage would be for members of a trusted community of Bitcoin users to anonymously vote for some proposal by signing it separately and publishing their signatures.

Thanks to Hein Meling for the initial URS implementation, Conformal Systems for their immensely useful libraries, and gmaxwell for inspiration.

Topic: Unique Ring Signatures using secp256k1 keys - page 2. (Read 7032 times)