Bitcointalk Mobile Browser presented by IRLBTC™

>> (p.1)

Author

Topic: Unique Ring Signatures using secp256k1 keys (Read 7053 times)

tacotime (OP)

Legendary

Offline

Activity: 1484
Merit: 1011

Unique Ring Signatures using secp256k1 keys

September 03, 2014, 09:12:28 PM

Merited by ABCbits (2)

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.

Code:

XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns

andytoshi

Full Member

Offline

Activity: 179
Merit: 162

-

Re: Unique Ring Signatures using secp256k1 keys

September 03, 2014, 11:20:20 PM
Last edit: September 03, 2014, 11:34:12 PM by andytoshi

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 (OP)

Legendary

Offline

Activity: 1484
Merit: 1011

Re: Unique Ring Signatures using secp256k1 keys

September 03, 2014, 11:30:01 PM

Quote from: andytoshi on September 03, 2014, 11: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.

Code:

XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns

andytoshi

Full Member

Offline

Activity: 179
Merit: 162

-

Re: Unique Ring Signatures using secp256k1 keys

September 03, 2014, 11:35:35 PM

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

tacotime (OP)

Legendary

Offline

Activity: 1484
Merit: 1011

Re: Unique Ring Signatures using secp256k1 keys

September 03, 2014, 11:43:08 PM
Last edit: September 04, 2014, 12:44:27 AM by tacotime

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

Code:

XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns

tacotime (OP)

Legendary

Offline

Activity: 1484
Merit: 1011

Re: Unique Ring Signatures using secp256k1 keys

September 03, 2014, 11:49:09 PM

Quote from: andytoshi on September 03, 2014, 11: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.

Code:

XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns

gmaxwell

Moderator
Legendary

Offline

Activity: 4494
Merit: 9697

Re: Unique Ring Signatures using secp256k1 keys

September 04, 2014, 12:31:34 AM
Last edit: September 04, 2014, 12:41:36 AM by gmaxwell

Merited by ABCbits (2)

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.

andytoshi

Full Member

Offline

Activity: 179
Merit: 162

-

Re: Unique Ring Signatures using secp256k1 keys

September 04, 2014, 12:41:58 AM

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

Code:

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

tacotime (OP)

Legendary

Offline

Activity: 1484
Merit: 1011

Re: Unique Ring Signatures using secp256k1 keys

September 04, 2014, 12:44:03 AM

Quote from: andytoshi on September 04, 2014, 12:41:58 AM

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

Code:

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

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

Code:

XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns

andytoshi

Full Member

Offline

Activity: 179
Merit: 162

-

Re: Unique Ring Signatures using secp256k1 keys

September 04, 2014, 02:04:54 AM

#10

Quote from: gmaxwell on September 04, 2014, 12:31:34 AM

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.

Crowex

Member

Offline

Activity: 111
Merit: 10

Re: Unique Ring Signatures using secp256k1 keys

September 04, 2014, 04:43:01 PM

#11

Quote from: andytoshi on September 04, 2014, 02:04:54 AM

Quote from: gmaxwell on September 04, 2014, 12:31:34 AM

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

Offline

Activity: 179
Merit: 162

-

Re: Unique Ring Signatures using secp256k1 keys

September 04, 2014, 06:47:29 PM

#12

Quote

I don't really know exactly what the ring signature protocol is (any links?) so maybe there are disadvantages to doing this?

Nope. Even with the same q, nobody except the signer is able to prove that they were or weren't the signer, and if the signer forgets her q then she can't either.

The "different q's" thing was just an artifact of my initial misunderstanding when I wrote the article.

gmaxwell

Moderator
Legendary

Offline

Activity: 4494
Merit: 9697

Re: Unique Ring Signatures using secp256k1 keys

September 04, 2014, 08:51:39 PM

#13

Quote from: andytoshi on September 04, 2014, 06:47:29 PM

Quote

I don't really know exactly what the ring signature protocol is (any links?) so maybe there are disadvantages to doing this?

You need different Qs if you want multiple signers (in the BRS style) and for them to be mutually anonymous from each other. E.g. to select a group of N out of M trusted parties, where the N don't know who each other are.

dillpicklechips

Hero Member

Offline

Activity: 994
Merit: 507

Re: Unique Ring Signatures using secp256k1 keys

September 04, 2014, 11:57:38 PM

#14

This sounds potentially useful for voting systems. You can see that everyone voted without seeing who voted for who.

drawingthesun

Legendary

Offline

Activity: 1176
Merit: 1015

Re: Unique Ring Signatures using secp256k1 keys

September 05, 2014, 05:39:28 PM

#15

Quote from: dillpicklechips on September 04, 2014, 11:57:38 PM

This sounds potentially useful for voting systems. You can see that everyone voted without seeing who voted for who.

Could a ring signature set of several million people be created? Is there a limit to how many people mix together?

gmaxwell

Moderator
Legendary

Offline

Activity: 4494
Merit: 9697

Re: Unique Ring Signatures using secp256k1 keys

September 05, 2014, 09:15:44 PM

#16

Quote from: drawingthesun on September 05, 2014, 05:39:28 PM

Could a ring signature set of several million people be created? Is there a limit to how many people mix together?

Only that it has linear scaling. Such a signature would be many megabytes in size and would take minutes to verify with state of the art ECC code.

drawingthesun

Legendary

Offline

Activity: 1176
Merit: 1015

Re: Unique Ring Signatures using secp256k1 keys

September 06, 2014, 04:25:55 AM

#17

Quote from: gmaxwell on September 05, 2014, 09:15:44 PM

Quote from: drawingthesun on September 05, 2014, 05:39:28 PM

Could a ring signature set of several million people be created? Is there a limit to how many people mix together?

Only that it has linear scaling. Such a signature would be many megabytes in size and would take minutes to verify with state of the art ECC code.

So if we had 1,000,000 people apart of this signature, you could never find out who voted or released/leaked info unless the other 999,999 admitted it wasn't them?

andytoshi

Full Member

Offline

Activity: 179
Merit: 162

-

Re: Unique Ring Signatures using secp256k1 keys

September 06, 2014, 01:14:12 PM

#18

Quote from: drawingthesun on September 06, 2014, 04:25:55 AM

Quote from: gmaxwell on September 05, 2014, 09:15:44 PM

Quote from: drawingthesun on September 05, 2014, 05:39:28 PM

Could a ring signature set of several million people be created? Is there a limit to how many people mix together?

Only that it has linear scaling. Such a signature would be many megabytes in size and would take minutes to verify with state of the art ECC code.

So if we had 1,000,000 people apart of this signature, you could never find out who voted or released/leaked info unless the other 999,999 admitted it wasn't them?

If you used the blinding scheme gmaxwell described above, all 1,000,000 could "admit" it wasn't them and nobody would be able to prove otherwise.

btchris

Hero Member

Offline

Activity: 672
Merit: 509

a.k.a. gurnec on GitHub

Re: Unique Ring Signatures using secp256k1 keys

September 06, 2014, 03:39:38 PM

#19

Quote from: andytoshi on September 06, 2014, 01:14:12 PM

Quote from: drawingthesun on September 06, 2014, 04:25:55 AM

So if we had 1,000,000 people apart of this signature, you could never find out who voted or released/leaked info unless the other 999,999 admitted it wasn't them?

If you used the blinding scheme gmaxwell described above, all 1,000,000 could "admit" it wasn't them and nobody would be able to prove otherwise.

It's even stronger than that, isn't it? If the signer used gmaxwell's blinding scheme, than none of the 1,000,000 (including the actual signer) are capable of proving that they either did or didn't sign it (even if any of them wanted to), correct?

tacotime (OP)

Legendary

Offline

Activity: 1484
Merit: 1011

Re: Unique Ring Signatures using secp256k1 keys

September 06, 2014, 03:43:32 PM

#20

Quote

Well, unless the computer used to generate the signature was compromised so that the private and ephemeral keys were known.

Haven't gotten around to implementing that yet, still dealing with the recent Monero attack. But hopefully soon.

Code:

XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns

Pages: [1] 2 » All

Page 1

Viewing Page: 1