An efficient multivariate threshold ring signature scheme

• Published in: Computer standards and interfaces 2021-02, Vol.74, p.103489, Article 103489
• Main Authors: Duong, Dung H., Tran, Ha T.N., Susilo, Willy, Luyen, Le Van
• Format: Article
• Language: English
• Subjects: MQ problem; Multivariate analysis; Multivariate cryptography; Post-quantum cryptography; Threshold ring signature
• ISSN: 0920-5489; 1872-7018
• DOI: 10.1016/j.csi.2020.103489

•Propose a new threshold identification protocol from multivariate polynomials.•Obtain an efficient threshold multivariate signature.•Provide concrete choice of parameters.•Provide improvements compared to the previous results. At CRYPTO 2011, Sakumoto et al. introduced the first 3-pass identification protocol with security reduction to the MQ problem and impersonation probability 23. Petzoldt et al. (AAECC 2013) extended that protocol into a threshold ring signature scheme, which later was improved by Zhang and Zhao (NSS 2014). In 2015, Monteiro et al. (IEICE 2015) improved the 3-pass identification protocol of Sakumoto et al. to the one with impersonation probability 12. In this paper, we utilize the previous methods and the protocol by Monteiro et al. (2015)[20] to propose an efficient threshold ring signature. As a result, our scheme is more efficient than all previous multivariate threshold signature schemes in terms of both communication cost and signature length. In particular, the signature length of our scheme is 40% and 22% shorter than that of Petzoldt et al. and Zhang–Zhao respectively.