Unique Ring Signatures using secp256k1 keys

Joshuar

hero member

Activity: 504

Merit: 500

eidoo wallet

Quote from: tacotime on March 21, 2015, 02:01:39 PM

Quote from: Joshuar on March 21, 2015, 01:02:45 PM

I know this thread may be a bit outdated. But, I was wondering, is the mixin number that can be used, truly infinite? I know you can use a mixin of say 100,000 etc, but what about a mixin of truly incredible size, like 1,000,000,000(1billion)?

Well, andytoshi and adam3us I know were trying to see if there was a way to compress ring signatures so that they reference the entire utxo set. I'm not sure how far they got. For maximum size of ring signature members, you're mainly limited to the memory of the system you are working on. Both size of the ring signature and time to verify is O(n) with the current signature algorithms.

For those outside Monero, a "mixin" is a ring signature member not the actual signer.

Ok thanks I understand, so limitations is just memory based.

tacotime

legendary

Activity: 1484

Merit: 1005

Quote from: Joshuar on March 21, 2015, 01:02:45 PM

I know this thread may be a bit outdated. But, I was wondering, is the mixin number that can be used, truly infinite? I know you can use a mixin of say 100,000 etc, but what about a mixin of truly incredible size, like 1,000,000,000(1billion)?

Well, andytoshi and adam3us I know were trying to see if there was a way to compress ring signatures so that they reference the entire utxo set. I'm not sure how far they got. For maximum size of ring signature members, you're mainly limited to the memory of the system you are working on. Both size of the ring signature and time to verify is O(n) with the current signature algorithms.

For those outside Monero, a "mixin" is a ring signature member not the actual signer.

Joshuar

hero member

Activity: 504

Merit: 500

eidoo wallet

I know this thread may be a bit outdated. But, I was wondering, is the mixin number that can be used, truly infinite? I know you can use a mixin of say 100,000 etc, but what about a mixin of truly incredible size, like 1,000,000,000(1billion)?

tacotime

legendary

Activity: 1484

Merit: 1005

Blinding has been added:
https://github.com/monero-project/urs/blob/master/urs.go#L547-L752

Use '-B' to blind your signature in the scheme described by andytoshi and gmaxwell (this is my first time messing with EC ops, hope I implemented it right!).

andytoshi

full member

Activity: 179

Merit: 151

-

Quote from: dillpicklechips on September 07, 2014, 12:35:04 AM

Another interesting use could be a type of ring signature coinjoin? A group gets together and determines the inputs. The ring signatures are used for each person to pick their outputs and can even have multiple outputs of different values. Once the group has enough messages specifying the output addresses the coinjoin transaction is created and signed. If any party of the group cheats the output values will total to be too high and the transaction is discarded.

This is a good idea. In the original coinjoin thread gmaxwell described a blinding scheme wherein users would initially provide their outputs in blinded form, have them blindsigned by the central server (or the "leader" node in a p2p setup) (or all participating parties, which is bandwidth-heavy), then reconnect anonymously to unblind them. For a p2p setup this means that somebody has to produce the blind signatures: either a leader must be selected, which adds complexity to the protocol, or every party signs every output, which leads to O(n^2) scaling.

With a ring signature on the other hand, each party would anonymously sign only their own outputs -- all nodes participate equally, with O(n) signatures. (Of course, the ring signatures are O(n) in size, so you might say this is still O(n^2) scaling. But since every signature uses the same keyring, this doesn't need to be passed around. Just the signature itself plus a blinding factor Q (one per signature, no need to use different ones per key in this case) as described in an earlier post.)

tacotime

legendary

Activity: 1484

Merit: 1005

Quote from: Crowex on September 07, 2014, 05:17:52 AM

Quote from: drawingthesun on September 05, 2014, 11:25:55 PM

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

Quote from: drawingthesun on September 05, 2014, 12: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?

You need to be careful here because voting and whistleblowing are not the same.
The linkability, or what the authors of this paper describe as uniqueness introduces restricted anonymity, as you described above, because the signer is not completely anonymous and can be exposed by all of the other people in the ring.
A blinding scheme could affect the linkability and increase the anonymity. It might mean that it is difficult for other signers to group together and expose a whistleblower but it also might mean that anybody could vote more than once.

The uniqueness would also seem to be necessary for any simple type of threshold scheme, although there may be other ways of achieving this.

Yes. Voting under this scheme would require signers to sign either a "Yea" or "Nay" message and submit it somehow to an authority who tallies the votes. Users could also vote for both Yea/Nay, which is a little strange but in the end doesn't effect the majority consensus decision one way or the other (hence you can get more than 100% votes, but the end decision will be based on the majority voting direction regardless).

Using gmaxwell's blinding scheme, you will no longer get unique X and Y values per message, so it can no longer be used for such a voting scheme. When I implement it I will just add a new flag that turns on or off this feature, because you may or may not want it. Additionally to simplify my coding I will probably make it sign H(m) instead of H(0) for the niZKP (I don't think it matters really what you sign, just that you can demonstrate you made a signature that proves knowledge of your private key).

Crowex

member

Activity: 111

Merit: 10

Quote from: drawingthesun on September 05, 2014, 11:25:55 PM

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

Quote from: drawingthesun on September 05, 2014, 12: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?

You need to be careful here because voting and whistleblowing are not the same.
The linkability, or what the authors of this paper describe as uniqueness introduces restricted anonymity, as you described above, because the signer is not completely anonymous and can be exposed by all of the other people in the ring.
A blinding scheme could affect the linkability and increase the anonymity. It might mean that it is difficult for other signers to group together and expose a whistleblower but it also might mean that anybody could vote more than once.

The uniqueness would also seem to be necessary for any simple type of threshold scheme, although there may be other ways of achieving this.

dillpicklechips

hero member

Activity: 994

Merit: 507

Another interesting use could be a type of ring signature coinjoin? A group gets together and determines the inputs. The ring signatures are used for each person to pick their outputs and can even have multiple outputs of different values. Once the group has enough messages specifying the output addresses the coinjoin transaction is created and signed. If any party of the group cheats the output values will total to be too high and the transaction is discarded.

andytoshi

full member

Activity: 179

Merit: 151

-

I did all of the writing but none of the ideas

So I think it's fair to give gmaxwell all the credit.

btchris

hero member

Activity: 672

Merit: 504

a.k.a. gurnec on GitHub

Quote from: andytoshi on September 06, 2014, 01:05:26 PM

Quote from: btchris on September 06, 2014, 10:39:38 AM

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?

Almost. If the signer actually threw away her q value, then yes. There is no way to enforce this. (But why wouldn't you? I dunno, depends on the context I guess..)

Got it, thanks.

Also, are you a co-author of the paper? I didn't mean to exclude you by calling it exclusively "gmaxwell's blinding scheme"...

andytoshi

full member

Activity: 179

Merit: 151

-

Quote from: btchris on September 06, 2014, 10:39:38 AM

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?

Almost. If the signer actually threw away her q value, then yes. There is no way to enforce this. (But why wouldn't you? I dunno, depends on the context I guess..)

tacotime

legendary

Activity: 1484

Merit: 1005

Quote

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?

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.

btchris

hero member

Activity: 672

Merit: 504

a.k.a. gurnec on GitHub

Quote from: andytoshi on September 06, 2014, 08:14:12 AM

Quote from: drawingthesun on September 05, 2014, 11:25:55 PM

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?

andytoshi

full member

Activity: 179

Merit: 151

-

Quote from: drawingthesun on September 05, 2014, 11:25:55 PM

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

Quote from: drawingthesun on September 05, 2014, 12: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.

drawingthesun

legendary

Activity: 1176

Merit: 1015

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

Quote from: drawingthesun on September 05, 2014, 12: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?

gmaxwell

staff

Activity: 4284

Merit: 8808

Quote from: drawingthesun on September 05, 2014, 12: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

Activity: 1176

Merit: 1015

Quote from: dillpicklechips on September 04, 2014, 06: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?

dillpicklechips

hero member

Activity: 994

Merit: 507

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

gmaxwell

staff

Activity: 4284

Merit: 8808

Quote from: andytoshi on September 04, 2014, 01: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?

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.

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.

andytoshi

full member

Activity: 179

Merit: 151

-

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.

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