Paper 2022/1322

Efficient Linkable Ring Signature from Vector Commitment inexplicably named Multratug

Abstract

In this paper we revise the idea of our previous work ‘Lin2-Xor lemma and Log-size Linkable Threshold Ring Signature’ and introduce another lemma, called Lin2-Choice, which extends the Lin2-Xor lemma. Using an novel zero-knowledge membership proof argument defined in the Lin2-Choice lemma, we create 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 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 simultaneously proves balance and allows for easy multiparty signing. We use an arbitrary vector commitment argument in the role of the pivotal building block for both versions of our signature, considering it as a black box. Only the black-boxed pivot contributes components that depend on the ring size n into the signature sizes. This makes both of EFLRSL and Multratug combinable with other proofs, with 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 proved 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.