anon: shorter signatures / more properties for ad hoc rings?

[tucnak]

Hello,

The current ad hoc style ring signature gets too big as ring grows in size, due to the fact that it takes O(n) of memory.

I've been fiddling around with Kyber for a couple of weeks now, as well as trying to read as much relevant literature as possible. Then I came across this paper, which despite being inapplicable to Kyber, has a nice comparison table of the different approaches taken over the years, Secure ID-based linkable and revocable-iff-linked ring signature with constant-size construction ^[pdf] (2013)

This is a comparison table from the paper, referring to surviving prior art:

Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups ^[pdf] (2004) is one of the first linkable constructs. This particular incarnation does t-out-of-n threshold signatures.

Short Linkable Ring Signatures for E-voting, E-cash and Attestation ^[pdf] (2004) is a constant-memory signature construction (Dodis et al.) with linkability.

Short Linkable Ring Signatures Revisited ^[pdf] (2006) is a good read, but I still can't wrap my head around accumulators, and frankly, pairing too. I use Ed25519 suite, which gives me 256-bit private keys. Does this mean that I can use same scalar for both Ed25519, as well as Bn256?

Ring Signatures of Sub-linear Size Without Random Oracles ^[pdf] (2007) is a game changer because of O(√n) space efficiency, where n is the number of key pairs.

Logarithmic size Ring Signatures Without Random Oracles ^[pdf] (2015) is more like O(n), seriously!

Ring Signatures: Logarithmic-Size, No Setup — from Standard Assumptions ^[pdf] (2019) seemingly manages to do it all and provide linkable log-sized non-interactive signatures with no trusted setup!

Compact linkable ring signatures and applications ^[pdf] (2019) has a new signature scheme, d-CLSAG signatures. These have d-dimensional keys and are compact linkable spontaneous anonymous group signatures in the sense that signature size scales with the sum of ring size and the dimension d.

Do I stand a chance implementing any of these algorithms, if yes, then which in particular will be a nice idea, or do I really need to be a seasoned cryptographer, if all I'm really after is shorter signatures? I'm willing to PR, too.

Cheers,
Ian

@jeffallen

[ineiti]

Hi @tucnak,

thanks for the suggestion. I scanned through the paper for 5 minutes, and it looks doable to me to implement the proposition in section 4.2. The bn256 suite in kyber should allow to set things up and going.

However I have no idea whether their security proofs hold up or not. From a 'decentralization' freak point of view, if I understand correctly, the proposed scheme in the paper from Man Ho Au requires to have a trusted third party to do the ID setup and to keep the private key. Which is not acceptable from a purist point of view ;)

You'd have to look with @jeffallen and @bford if they would like to add this signature scheme to the kyber library, but given a good implementation I would say why not?

There has been some work by a PhD student 2 years ago to look for a decentralized linkable ring signature with O(1) signature size, but it seemed to be really complicated. He also ended up with an accumulator-base scheme, but then distributed the private key of the Public Key Generator, IIRC.

[tucnak]

Thank you for your informative answer!

Perhaps I was misleading in the way I reasoned about my OP, the 2013 paper (Au et al.) was mentioned first because I thought it had the most informative comparison table of all. Indeed, some of these (ID- and PKG-based) are irrelevant in the Kyber setting, yet I thought it was worth having them for context. This particular paper hardly remains in the focus, I believe.

For example, I think these two aforementioned (2019) papers should be much more interesting: Ring Signatures: Logarithmic-Size, No Setup — from Standard Assumptions ^[pdf] and Compact linkable ring signatures and applications ^[pdf]. The former claims to achieve logarithmic-size ring signatures in the standard model, while the latter seems to be some kind of novelty, log-signatures for multi-dimensional keys, whatever it really is.

I feel the need to ask you a couple more questions, if you may!

1. Bn256, as I understand, operates over 256-bit Barreto-Naehrig curves. From what I've read in literature, it seems pairing constructions are increasingly more popular, and I would love to try, and implement some of these algorithms, provided they are in some way compatible with my existing Ed25519 key setup. This must sound silly to a seasoned cryptographer, but can I somehow go from Ed25519 to Bn256?
2. Can you recommend a book or some kind of comprehensive entry-level resource in cryptography for software engineers?

[ineiti]

OK - now I understand better. I will try to look at the papers you proposed. With regard to the other questions:

1. no, you cannot use private/public keys from ed25519 in bn256. You can reason more or less the same way about bn256.G1 and bn256.G2 as you reason about ed25519 in general. But the pairing operation itself is a new beast.
2. people often refer to https://nostarch.com/seriouscrypto, even though the book was too deep for me. I'm still looking for something like https://jvns.ca/linux-comics-zine.pdf for cryptography, but that might be just too dangerous ;) Even though I'd like to have a go at it.

[shachar1236]

@tucnak Did you implement this already?