Paper 2022/1170 Original: eprint.iacr.org/2022/1170 ↗

TRIFORS: LINKable Trilinear Forms Ring Signature

Abstract

We present TRIFORS (TRIlinear FOrms Ring Signature), a logarithmic post-quantum (linkable) ring signature based on a novel assumption regarding the equivalence of alternating trilinear forms. The basis of this work is the construction by Beullens, Katsumata and Pintore from Asiacrypt 2020 to obtain a linkable ring signature from a cryptographic group action. The group action on trilinear forms used here is the same employed in the signature presented by Tang et al. at Eurocrypt 2022. We first define a sigma protocol that, given a set of public keys, the ring, allows us to prove the knowledge of a secret key corresponding to a public one in the ring. Furthermore, some optimisations are used to reduce the size of the signature: among others, we use a novel application of the combinatorial number system to the space of the challenges. Using the Fiat-Shamir transform, and taking into account the attack of Beullens from Crypto 2023, we obtain a (linkable) ring signature of competitive length with the state-of-the-art among post-quantum proposals for security level 128.