Pages:
Author

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

hero member
Activity: 504
Merit: 500
eidoo wallet
March 22, 2015, 12:54:03 AM
#31
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.
legendary
Activity: 1484
Merit: 1005
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.
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)?
legendary
Activity: 1484
Merit: 1005
September 14, 2014, 12:27:26 AM
#28
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!).
full member
Activity: 179
Merit: 151
-
September 07, 2014, 01:44:06 PM
#27
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.)
legendary
Activity: 1484
Merit: 1005
September 07, 2014, 11:00:16 AM
#26
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. Smiley
 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).
member
Activity: 111
Merit: 10
September 07, 2014, 05:17:52 AM
#25
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. Smiley
 The uniqueness would also seem to be necessary for any simple type of threshold scheme, although there may be other ways of achieving this.
hero member
Activity: 994
Merit: 507
September 07, 2014, 12:35:04 AM
#24
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.
full member
Activity: 179
Merit: 151
-
September 06, 2014, 11:45:30 PM
#23
I did all of the writing but none of the ideas Smiley So I think it's fair to give gmaxwell all the credit.
hero member
Activity: 672
Merit: 504
a.k.a. gurnec on GitHub
September 06, 2014, 06:39:22 PM
#22
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"...
full member
Activity: 179
Merit: 151
-
September 06, 2014, 01:05:26 PM
#21
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..)
legendary
Activity: 1484
Merit: 1005
September 06, 2014, 10:43:32 AM
#20
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.
hero member
Activity: 672
Merit: 504
a.k.a. gurnec on GitHub
September 06, 2014, 10:39:38 AM
#19
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?
full member
Activity: 179
Merit: 151
-
September 06, 2014, 08:14:12 AM
#18
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.
legendary
Activity: 1176
Merit: 1015
September 05, 2014, 11:25:55 PM
#17
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?
staff
Activity: 4284
Merit: 8808
September 05, 2014, 04:15:44 PM
#16
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.
legendary
Activity: 1176
Merit: 1015
September 05, 2014, 12:39:28 PM
#15
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?
hero member
Activity: 994
Merit: 507
September 04, 2014, 06:57:38 PM
#14
This sounds potentially useful for voting systems. You can see that everyone voted without seeing who voted for who.
staff
Activity: 4284
Merit: 8808
September 04, 2014, 03:51:39 PM
#13
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.
full member
Activity: 179
Merit: 151
-
September 04, 2014, 01: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.
Pages:
Jump to: