Algebraic Cryptanalysis and Countermeasures of Lightweight Signature Scheme Based on Multivariate Quadratic Polynomials
摘要
Multivariate Public Key Cryptography (MPKC) is a promising candidate for Post Quantum Cryptography (PQC) that ensures data security, information security, computer system security, and network security against large-scale quantum computers. Among the various threats to MPKC, MinRank attacks are crucial to MPKC, as they attempt to solve the MinRank problem given a public key and can break several multivariate systems. Recent advancements have introduced the rectangular MinRank attack, which breaks the Rainbow signature scheme by altering Rainbow’s public keys. This study examines the rank and structural weaknesses of the lightweight signature scheme based on multivariate quadratic equations. In this article, we present the cryptanalysis of the multivariate quadratic polynomial-based digital signature algorithm, called Lite-Rainbow, which is based on the state-of-the-art signature scheme Rainbow, through a rectangular MinRank attack and a simple attack. In addition, we provide countermeasures to overcome the proposed attack on lightweight signature schemes.