On the security of multivariate-based ring signature and other related primitives. (May 2023)

• Record Type: Journal Article
• Authors: Srivastava, Vikas; Debnath, Sumit Kumar; Tiwari, Sharwan Kumar; Singh, Harshdeep
• Is Part Of: Journal of information security and applications. Volume 74(2023)
• Publication Date: 2023-05
• Subjects: Post-quantum cryptography -- Multivariate public key cryptography -- Cryptanalysis -- Underdetermined multivariate quadratic equations; Computer security -- Periodicals; Information technology -- Security measures -- Periodicals; 005.805
• DOI: 10.1016/j.jisa.2023.103474
• Languages: English
• ISSNs: 2214-2126

Abstract

Abstract: The multivariate public-key cryptography (MPKC) provides a promising class of post-quantum signature schemes. Its theoretical security comes from the intractability of the multivariate quadratic problem ( M Q problem), which is an NP-hard problem [1] . Nevertheless, not every instance of M Q -problem is hard [2–6] while the problem itself is NP-hard. Thus, it is important to understand and analyze the nature of the quadratic systems used in existing MPKC so that the security of the multivariate schemes can be properly assessed. Herein, we present a detailed cryptanalysis of the multivariate based 'ring' signature scheme presented by Wang et al. [7] . We utilize the attacks on the underdetermined system of multivariate quadratic equations. We prove both theoretically and experimentally that the scheme (Wang et al. [7] ) can be broken in polynomial time even for rings of small size. Additionally, we observed that the attack strategy we proposed in this work is not only limited to [7], but can also be applied to break the unforgeability of other multivariate based schemes such as verifiable ring signature scheme [8], multivariate group signature scheme [9], and Gui and GeMSS based ring signature scheme [10, 11] .