Algebraic Attacks on Round-Reduced Rain and Full AIM-III

Picnic is a NIST PQC Round 3 Alternate signature candidate that builds upon symmetric primitives following the MPC-in-the-head paradigm. Recently, researchers have been exploring more secure/efficient signature schemes from conservative one-way functions based on AES, or new low-complexity one-way functions like Rain (CCS 2022) and AIM (CCS 2023 and Round 1 Additional Signatures announced by NIST PQC). The signature schemes based on Rain and AIM are currently the most efficient among MPC-in-the-head-based schemes, making them promising post-quantum digital signature candidates. However, the exact hardness of these new one-way functions deserves further study and scrutiny. This work presents algebraic attacks on Rain and AIM for certain instances, where one-round Rain can be compromised in 2 ^{n / 2} for security parameter n∈ { 128, 192, 256 }, and two-round Rain can be broken in 2 ^120.3, 2 ^180.4, and 2 ^243.1 encryptions, respectively. Additionally, we demonstrate an attack on AIM-III (which aims at 192-bit security) with a complexity of 2 ^186.5 encryptions. These attacks exploit the algebraic structure of the power function over fields with characteristic 2, which provides potential insights into the algebraic structures of some symmetric primitives and thus might be of independent interest.