Ring signatures

[burdges]

We might've some use for simple ring signatures so that validators can authenticate themselves as being validators or parachain validators without showing their specific session key.

There is a simple scheme in https://www.youtube.com/watch?v=Rnl1g6IccpY but designated-verifier schemes might be slightly stronger in our context https://pdfs.semanticscholar.org/2652/4fd1c19d8aa110e650db85b3c742a2f340c3.pdf and http://dspace.lib.fcu.edu.tw/bitstream/2377/30122/1/CI01B03.pdf although probably not worth any complexity

[burdges]

I'm going to judge such defenses as being only a fig leave for now, and thus postpone this indefinitely. If anyone else has use for ring signatures then send a pull request.. or ask for help. :)

[burdges]

We've increased interest in this due to the babe block time issue, so I'll link more literature

All the simple constructions have linear cost https://eprint.iacr.org/2003/067.pdf and https://www.iacr.org/cryptodb/archive/2002/ASIACRYPT/50/50.pdf so 32 * k * n^2 for babe commitments from n validators for k blocks per epoch. And AOS looks less good.

RingCT 2.0 and https://www.cs.dartmouth.edu/~trdata/reports/TR2009-643.pdf are so poorly written they make me doubt Monero's security. No form of DDH is satisfied by a Type I paring.

RingCT 2.0 actually copies badly from the pairing-based accumulator designs in https://eprint.iacr.org/2005/123.pdf and https://eprint.iacr.org/2016/766.pdf but they do require each party prove building their own accumulator, not so good. I donno if https://eprint.iacr.org/2018/1188 helps.

Ring Signatures of Sub-linear Size Without Random Oracles by Nishanth Chandran, Jens Groth, and Amit Sahai achieves square root bandwidth by placing the public keys into a matrix from which it issued certificates on ephemeral keys, which incidentally make a VRF easy. As written, it requires pairings, but we might think along similar ideas or investigate the bulletproofs code.