Paper 2022/1322

Efficient Linkable Ring Signature from Vector Commitment inexplicably named Multratug

Abstract

In this paper we revise the idea of our previous article “Lin2-Xor Lemma: an OR-proof that leads to the membership proof and signature” and introduce another lemma, called Lin2-Choice, which is a generalization of the Lin2-Xor lemma. With the Lin2-Choice lemma we obtain a compact general-purpose trusted-setup-free log-size linkable threshold ring signature called EFLRSL. The signature size is 2log(n+1)+3l+1, where n is the ring size and l is the threshold. By extending the set membership argument of the Lin2-Choice lemma we create a multifunctional version of the EFLRSL signature aliased as Multratug, of size 2log(n+l+1)+7l+4. In addition to signing a message, Multratug proves balance and allows for easy multiparty signing, which makes it suitable for blockchains. We use a black-boxed vector commitment argument as the pivotal building block for both of EFLRSL and Multratug. Only the black-boxed pivot contributes components that depend on the ring size n into the signature sizes. This makes both versions of our signature combinable with other proofs, thus allowing overall size reduction. All this takes place in a prime-order group without bilinear parings under the decisional Diffie-Hellman assumption in the random oracle model. Both versions of our signature are unforgeable w.r.t. insider corruption and existentially unforgeable under chosen message attack. They remain anonymous even for non-uniformly distributed and malformed keys, which makes it possible to use them as a log-size drop-in replacement for LSAG-based schemes.