Unique Ring Signatures using secp256k1 keys

[andytoshi]

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

[btchris]

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]

I did all of the writing but none of the ideas So I think it's fair to give gmaxwell all the credit.

[dillpicklechips]

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.

[Crowex]

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.

[tacotime]

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

[andytoshi]

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]

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

[Joshuar]

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]

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]

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.