Multivariate polynomial systems over Galois fields or finite fields present a promising foundation for post-quantum digital signatures, with their security grounded in the Multivariate Quadratic (MQ) Problem. Although the MQ-Problem is NP-hard, the difficulty of solving it varies across different instances, necessitating a deep understanding of the quadratic polynomial structures in these schemes for accurate security evaluations. In this paper, we conduct a cryptanalysis of a group signature scheme based on the Rainbow signature. Our analysis reveals a critical vulnerability where an adversary can forge group signatures by retrieving the secret key through public data exploitation and leveraging the subspace structure inherent to Rainbow. Remarkably, this key retrieval can be executed with fewer than \(2^{65}\) field operations. To address this vulnerability, we provide countermeasures that significantly enhance security without imposing additional computational overhead.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Cryptanalysis and Countermeasures on Multivariate Polynomial-Based Group Signature Scheme

  • Kuldeep Namdeo,
  • Dheerendra Mishra,
  • Namita Srivastava

摘要

Multivariate polynomial systems over Galois fields or finite fields present a promising foundation for post-quantum digital signatures, with their security grounded in the Multivariate Quadratic (MQ) Problem. Although the MQ-Problem is NP-hard, the difficulty of solving it varies across different instances, necessitating a deep understanding of the quadratic polynomial structures in these schemes for accurate security evaluations. In this paper, we conduct a cryptanalysis of a group signature scheme based on the Rainbow signature. Our analysis reveals a critical vulnerability where an adversary can forge group signatures by retrieving the secret key through public data exploitation and leveraging the subspace structure inherent to Rainbow. Remarkably, this key retrieval can be executed with fewer than \(2^{65}\) field operations. To address this vulnerability, we provide countermeasures that significantly enhance security without imposing additional computational overhead.