A New Multivariate Based Threshold Ring Signature Scheme

In CRYPTO 2011, Sakumoto et al. presented a 3-pass identification protocol whose security is solely based on the MQ problem. This identification protocol was extended to a threshold ring signature scheme by Petzoldt et al. via Fiat-Shamir transformation in AAECC 2013. In this paper, we present a multivariate based G-protocol based on Sakumoto et al.'s work, and extend it to a threshold ring signature scheme by applying G-transformation (TIFS 2013). Compared with Petzoldt et al.'s work, our scheme reduces signature length and rounds by 21% and 29% respectively to achieve 80-bit security. What's more, our scheme has higher level provable security, enjoys much better performance on power limited devices, and can be flexible deployed in interactive protocols. To the best of our knowledge, it is the first application of G-transformation in post-quantum cryptography.